Computer Science C63 Winter 2025
Scarborough Campus University of Toronto
Recursion Theorem
Vassos Hadzilacos
Motivation
As programmers you know that recursion, the ability of a program to call itself, is a powerful technique.
Unfortunately, this feature is not directly available in the Turing machine model: There is no direct way
for a Turing machine to obtain its own code and then use that code in its computation. The Recursion
Theorem is an extremely useful result which asserts that we can, in fact, do this — albeit indirectly.
Informally, it says that when defining a Turing machine M we can imagine that we have available the
instruction “hM i := GetSelf”, which assigns to hM i the code of M , the machine being defined, and then
allows M to use its code hM i in its computation!
For example, consider the following Turing machine, enhanced with this feature. Let’s think of the
input x as an natural number, although in reality it is a string representing a natural number. This way
we can use more common and intuitive notation for applying operations to numbers:
F := on input x:
1 if x = 0 then output 1
2 else
3 hF i := GetSelf
4 a := output of F on input x − 1
5 b := x ∗ a
6 output b
This “enhanced” Turing machine uses recursion to compute the factorial of its input. Note that recursion
is a form of self-reference, and as we have been seeing since the first lecture, self-reference can be the
source of trouble. Later we will see how this ability for self-reference can be exploited to show that certain
problems are undecidable or unrecognizable.
Statement of the Recursion Theorem
The technical statement of the Recursion Theorem is somewhat abstract, so it takes some careful examina-
tion to absorb its meaning and understand how it relates to the above stated goal — of allowing a Turing
machine to effectively obtain, and use, its own code. First let us establish some notation and conventions
that will be useful.
In this document we will be thinking of Turing machines mostly as computers of partial functions,
rather than as language recognizers – i.e., computers of partial functions with only binary output. (Note
that a function is a special case of a partial function, namely one that is defined on all inputs.) If M is a
Turing machine we will use the corresponding lower-case character m to denote the partial function that
M computes. That is, m(x) is the output of M on input x, if M halts on x; if M loops on x, m(x) is
undefined and we denote this as m(x) = ⊥.
So far we have been consideringTuring machines as computers of functions that take one input. It will
be useful here to also consider Turing machines with two inputs — that is, computers of partial functions
with two arguments. This is not really a departure from the single-input Turing machine model since we
can encode a pair of strings by a single string. So a Turing machine with two inputs can be thought of as
a regular Turing machine that takes a single string as its input, “decodes” this string as a pair of strings,
1
and treats the first component of the pair as a first input and the second component of the pair as a second
input. We can now state the Recursion Theorem:
Theorem 5.2 (The Recursion Theorem, Kleene 1938): Let T be a (two-input) Turing machine that
computes the partial function t: Σ∗ × Σ∗ → Σ∗ . Think of the first input of T as the code of a Turing
machine, encoded by a string in Σ∗ . There exists a (one-input) Turing machine R that computes the partial
function r: Σ∗ → Σ∗ such that, for every x ∈ Σ∗ , r(x) = t(hRi, x). Furthermore, the mapping hT i 7→ hRi
is computable.
Let us unpack this: T is a two-input Turing machine whose first input is to be interpreted as the code
of a Turing machine M . T describes how M is to be used on T ’s second input x. For example, recall the
factorial-computing Turing machine (enhanced with the GetSelf instruction) discussed earlier. Consider
the following two-input Turing machine T :
T := on inputs hM i and x:
1 if x = 0 then output 1
2 else
3 a := output of M on input x − 1
4 b := x ∗ a
5 output b
6 halt
Note that this is a normal Turing machine — it does not use the magic instruction GetSelf. It describes
how to use a Turing machine M to manipulate input x: It applies M to x − 1, multiplies the result of
this by x, and outputs the product. What this actually does of course depends on M : Plugging different
Turing machine codes for hM i results in T computing different functions. For example,
• If hM i is a Turing machine that, on any input x, outputs 3, then T computes the function
(
1, if x = 0
f1 (x) =
3x, otherwise
• If hM i is a Turing machine that, on input x, outputs x + 1, then T computes the function
(
1, if x = 0
f2 (x) = 2
x , otherwise
• If hM i is a Turing machine that loops on any input x, then T computes the partial function
(
1, if x = 0
f3 (x) =
⊥, otherwise
The Turing machine R of the Recursion Theorem that corresponds to the above Turing machine T is
precisely the Turing machine F shown earlier, that on input x outputs x!, with the line “hF i := GetSelf”
replaced by a construction that we will see in the proof of the Recursion Theorem — specifically, the Turing
machine that computes hRi from hT i.
The Turing machine T is not limited to using its first input hM i only in the simple manner that the
above example illustrates. Here is another example where hM i is used multiple times on multiple inputs
obtained from x:
2
T 0 := on inputs hM i and x:
1 if x = 0 or x = 1 then output 1
2 else
3 a := output of M on input x − 1
4 b := output of M on input x − 2
5 c := a + b
6 halt
T 0 uses its first input hM i twice: First it applies M on x − 1 and then on x − 2. It then returns the
sum of the results of these two applications of M . As an exercise, determine the Turing machine R that
corresponds to this T 0 according to the Recursion Theorem. (It computes a well-known function!)
Applications
Next we will present three applications of the Recursion Theorem. We will assume that Turing machines
have access to the GetSelf instruction to obtain their code, and then use this ability to create machines
with self-contradictory behaviour thereby proving, by contradiction, that various problems are undecidable
or unrecognizable.
A. Alternative proof of the undecidability of Univ
Suppose, for contradiction, that Univ is decidable, and let DU be decider for it. Now consider the following
Turing machine:
R := on input x:
1 hRi := GetSelf
2 run DU on hR, xi I and then do the opposite
3 if DU accepts then reject
4 else accept
We have:
• If R accepts x, DU rejects hR, xi, which means that R does not accept x.
• If R rejects x, DU accepts hR, xi, which means that R accepts x.
Therefore both cases lead to contradiction, which means that the original assumption, namely that Univ
is decidable, is false.
B. Alternative proof of Rice’s theorem
Let P be any non-trivial property of recognizable languages. We will prove that TP = {hM i: L(M ) ∈ P }
is undecidable.
Suppose, for contradiction, that TP is decidable, and let DP be a decider for it. Since P is non-trivial,
there are Turing machines MY and MN such that L(MY ) ∈ P and L(MN ) ∈ / P . Consider the following
Turing machine:
R := on input x:
1 hRi := GetSelf
2 run DP on R
3 if DP accepts hRi then I behave like MN
4 run MN on x
5 if MN accepts then accept
6 else reject
7 else I behave like MY
8 run MY on x
9 if MY accepts then accept
10 else reject
3
We have: (
L(MN ) ∈
/ P, if DP accepts hRi ⇔ L(R) ∈ P
L(R) =
L(MY ) ∈ P, if DP does not accept hRi ⇔ L(R) ∈
/P
Therefore L(R) ∈ P if and only if L(R) ∈
/ P , which is a contradiction. So the original assumption, namely
that TP is decidable, is false.
C. A new unrecognizability result
For each recognizable language L there are infinitely many Turing machines that recognize it: we can add
any number of useless states or symbols to the description of a machine without changing its essential
functionality. If we order the machines that recognize L by the length of their encoding, the shortest ones
are called minimal for L. Let Min be the set of codes of minimal Turing machines; that is,
Min = {hM i: for every Turing machine M 0 such that L(M 0 ) = L(M ), |hM 0 i| ≥ |hM i|.
Theorem 5.3: Min is unrecognizable.
Proof. Suppose, for contradiction, that Min is recognizable. Then there is an enumerator EMin for Min
(see Week 3 Tutorial, Question 1). Consider the following Turing machine:
R := on input x:
1 hRi := GetSelf
2 repeat
3 hM i := next element of Min output by EMin
4 until |hM i| > |hRi|
5 I Behave like M
6 run M on x
7 if M accepts then accept
8 else reject
The loop in lines 2-4 will terminate because EMin has an infinite number of strings to output (since there
are infinitely many recognizable languages), so it must output arbitrarily long Turing machine codes. So by
lines 6-8 L(R) = L(M ). By the exit condition of the loop |hM i| > |hRi|, so hM i ∈ / Min. This contradicts
the fact that hM i was output by an enumerator for Min.
Note that the above proof actually shows a stronger result than the statement of Theorem 5.3: Not
only is Min unrecognizable, but so is every infinite subset of it!
Some preliminary results
If M and N are Turing machines, M . N denotes the Turing machine that “pipes” M ’s output to N ’s
input (see Figure 1(a)). That is, M . N first runs M on its input and then,
if M halts, it runs N on M ’s
output. Thus, on input x, M . N computes the partial function n m(x) .
If N is a two-input Turing machine, M . N denotes the two-input Turing machine that “pipes” M ’s
output to N ’s first input (see Figure 1(b)): M . N first runs M on its first input; if and when M halts,
M . N runs N using M ’s output as the first input and its second input as N ’s second input.
Thus, in this
case, on inputs x and y, M . N computes the two-argument partial function n m(x), y .
Lemma 5.4: There is a two-input Turing machine Pipe that takes inputs hM i and hN i, and outputs
hM . N i.
Proof. Consider the case where N is a one-input Turing machine. The initial state of M . N is the
initial state of M . Each state transition of M that leads to the halt state is modified to lead to a special
4
x M m(x) x M m(x)
x
x N n(x) N n(x, y)
y
m(x) m(x)
x M N n m(x) x M
N n m(x), y
M .N y
M .N
(a) Piping to 1-input TM (b) Piping to 2-input TM
Figure 1: The “piping” operation . on TMs
state in which the tape head keeps moving left until it reaches the leftmost cell, at which point M . N
enters the initial state of N and continues the computation from there, halting if and when N does.
The case where N is a two-input Turing machine is similar with some straightforward additional
manipulations to save the second input to M . N so that it can be presented as the second input to N
when M completes its computation, the output of which is presented as the first input to N .
Given the preceding description of how M . N operates, it is clear that given hM i and hN i, a Turing
machine Pipe can construct hM . N i.
Note that Pipe is not the Turing machine M . N ; it is a Turing machine that produces the code of
M . N , given the codes of M and N .
Lemma 5.5: There is a Turing machine Print that, on input x, outputs hPx i, where Px is a Turing
machine that outputs x.
Proof. Print hard-codes its input string x = a1 a2 . . . ak into the state transition function of the Turing
machine Px whose code it must output. It can do so by defining a set of states that includes a state qi for
each i ∈ [1..k + 1], where, for i ∈ [1..k], qi “remembers” that the i-th symbol of x is ai and qk+1 is the halt
state. The transition function causes Px to behave as follows: Px starts by erasing its input and returning
the tape head to the leftmost cell; it then enters state q1 , and for each i ∈ [1..k], the transition function of
Px specifies that, if Px is in state qi and the current symbol is t, Px replaces the t by ai , enters state qi+1 ,
and moves to the right. Print then returns the code hPx i of the Turing machine Px described above.
Note that Px takes no input, since it starts by erasing whatever is initially on its tape, so it computes
a function of zero arguments.
Warm-up exercise: A Quine
As a preliminary step towards proving the Recursion Theorem we show how to construct a Turing machine
that outputs its own code.1 This is trickier than it may first appear. Note that PhM i is not such a machine:
its output is hM i and not its own code, which is hPhM i i.
1
A program in any programming language that just prints its own code is called a Quine, after the American philosopher
and logician Willard Van Orman Quine who, among other things, was interested in self-reference and the paradoxes to which
it leads.
5
hPhM i i
hM i Print
Pipe hPhM i . M i hBi
A = PhBi B hPhBi . Bi = hQi
B Q=A.B
Figure 2: The TM B Figure 3: The Quine Q
Theprem 5.6: There is a Turing machine Q that (ignores its input and) outputs its own code hQi.
Proof. Let B be a Turing machine that takes as input hM i and outputs hPhM i . M i. That is, B takes
as input the code of a Turing machine M , and outputs the code of the Turing machine that runs M on
input hM i. B can be built using the Turing machines Pipe and Print of Lemmas 5.4 and 5.5, as follows
(also depicted diagrammatically in Figure 2):
B := on input hM i:
1 a := output of Print on input hM i (i.e., a = hPhM i i)
2 b := output of Pipe on input a and hM i (i.e., b = hPhM i . M i)
3 output b
4 halt
This Turing machine has a code hBi and, by Lemma 5.4, there is a Turing machine PhBi that outputs
hBi. Let A = PhBi .
We claim that Q = A . B has the desired property: it outputs hQi. We have Q = A . B = PhBi . B
(see Figure 3). That is, Q is the Turing machine that runs B on B’s own code, hBi. By the specification of
B, the output of B on hBi is hPhBi . Bi = hA . Bi = hQi. That is, the output of Q is hQi, as wanted.
Proof of the Recursion Theorem
Though a program that prints its own code has a self-referential flavour, it is not quite what we want:
The Recursion Theorem does not only say that a program can print its own code, but that it can use that
code in arbitrary (computable) ways, as specified by the Turing machine T . As we will see, however, the
proof of the Recursion Theorem is a somewhat more elaborate version of the proof of Theorem 5.6. For
convenience we restate the Recursion Theorem below.
Theorem 5.2 (The Recursion Theorem, Kleene 1938): Let T be a (two-input) Turing machine that
computes the partial function t: Σ∗ × Σ∗ → Σ∗ . There exists a (one-input) Turing machine R that
computes the partial function r: Σ∗ → Σ∗ such that, for every x ∈ Σ∗ , r(x) = t(hRi, x). Furthermore, the
mapping hT i 7→ hRi is computable.
Proof of Theorem 5.2. Let B be the same Turing machine as in the proof of Theorem 5.6, except
that the input hM i is interpreted as the code of a two-input Turing machine. As we have seen this simply
means that the Turing machine decodes its input string as if it encoded a pair of strings, and we think
of the two components of that pair as its two inputs. So, on input the code hM i of a two-input Turing
machine M , B outputs hPhM i . M i — that is, the code a Turing machine that outputs the code hM i of M
and uses it as the first input of M .
Next, let A be the Turing machine PhB . T i . That is, A is a Turing machine that, without any input,
outputs the code of a two-input Turing machine that first runs B on its input and then uses B’s output
as the first input of T .
Finally, let R = A . (B . T ) — see Figure 4. We claim that this Turing machine has the desired
property: It computes the partial function r such that r(x) = t(hRi, x). To see this first note that the
output of A is hB . T i. When we run B on this Turing machine code, by the definition of B, its output
6
is hPhB . T i . (B . T )i, and this becomes the first input
of T in R. Therefore, on input x, R outputs
r(x) = t h PhB . T i . (B . T )i, x = t h A . (B . T ) i, x = t(hRi, x), as wanted.
| {z } | {z }
A R
hB . T i hPhB . T i . (B . T )i
A = PhB . T i B
T t(hPhB . T i . (B . T )i, x) = t(hRi, x) = r(x)
x
R = A . (B . T )
Figure 4: The Turing machine R
It remains to show that the mapping hT i 7→ hRi is computable; that is, there is a Turing machine
Recursify that takes as input hT i, where T is a two-input Turing machine, and outputs the code hRi of
the one-input Turing machine R described above. To see this we first note that, by Lemma 5.5, there is
a Turing machine, namely PhBi , that outputs hBi. Using this machine to produce hBi, its input hT i, and
the Turing machine Pipe of Lemma 5.4, Recursify can then produce hB . T i. Using this as input and
the Turing machine Print of Lemma 5.5, Recursify can construct A = PhB . T i . Finally, using A, the
previously produced hB . T i, and Pipe again, Recursify can output hA . (B . T )i, i.e., hRi.