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
    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$ 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
    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
    Aug 14, 2023 at 19:41

2 Answers 2

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$ Aug 12, 2023 at 6:31
  • 1
    $\begingroup$ @DashwoodIce9 Thank-you, I am glad to hear it — worth an upvote? $\endgroup$
    – PJTraill
    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$ 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
    Aug 11, 2023 at 23:09

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.