3
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – A. Othmane Jul 17 at 0:53
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – A. Othmane Jul 22 at 0:27
  • $\begingroup$ @A.Othmane Correct. $\endgroup$ – Noah Schweber Jul 22 at 0:44

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.