April 15th, 2025

April 15th, 2025

While teaching the Alife course, the question of how the Kleene fixed point theorem (and relatedly, the y-combinator) should be used to warrant the existence of self-replicators and of quines in programming language was a bit unclear...

While teaching the Alife course, the question of how the Kleene fixed point theorem (and relatedly, the y-combinator) should be used to warrant the existence of self-replicators and of quines in programming language was a bit unclear...

This has all gotten much better lately, though I still think there is room for progress around the details (for instance, in a programming language like python)

This has all gotten much better lately, though I still think there is room for progress around the details (for instance, in a programming language like python)

Then, this also re-appeared in the context of the halting problem, which is used to argue about the computational undecidability of many questions about cellular automata

Then, this also re-appeared in the context of the halting problem, which is used to argue about the computational undecidability of many questions about cellular automata

Anyway, if we start from the y-combinator, we get something like

Anyway, if we start from the y-combinator, we get something like

$Y f = (\lambda x.f(x \, x))(\lambda x. f(x\, x)) $

The way I like to think of this is by saying 'wrap-auto-feed', where we think of $f$ as being the 'wrapper' (more about this in the relevant contexts for quines in programming languages, and for self-replicators in cellular automata), and we autofeed $x$ to itself

The way I like to think of this is by saying 'wrap-auto-feed', where we think of $f$ as being the 'wrapper' (more about this in the relevant contexts for quines in programming languages, and for self-replicators in cellular automata), and we autofeed $x$ to itself

And what we want is a fixed point for the wrapper in some sense

And what we want is a fixed point for the wrapper in some sense

The naturally tricky thing with the y-combinator is that if we try to 'resolve' it, then we get an infinite recursion

The naturally tricky thing with the y-combinator is that if we try to 'resolve' it, then we get an infinite recursion

For instance, one step of the evaluation of $Yf$ gives:

For instance, one step of the evaluation of $Yf$ gives:

$f((\lambda x.f(xx))(\lambda x.f(xx)))$

And naturally, this is $f(Yf)$... and if we try to fully 'resolve' this, we will just get something like $(f\circ f\circ\cdots\circ f)(Yf)$, and we 'dig an infinitely deep hole' if we keep evaluating

And naturally, this is $f(Yf)$... and if we try to fully 'resolve' this, we will just get something like $(f\circ f\circ\cdots\circ f)(Yf)$, and we 'dig an infinitely deep hole' if we keep evaluating

The point is not so much that we need to resolve this expression (which can't be resolved, anyway), but precisely that we can write a finite expression that contains a deferred version of the evaluations

The point is not so much that we need to resolve this expression (which can't be resolved, anyway), but precisely that we can write a finite expression that contains a deferred version of the evaluations

Intuitively, if we think of 'wrap-auto-feed', we have something like the one-step evaluation of 'the auto-feed of the wrap-auto-feed' is 'wrap-auto-feed of the wrap-auto-feed' which is the 'wrap of the auto-feed of the wrap-auto-feed', and hence the evaluation corresponds to one step of wrapping

Intuitively, if we think of 'wrap-auto-feed', we have something like the one-step evaluation of 'the auto-feed of the wrap-auto-feed' is 'wrap-auto-feed of the wrap-auto-feed' which is the 'wrap of the auto-feed of the wrap-auto-feed', and hence the evaluation corresponds to one step of wrapping

So... how does this imply the existence of quines, in e.g. Python?

So... how does this imply the existence of quines, in e.g. Python?

This definitely shows that we can construct for instance construct quines of the form

This definitely shows that we can construct for instance construct quines of the form

for an appropriate replacement of $???$ inside the quotemarks

for an appropriate replacement of $???$ inside the quotemarks

So we want to construct an expression $x$ to be evaluated (without side effects) such that $eval(x)=wrap(x)$, where $wrap$ is defined as

So we want to construct an expression $x$ to be evaluated (without side effects) such that $eval(x)=wrap(x)$, where $wrap$ is defined as

And so, solving that equation is indeed possible with the y-combinator idea

And so, solving that equation is indeed possible with the y-combinator idea

We can in particular this nice 'almost-quine' (except for some quotemark problems, it writes its own input)

We can in particular this nice 'almost-quine' (except for some quotemark problems, it writes its own input)

What is nice is that we see the auto-feed is

What is nice is that we see the auto-feed is

Here $chr(36)$ is just the dollar sign, but we don't want to write '\$' for the obvious reason that we will need to solve the problem that this would create

Here $chr(36)$ is just the dollar sign, but we don't want to write '$' for the obvious reason that we will need to solve the problem that this would create

And so, we really see that the string to put in the eval is _apply auto-feed to wrap-auto-feed_

And so, we really see that the string to put in the eval is apply auto-feed to wrap-auto-feed

This suggests that 'wrap-auto-feed' is perhaps not what this should be called, but rather 'wrap-_then_-auto-feed', to emphasize that we wrap an _expression that will be resolved to autofeed_

This suggests that 'wrap-auto-feed' is perhaps not what this should be called, but rather 'wrap-then-auto-feed', to emphasize that we wrap an expression that will be resolved to autofeed

A fundamental idea of the y-combinator is that the resolution is _deferred_

A fundamental idea of the y-combinator is that the resolution is deferred

(Note that quines are also deferred expressions in some sense, because they of course yield an output such that if we had to evaluate it, would lead to an infinite loop)

(Note that quines are also deferred expressions in some sense, because they of course yield an output such that if we had to evaluate it, would lead to an infinite loop)

Some Things to Think About

Some Things to Think About

There is something about the lambda expressions there, about exactly what we do (though it is universal) that should be examined

There is something about the lambda expressions there, about exactly what we do (though it is universal) that should be examined

Also, for the self-replicators within cellular automata constructions, for instance, the wrap idea is exactly the same (in order to have a copy of the tape, we consider a piece of data $d$on the tape to be determined, such that upon evaluation, it should transform into the stream of bits that will print everything including $d$... and that's the wrapping function)

Also, for the self-replicators within cellular automata constructions, for instance, the wrap idea is exactly the same (in order to have a copy of the tape, we consider a piece of data $d$on the tape to be determined, such that upon evaluation, it should transform into the stream of bits that will print everything including $d$... and that's the wrapping function)