Questions: Kleene's Recursion Theorem and Self-Reference

Question 1

A programmer claims it is impossible to write a program that outputs its own source code without simply hardcoding the source as a literal string. The Kleene recursion theorem says:

• A. The programmer is correct — a program that doesn't hardcode its source cannot know what it is
• B. The programmer is incorrect — the recursion theorem guarantees a quine exists, because the function mapping any program to its 'print self' version has a fixed point
• C. The programmer is correct — reading one's own source requires OS privileges not available to standard programs
• D. The theorem is irrelevant to this question because printing is an I/O side effect, not a computable function

Answer: (B)

Quines are guaranteed to exist by the Kleene recursion theorem. Define f(e) as the index of a program that prints the source code of φ_e. The recursion theorem guarantees a fixed point: an index e* such that φ_{e*} = φ_{f(e*)}, meaning the program at e* behaves exactly like the program that prints the source of φ_{e*} — which is itself. No circular reasoning or OS tricks are required. The fixed-point construction via s-m-n is what makes it work.

Question 2

Rice's theorem states that no non-trivial semantic property of programs is decidable. The proof via the recursion theorem proceeds by:

• A. Assuming the property P is decidable, constructing a computable function f that maps programs satisfying P to programs not satisfying P and vice versa, then deriving a fixed point of f — a contradiction
• B. Reducing every program property to the halting problem and showing the halting problem is undecidable
• C. Using the s-m-n theorem to enumerate all programs with property P and showing the enumeration diverges
• D. Proving that the complement of any decidable property is also decidable, which leads to a contradiction with known results

Answer: (A)

If P were decidable, we could build a computable function f: given any program index e, check if φ_e has property P; if yes, output the index of a program without P; if no, output the index of a program with P. By the recursion theorem, f has a fixed point e* where φ_{e*} = φ_{f(e*)}. But f(e*) disagrees with e* on whether P holds — a contradiction. The recursion theorem's guarantee of fixed points thus makes any 'flip the property' function impossible, ruling out decidability.

Question 3

Because of the Kleene recursion theorem, every computable transformation of program indices has at least one fixed point — a program that behaves identically before and after the transformation is applied.

• T. True
• F. False

Answer: True

This is precisely what the recursion theorem states: for any total computable function f (mapping indices to indices), there exists an index e such that φ_e = φ_{f(e)}. The program at index e 'behaves the same' as the program at index f(e), even though they may have different indices (different code). This is why no computable transformation can be designed to always change the behavior of programs — the fixed point is inescapable.

Question 4

The Kleene recursion theorem implies that self-referential programs — programs that reason about their own code — are paradoxical and can seldom be defined within standard computational models.

• T. True
• F. False

Answer: False

The theorem implies exactly the opposite: self-reference is not paradoxical but is an inescapable, well-defined feature of any sufficiently powerful computational system. Quines, programs that inspect their own indices, and programs that simulate themselves are all constructively guaranteed to exist. Far from being paradoxical, self-reference is the engine behind major results in computability — including the undecidability of the halting problem and Rice's theorem — all of which work precisely because programs can legitimately refer to themselves.

Question 5

Explain, in your own words, why a quine (a program that outputs its own source code) is guaranteed to exist by the Kleene recursion theorem. What role does the fixed point play?

Model answer: Define a computable function f where f(e) is the index of a program that, when run, prints the source code of the program at index e. The recursion theorem guarantees that f has a fixed point: an index e* such that φ_{e*} = φ_{f(e*)}. This means the program at e* behaves the same as the program that 'prints source of e*' — in other words, the program at e* prints its own source. The fixed point is the quine: it is not hardcoded, it is constructed via s-m-n by building a program that first obtains its own index, applies f, and simulates the result.

The key insight is that obtaining one's own index is possible through s-m-n machinery — programs can compute their own Gödel numbers. Once a program has its own index, it can use f to find the index of its 'print me' version, then simulate it. The recursion theorem packages this self-referential construction cleanly: fixed points of computable functions always exist, so any computable operation on programs always has a program that is 'immune' to that operation in the sense of being its own fixed point.