Quines Are Not Self-Replication

Original post: here.

If we were to read the blog post here entitled: Quines (self-replicating programs), then we would see it make a few definitions and points about quines.

Firstly it defines quines as such:

Def. 0 - Quine - a computer program which prints its own listing

It also alludes to mathematical theorems primarily focused around the fixed-point theorem which it rightfully nicknames "Kleene's Fixed Point-Theorem".

The post generally revolves around mathematical theorems entirely based on the starting premise that a program is (effectively) always nothing more or reducible to the concept of a "computable function".

However, a program does not have to be a function. It may not be modelable as a simple input and output. Or, more specifically, a functional interpretation of a sequence may be only one of many possible ways to interpret what that sequence "is". Although, considering all programs as sets of sequences covers any programs which are explicitly designed to implement a function and those that could be simply interpreted, in one way, as being such.

The source code for a quine is a spatial program since they are invariant across time (they will remain the same string regardless of the year or day). Executing computer programs (as we run computer programs today) are temporal programs since they do not require a specific computer running at a specific spatial location.

If a program is truly self-replicating then it would be able to reproduce itself during its own execution. This means that a spatial program can't actually ever self-replicate.

Thrm 1. A spatial program cannot self-replicate.

It can however, and obviously so, contain a replication of another spatial program (replicated sub-sequence).

Cor. 1. A spatial program can contain repetitions of some sub-sequence.

However, in order for a program to replicate anything, including itself, it must be a sequence across time.

This is interesting, because usually when we talk about a quine we are discussing the source code i.e. we are discussing the spatial program. But, the replication piece takes place within a specific sequence of the temporal program i.e., a particular execution of the resulting compiled binary.

But the binary does not reproduce itself. It reproduces the source code in its execution. So, if neither the source code spatial program nor the binary temporal program are reproducing themselves, can we really say that any self-replication is occurring?

The answer is a very clear and definitive: no. No self-replication is occurring.

But, what we can say is that the binary program is a replicator for the source code (given a particular starting state / input i.e. for a specific subset of sequences in the program).

But, when we look at it simply like this: we have to stop and wonder why all the fuss around associating quines with self-replication and drawing biological analogies?

So then, what is a Quine?

A quine is simply a spatial program that upon compilation will produce a binary that is an implementation of a function for which a fixed point of that function (fixed point = input is the same as the output i.e. unchanged) is the original spatial program string (the source code).

It's basically a mathematical / linguistic parlor trick. Nothing super significant is occurring. It appears more significant because the input string has meaning to people. In this case, it is the source code (literally: source program) that the binary is compiled from.

And that's it. The trick is not to find the source code. It's to find the function. Now, a Quine can also have a single possible execution (i.e. only one possible {input,output} pair as a function) that always outputs its own source code.

So, it's really neat and fun, but it is not self-replication. It interestingly becomes a replicator for the source code when there is only one possible execution of the binary, which is really cool.

And that is generally what we think of when we think of replication around a Quine. A program that prints its own source code (for a particular encoding/language). It's, of course still cool.

The truth is that every string can be turned into a Quine with the right compiler (i.e. the right programming language). The compiled temporal program (the binary) just needs to be an executable that only prints out the original string every time. The trick to building a quine is finding the function for which the "source code string" is a fixed-point of, and then implementing (compiling) that function into a runnable binary.

Further Reading

• https://cs.stackexchange.com/questions/92522/why-does-the-fixed-point-theorem-apply-to-quines
• https://en.wikipedia.org/wiki/Indirect_self-reference