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?

  • 1
    $\begingroup$ Pretty much exactly like your informal argument. Just do an induction on the length of programs. There's a three-line proof on pp. 14–15 of Soare's book Recursively Enumerable Sets and Degrees. This result is typically known as the "padding lemma". Note that it's actually stronger than your statement of it: for each index $x$ we can effectively find an infinite set $A_x$ of indices for the partial recursive function $\varphi_x$. $\endgroup$ – Benedict Eastaugh Mar 29 '17 at 14:51
  • $\begingroup$ @BenedictEastaugh The proof in Soare's book is by turing program. Could you give a proof by URM-program? $\endgroup$ – Marvin Mar 29 '17 at 15:33
  • $\begingroup$ I've now provided one, but it really doesn't do anything except spell out your informal proof in the way I suggested. $\endgroup$ – Benedict Eastaugh Mar 29 '17 at 19:36

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.


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.

  • $\begingroup$ a typo, should change $P$ to $P^n$ in the definition. $\endgroup$ – Marvin Mar 29 '17 at 21:16
  • $\begingroup$ What does $\frown$ mean here? What does $J(\ldots)$ mean? $\endgroup$ – Henning Makholm Mar 29 '17 at 23:23
  • $\begingroup$ @HenningMakholm $\frown$ is just concatenation; a program is a list of instructions. $J(m,n,q)$ is a jump instruction: if the values in registers $m$ and $n$ are the same, then execute the $q$th instruction of the program; otherwise proceed to the next instruction. Since Marvin said he wanted a proof using unlimited register machines as in Cutland's book, the notation is Cutland's. $\endgroup$ – Benedict Eastaugh Mar 29 '17 at 23:45
  • 1
    $\begingroup$ There's a small but important mistake here: you don't have $y\in A_e\iff \varphi_y=\varphi_e$, merely $y\in A_e\implies \varphi_y=\varphi_e$. For each $e$, the set of $y$ such that $\varphi_y=\varphi_e$ is incomputable. $\endgroup$ – Noah Schweber Apr 24 '17 at 2:46
  • $\begingroup$ Yes, of course—thanks for pointing this out, I've fixed it now. $\endgroup$ – Benedict Eastaugh Feb 25 '18 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.