2
$\begingroup$

I was going through the Wikipedia page on Quines and did not understand this paragraph -

A quine is a fixed point of an execution environment, when the execution environment is viewed as a function transforming programs into their outputs. Quines are possible in any Turing-complete programming language, as a direct consequence of Kleene's recursion theorem.

I did not understand -

  1. What is a fixed point?
  2. What is the Kleene's recursion theorem?
  3. How do these two relate with Quines?

I followed the links to both fixed point and Kleene's recursion theorem on Wikipedia but wasn't able to understand the content in there. It was a little too complex for me. I am looking for a simplified explanation of this paragraph. If it's not possible to do that (because for instance the topic requires knowledge of some higher level Computer Science concepts) that's understandable, please comment the same.

Thanks!

$\endgroup$
4
  • 1
    $\begingroup$ A fixed-point of a function is an element such that its image by the function is the element itself, $f(x)=x$. Here the function is the transformation of a program into the output of this program, hence quines are fixed-points of this function. $\endgroup$
    – user16034
    Commented Aug 10, 2023 at 12:21
  • $\begingroup$ You should have clicked through to least fixed point, then to fixed point, to find its definition. This really means the paragraph should be rewritten. A layperson should be able to make sense of it. $\endgroup$ Commented Aug 10, 2023 at 12:29
  • 2
    $\begingroup$ I have changed that paragraph so that “fixed point” links to the article Fixed point (mathematics), answering question 1. Question 3 is answered in the 2nd paragraph of the article on the recursion theorem, which says “The recursion theorems can be applied to ... generate quines”. $\endgroup$
    – PJTraill
    Commented Aug 11, 2023 at 23:00
  • $\begingroup$ Hmmm, that's a mighty poor sentence. I wonder if we can suggest a change or if it's hopeless to try to actually change a Wikipedia page. $\endgroup$
    – cody
    Commented Aug 14, 2023 at 19:41

3 Answers 3

3
$\begingroup$

What is a fixed point?

A fixed point of a function is a value unchanged by that function. For example $0^2=0$ and $1^2=1$, so $0$ and $1$ are fixed points of the squaring function. Similarly “ASDF” is a fixed point of the function converting text into upper case.

This was unclear at the time of asking, as ‘fixed point’ in Wikipedia was inappropriately linked; this has been fixed.

What is Kleene’s recursion theorem?

There are actually two, but they both say that certain functions have fixed points. The second theorem, which is relevant here, applies to computable functions. (The first concerns “enumeration operators”, which are mathematical relations between natural numbers and sets of natural numbers.)

How do these two relate to quines?

Kleene’s second recursion theorem can be used to prove that quines, which are fixed points, exist in most programming languages.

As the paragraph that confused you said, a quine (a self-printing programme) can be seen as a fixed point of the function that turns a programme (in a given programming language) into the output of that programme (when run with no input): the output is the same as the input. If the programming language is Turing complete, this function satisfies the conditions of Kleene’s recursion theorem, so it must have a fixed point, i.e. a quine in that language. This applies to most current programming languages.

To follow the proofs of all this you need some technical knowledge and some mathematical maturity. You may be able get the former from the Wikipedia articles or from a course or book on computability theory, while the latter comes with practice.

$\endgroup$
3
  • $\begingroup$ Thank you. This is very helpful! $\endgroup$ Commented Aug 12, 2023 at 6:31
  • 1
    $\begingroup$ @DashwoodIce9 Thank-you, I am glad to hear it — worth an upvote? $\endgroup$
    – PJTraill
    Commented Aug 12, 2023 at 16:27
  • 1
    $\begingroup$ I tried. Unfortunately, I haven't got the required reputation for that yet :( Need 15 points. $\endgroup$ Commented Aug 12, 2023 at 16:57
2
$\begingroup$

Quines are programs which when executed, print their own code.

$\endgroup$
1
  • 2
    $\begingroup$ This does not answer the 3 questions posed in the OP, and they presumably knew this as it is in the 1st paragraph of the cited Wikipedia article (as of 2023-08-12, since at latest 2023-05-29). $\endgroup$
    – PJTraill
    Commented Aug 11, 2023 at 23:09
0
$\begingroup$

A fixed point is a solution $x$ to a fixed-point equation $x = f(x)$.

The Kleene Recursion Theorem states that there is a Universal Recursive Function $f(P(φ),y)$ that includes every other recursive function $φ(y)$ in it, in the sense that $f(P(φ),y) = φ(y)$.

In contemporary terms, $f$ is a Loader and $P(φ)$ is the Application (a.k.a. a "Computer Program") that is being loaded, $φ$ is what the application $P(φ)$ computes, while the evaluation $f(P(φ),y)$ is the execution of the application that was loaded. The evaluation of a recursive function is "computation" and a Universal Recursive Function is a Universal Computer, or just Computing Machine actually, since that is what a computer is meant to be - in contrast to an Embedded Controller which functions more as a dedicated machine ... except that in recent decades embedded controllers have come equipped with their own loaders and execution environments.

In general $y$ is a - possibly empty - list of inputs, rather than just a single input. So, it's best to treat it as a vector, and allow for the case of 0-component vectors. An operating system is an environment set up on a machine whose function is to coordinate the execution of applications and whatever other support is required for this. In an operating system environment a program, like one written in either of the programming languages C or C++ will have a top-level function (called "main") that accepts, as its input, a vector of inputs: "argv" is the name usually used for the vector, and "argc" the name usually used for the count of the number of components in "argv"; while "void" is used to handle the case of an empty vector. The function "main", for such a program, is effectively $φ$ itself, while the actual text of the program (or more accurately: the machine-language image that the text compiles into) is the $P(φ)$.

In the context of the article $y$ is the empty list. So, the fixed point for $f(P(φ))$ is actually for the other variable: the fixed point of $f(x) = x$. We already have a name for that: $x$ is a self-replicating program and the $φ$, for which $x = P(φ)$, is the function that $x$ specifies.

A similar concept can be entertained for Universal Constructors. In contrast to computing things, a constructor makes things (i.e. it's a function $φ(y)$ whose outputs are things), and the specification $P(φ)$ is its design. A Universal Constructor $f(P(φ),y)$, therefore, is a function that can make anything that anything else can make. A construction function $φ$ with zero inputs just flat-out makes things on its own. The fixed point of $x = f(x,y)$ for zero-input constructors $φ$ is, thus, the design $x = P(φ)$ of a self-replicating constructor $φ$. Constructors, these days, are called Three Dimensional Printers. The idea of formalizing constructors is a Hungarian-thing: Von Neumann and Lindenmayer (and his L-Systems); it's also the root of Artificial Life, especially when you start talking about things being self-replicating.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.