Is there any recursive function f whose code is unique?

I am doing some reviewing for the term final on computability and found out this simple exercise. I am very fresh on theoretical computer science so if you do have an answer please make it simple.

The question is fairly simple: Is there any recursive function f whose code is unique? That is $$comp(p_1, ) \doteq comp(p_2,) \doteq f$$ implies $$p_1=p_2$$.

$$comp$$ is the universal recursive function. That is, the function that for every recursive function $$f: \mathbb{N}^m \rightarrow \mathbb{N}$$, exists a code $$p_f$$ such that $$f \doteq comp(p_f, )$$. And $$\doteq$$ designates equality in Kleene sense.

I found in my notes Rice's theorem in the following form.

Let $$k$$ be an arbitrary natural number and $$g: \mathbb{N} \rightarrow \mathbb{N}$$. If g satisfies the following conditions, the $$g$$ is not recursive.

1.Totality: For any $$p\in\mathbb{N}$$, the value $$g(p)$$ is defined and $$g(p)\in {0,1}$$

2.No constant: $$g$$ is not constant. There exists two natural numbers $$p_0,p_1\in\mathbb{N}$$ such that $$g(p_0)=0$$ and $$g(p_1)=1$$

3."Reflects equivalence of codes" If p,q are codes for the same recursive function $$\mathbb{N}^k \rightarrow \mathbb{N}$$ then $$g(p)=g(q)$$

I know the answer must be No there is not by property 3 but how can I formally write it.

No. The Padding Lemma states that there is a primitive recursive function $$\sf pad$$ such that, if $$n$$ is a code for $$f$$, then $${\sf pad}(n)$$ is another code for $$f$$ which is larger than $$n$$.

Therefore, if $$f$$ has a code, it has infinitely many.

The intuition is: if you have a TM $$M$$ computing $$f$$, you can modify the TM so that it starts with some useless steps (e.g. move right, then left), and then behaves as $$M$$. The modified TM has a few more states, and under the "usual encoding" it will have a larger code than $$M$$.

• I have read about the equivalence of recursive functions and Turing computable programs. I was wondering if Rice’s theorem can be used in some way like in this thread math.stackexchange.com/questions/2208553/… – A. Othmane Jul 17 '19 at 0:53

Rice's theorem is indeed applicable. Remember the intuitive meaning of Rice's theorem: any nontrivial property of partial computable functions either always holds, always fails, or is nonrecursive - in the sense that the set of natural numbers with that property is nonrecursive. This isn't how you've phrased it but it's a bit easier, in my opinion, to think in terms of properties: besides matching what we think about normally, they correspond to total functions (set $$g(x)=0$$ if the property fails for $$x$$ and $$g(x)=1$$ if the property holds for $$x$$) and this makes condition (1) trivial.

Now in our case, the property we care about is "is an index for $$f$$." It's easy to check that (2) and (3) hold for this property: some but not all natural numbers are indices for $$f$$ (note that this doesn't assume what you're trying to prove - you just need that $$f$$ has at least one index, and that there is more than one recursive function), and if $$a,b$$ are indices for the same partial recursive function $$h$$ then either $$h\cong f$$ in which case the property holds of both $$a$$ and $$b$$ or $$h\not\cong f$$ in which case the property fails for both $$a$$ and $$b$$.

So by Rice's Theorem, the set of naturals with this property - that is, the set of indices for $$f$$ is non-computable.

It's worth noting that Rice's theorem doesn't hold in all situations you might imagine! Specifically, we can whip up recursive numberings of partial recursive functions which don't satisfy the padding lemma; these are called Friedberg numberings, and see this paper of Kummer for a simple proof that they exist.

• Note that as an immediate consequence there is no effective way to translate from the usual numbering to a Friedberg numbering (it's a good exercise to make this precise and prove it). As a consequence you can think of a Friedberg numbering as a hilariously awful programming language F - in which every program $$\pi$$ you can write in your favorite non-stupid langauge has a corresponding program $$\hat{\pi}$$ in F, but you can't find it!

Basically, the existence of good numberings of partial recursive functions is something we should all be nontrivially happy about.

• Thank you. To sum up the answer, you defined g {p: p is code for f} which is non constant (there exists a code for f and code not for f ), is total in the sense it is defined for all codes (one can check if it is code for f or not), reflects equivalence of code by discussing cases. Then by Rice it is non recursive therefore g is infinite as a set – A. Othmane Jul 22 '19 at 0:27
• @A.Othmane Correct. – Noah Schweber Jul 22 '19 at 0:44