HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is there any recursive function f whose code is unique?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
uniquewhoseanyfunctionrecursivecodethere

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#111890, answer score: 6

Revisions (0)

No revisions yet.