Recall the formal statement of Rice's theorem:

We will use the notation $\left[n\right]$ for the $n$th Turing machine under some fixed numbering system. Each such machine induces a function, which we will also write as $\left[n\right]$ where this is unambiguous due to context; then it makes sense to write $\left[n\right]\left(m\right)$ for the value that machine $\left[n\right]$ outputs when it is run on input $m$.

Let $A$ be a non-empty, proper ^[1] subset of $\left\{Graph\right(n):n\in N\}$, where $Graph\left(n\right)$ is the graph of the partial function computed by $\left[n\right]$, the $n$th Turing machine. Then there is no Turing machine $\left[r\right]$ such that:

• $\left[r\right]\left(i\right)$ is $1$ if $Graph\left(i\right)\in A$
• $\left[r\right]\left(i\right)$ is $0$ if $Graph\left(i\right)\notin A$.

We give a proof that is (very nearly) constructive: one which (if we could be bothered to work it all through) gives us an explicit example ^[2] of a Turing machine whose "am-I-in-$A$" nature cannot be determined by a Turing machine. ^[3]

We will present an intermediate lemma which does all the heavy lifting; this makes the actual reasoning rather unclear but very succinct, so we will also include an extensive worked example of what this lemma does for us.

Fixed point theorem

The intermediate lemma is a certain fixed-point theorem.

Let $h:N\to N$ be total computable: that is, it halts on every input. Then there is $n\in N$ such that $Graph\left(n\right)=Graph\left(h\right(n\left)\right)$. ^[4]

That is, the "underlying function" of $n$ - the partial function computed by $\left[n\right]$ - has the same output, at every point, as the function computed by $\left[h\right(n\left)\right]$. If we view $h$ as a way of manipulating a program (as specified by its description_number), then this fixed-point theorem states that we can find a program whose underlying function is not changed at all by $h$.

The proof of this lemma is quite simple once the magic steps have been discovered, but it is devilishly difficult to intuit, because it involves two rather strange and confusing recursions and some self-reference.

Recall the $s_{mn}$ theorem, which states that there is a total computable function $S$ of two variables $m,n$ such that for every $e\in N$, we have $\left[e\right](m,n)=\left[S\right(e,m\left)\right]\left(n\right)$: that is, there is a total computable way $S$ of currying computable functions. (Strictly speaking, our Turing machines only take one argument. Therefore we should use a computable pairing scheme such as Cantor's pairing function, so that actually $\left[e\right](m,n)$ should be interpreted as $\left[e\right]\left(pair\right(m,n\left)\right)$.)

Then the function which takes the pair $(e,x)$ and outputs the value of $\left[h\right(S(e,e)\left)\right]\left(x\right)$ is computable, so it has a description number $a$, say. ^[5]

Now we claim that $S(a,a)$ is the $n$ we seek. ^[6] Indeed, for any $x$, $\left[n\right]\left(x\right)=\left[S\right(a,a\left)\right]\left(x\right)$ by definition of $n$; this is $\left[a\right](a,x)$ by the $s_{mn}$ theorem; this is $\left[h\right(S(a,a)\left)\right]\left(x\right)$ by definition of $\left[a\right]$; and that is $\left[h\right(n\left)\right]\left(x\right)$ by definition of $n$.

Therefore $\left[n\right]\left(x\right)=\left[h\right(n\left)\right]\left(x\right)$, so we have found our fixed point.

x = 0

x = 1
print(x)

x = 1
x = 0
print(x)

eval("print(r1)", 5)  # does nothing other than print the number 5
eval("print(y)", 5)  # throws an error because `y` is not defined when it comes to printing it
eval("print(6)", 5)  # prints 6, ignoring the fact that the variable `r1` is equal to `5` in the sub-instance

eval("r1 = e; h(eval(r1, str_as_int(r1)))", x)

eval("r1 = e; x = 0; eval(r1, str_as_int(r1))", x)

eval("eval(\"r1 = e; x = 0; eval(r1, str_as_int(r1))\", x)", str_to_int("eval(\"r1 = e; x = 0; eval(r1, str_as_int(r1))\", x)"))

Deducing Rice's theorem from the fixed point theorem

Finally, Rice's theorem follows quickly: suppose we could decide in general whether $Graph\left(n\right)\in A$ or not, and label by $\iota$ the computable function which decides this (that is, whose value is $1$ if $Graph\left(n\right)\in A$, and $0$ otherwise).

Since $A$ is nonempty and proper, there are natural numbers $a$ and $b$ such that $Graph\left(a\right)\in A$ but $Graph\left(b\right)\notin A$. Define the computable function $g$ which takes $n$ and outputs $a$ if $\iota \left(n\right)=0$, and $b$ otherwise. (That is, it flips its input: if its input had the property of $A$, the function $g$ outputs $b$ whose graph is not in $A$, and vice versa. Informally, it is the program-transformer that reads in a program, determines whether the program computes a function in $A$ or not, and transforms the program into a specific canonical example of something which has the opposite $A$-ness status.)

By the fixed-point theorem, we can find $n$ such that $Graph\left(n\right)=Graph\left(g\right(n\left)\right)$.

But now we can ask whether $Graph\left(n\right)$ is in $A$ (and therefore whether $Graph\left(g\right(n\left)\right)$ is in $A$).

• If it is in $A$, then $g\left(n\right)=b$ and so $Graph\left(g\right(n\left)\right)=Graph\left(b\right)$ which is not in $A$.
• If it is not in $A$, then $g\left(n\right)=a$ and so $Graph\left(g\right(n\left)\right)=Graph\left(a\right)$ is in $A$.

We have obtained contradictions in both cases (namely that $Graph\left(g\right(n\left)\right)$ is both in $A$ and not in $A$), so it must be the case that $\iota$ does not exist after all.

1. ^{^︎}

   That is, it is not the entire set.

2. ^{^︎}

   Well, very nearly; see the next note.

3. ^{^︎}

   It's only "very nearly" constructive. It would be actually constructive if we knew in advance a specific example of a program whose function is in $A$, and a program whose function is in $B$. The proof here assumes the existence of a program of each type, but ironically the theorem itself guarantees that there is no fully-general way to find such programs.

4. ^{^︎}

   And, moreover, we can actually find such an $n$.

5. ^{^︎}

   This is the first strange part: we are treating $e$ both as a description number, and as an input to \(E\), when we consider $S(e,e)$.

6. ^{^︎}

   This is the second strange part, for the same reason as $S(e,e)$ was the first; but this one is even worse, because the definition of $a$ already involves a weird recursion and we've just added another one on top.

7. ^{^︎}

   This is a standard, agreed-upon method of turning a number between $0$ and $128$ into a character.

8. ^{^︎}

   The string is standing in place of $m$, but we have just skipped the intermediate step of "unpack the integer into a string" and gone straight to assuming it is a string.