[Fis] CODE DISCUSSION. Recursion

Louis Kauffman loukau at gmail.com
Wed Sep 22 19:29:43 CEST 2021

Dear Joseph,

(I am sending this again without graphics so it can end up on fis.) 

The RD construction is very general, but we have articulated it with particular models. 

One starts with a domain where distinctions can be made and there is a notion of locality.
In that domain one makes distinctions about given entities 
and replaces the entities by the corresponding signs of distinction. 
These signs amalgamate to become new entities to be distinguished at the next round. 

Lest this seem abstract, look again at the model.

The sign = is an amalgamation of empty word on left and empty word on rght.
The sign ] is amalgamation of empty word on left and  vertical bar | on rght.
The sign [] is amalgamation of vertical bar | on left and  empty word on rght.
The sign O is meant to be a box and so is an amalgamation of vertical bar on left and right.

The point is that the alphabet arises by the amalgamations of previous distinctions and so new symbolic entities arise from the process of distinguishing by these rules.
After the body of this email, I will show you how the two dimensional RD alphabet arises.

This level of model includes notions of language and description in a very elementary formal framework. 
I have not included a logical language or a language that even begins to
have self-reference and ordinary reference. Thus meta-levels and thinking about thinking are not fully reflected in this small model. 
But the action of the model gives one the opportunity to reflect on these
larger issues. I am in the business of finding significant minimal models. 
These models are not going to be complete articulations of the whole situation of thinking about thinking or
reflecting on reflecting. They are intended as ways to help thinking about that. 

Note also that the RD above engages in “mitosis” or “self-replication”. It does so without a reflective level. This is of interest
for thinking about coding in biology and in thinking about what coding would mean in physical situations “below” biology.

Let me give here another example: the audio-active sequences studied by John Horton Conway.
11 - read “one one” and it describes the line above.
21- read “two ones” and it describes the line above.
1211- read “one two, one one” and it describes the line above.
111221- read “three ones, two two’s, one one” and it describes the line above.
312211- read “one three, two two’s, one one” and it describes the line above.
This recursion is an example of "describing describing" and the coding issues are somewhat different from the RD.
We retain locality of interaction and have a fixed alphabet that is less iconic. Counting is needed at the descriptive level.
This recursion requires more structure to run, but it is very very interesting.
Note that 22 is the only self-referential sequence.

Note also that we could write nx —> xx…x (n x’s) meaning that nx describes xx…x. 
In the audio active line we would have

as in

So we have nx —> xx…x
and 2x —> xx
and so
22 —> 22.

This pattern fits into the whole of 20th century logic since Russell.
Let me tender persuasions.
Russell:  Rx = ~xx
This is the definition of the Russell set if you take AB to mean “B is a member of A” and ~ is “not”.
Then: RR = ~ RR is the Russell paradox.
In this formalism, the Russell paradox becomes the production of a fixed point for negation.

Church and Curry generalized this to an abstract formalism (lambda calculus) where they could write
gx = F(xx) for an arbitrary F.
gg = F(gg) and we produce a fixed point for F.
This is exactly how we got to the self reference of 22 by
2x —> xx
22 —> 22 
where here equality is replaced  by reference.

The notion of replacement of reference is integral to Goedelian self-refefrence.
g ——> P(x) now interpreted as “g is the Goedel number of the proposition P(x) with free variable x.
Then let #g be the Goedel number of P(g) so that 
#g —> P(g).
Let the language be rich enough so that # is an operation in the language.
h —> P(#x)
#h—> P(#h)
and P(#h) talks about its own Goedel number.
Then with Goedel let ~B(x) mean that “there is no proof of the statement with Goedel number x.
Then with 
h —> ~B(#x)
#h —> ~B(#h)
and we have produced the proposition ~B(#h) that asserts its own unprovability!
This is the core of Goedel’s incompleteness Theorem.

I hope you see that we have arrived Goedel’s Theorem on a track leading directly from the self-reference of 22, by way of the Russell Paradox.
All this comes from the capacity of language to speak about language and thinking to think about thinking.
Goedel in fact shows us that all formalisms that we build that are rich enough and are consistent will be incomplete.
So there is no intent here to create complete formalisms.
I want to look at how the simplest non trivial formalisms behave, and how even very similar ones such as the RD and the audio activity are related to each other and to 
the larger issues of reference, self reference  and the generation of such dialogues at all levels.

Note also how small formalisms can summarize wide ideas.
The von Neumann Universal Building Machine B acts as follows.
B,x —> X,x.
Give B a blueprint x and B will produce X (the entity described by the blueprint).
Hence if b is the blueprint for B, then B can build itself!
B,b —> B,b.
This is another variant of 2x —> xx so 22—> 22.

Another thing that happened in the 20th century is that everyone got frightened about Rx =~xx giving RR = ~ RR,
and the story I am telling here of the central role of reference and self-reference is still not fully appreciated by mathematical practitioners such as
economists and even physicists.
Very best,

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listas.unizar.es/pipermail/fis/attachments/20210922/c7a004c7/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: RD.png
Type: image/png
Size: 24143 bytes
Desc: not available
URL: <http://listas.unizar.es/pipermail/fis/attachments/20210922/c7a004c7/attachment-0001.png>

More information about the Fis mailing list