How to prove that every computable function has infinitely many indices? [cutland 4.2.3]

1.6k Views Asked by At

Intuitively, it's obvious. For instance, a unary URM-comuptable function $f$ has an index $a$, where $a=\gamma(P)$. $P$ is the program computing $f$. Informally, I could put some instruction after the final configuration. If the final configuration is that $1$ is in $R_1$, then add $T(1,2)$ and $T(2,1)$. So the final configuration is that $1$ is sitll in $R_1$. There is infinitely many programs like above. Hence, infinitely many indices.

But how to prove formally?

2

There are 2 best solutions below

1
On BEST ANSWER

If you have proved Rice's theorem, then it provides a slick nonconstructive shortcut:

Assume, to the contrary, that there are only finitely many programs that compute $f$. Then we can decide the property "this Turing machine computes $f$" simply by constructing an URM program that simulates the input machine (which is well known to be a computable task) and comparing it to each of those finitely many possibilities in turn. But Rice tells us that this is not possible to decide that property.

5
On

Padding lemma. Let $e$ be an index of a partial recursive function $\varphi_e$. Then there is an infinite, recursive set of indexes $A_e$ such that for all $y$, if $y \in A_e$ then $\varphi_y = \varphi_e$.

Proof. Let $e$ be such an index. Then there is a program $P = (I_1, I_2, \dotsc, I_k)$ such that an unlimited register machine with program $P$ computes $\varphi_e$. We show by induction on the length of programs that for all $n \geq k$, there is a program $P^n$ with length $n$ that computes $\varphi_e$. The base case is given (i.e., by the assumption that $P$ computes $\varphi_e$). Let $n > k$. Our inductive hypothesis is that there is a program $P^n$ that computes $\varphi_e$. Define $P^{n+1} = P^n \frown (J(1,2,n+2))$. If the machine running program $P^{n+1}$ ever executes instruction $I_{n+1} = J(1,2,n+2)$, then it halts. But if the machine were running program $P^n$, it would have halted anyway (since $n+1$ is greater than the length of the program $P^n$). Conversely, if the machine would have halted running program $P^n$, then it also halts when running program $P^{n+1}$ (because it could only halt either by reaching the end of the instructions, in which case $P^{n+1}$ runs instruction $I_{n+1}$ and halts, or by jumping further than the length of the program, in which case $P^{n+1}$ halts too). So $P^n$ and $P^{n+1}$ compute the same partial recursive function, $\varphi_e$. Now we just set $A_e$ to be the set of all $x$ such that $x$ is the Gödel code of a program of the form just described. $A_e$ is infinite and consists only of programs which compute the partial recursive function $\varphi_e$. QED.

The same trick works with whatever model of computation you like, as long as it's equivalent to Turing computation. The particular padding instruction used in the proof above is also not particularly important: there are lots of ways to do the same thing.