patternMinor
Is there any recursive function f whose code is unique?
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.
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$.
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.