Is there any recursive function f whose code is unique?

Question

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, <x_0,x_1,...,x_{m-1} > )$. 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.

Answer 1

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$.

• A. Othmane: 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/…

Answer 2

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.

• A. Othmane: 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
• Noah Schweber: @A.Othmane Correct.