Is 'the simplest Turing machine for recursive functions' turing-computable?

Question

It's a well-known fact that all recursive functions are Turing-computable, and we can give all Turing machines a unique code number, therefore we can give all recursive functions a unique code number. I'm curious about whether there is any Turing machine that computes the 'simplest(having the least number of states)' code number of Turing machine for a given code number for recursive function. If the code number for addition is 789, then for the input 789, our machine gives us the code number of the simplest Turing machine that computes addition. Does such machine exist?

Answer 1

No, there is not. Note that using such a machine you would be able to tell when two numbers are codes for the same function, which would lead to a contradiction with Rice's Theorem.

• Rice's theorem is usually phrased in terms of sets of indices of c.e. sets rather than sets of indices of partial computable functions, but it holds in both settings via essentially the same proof. If you've only seen the sets-version before, it's a good exercise to prove the following: if $X$ is computable and for all $a,b$ with $\varphi_a\simeq\varphi_b$ we have $a\in X\iff b\in X$, then either $X=\emptyset$ or $X=\mathbb{N}$. To see how this relates to your question, suppose $i$ were the "least index" function and consider for example $i^{-1}(\{17\})$.

Interestingly, this depends on a subtle feature of the way we code computable functions by numbers. There is a partial computable binary function $f(x,y)$ such that for every partial computable unary function $h(x)$ there is exactly one $n$ such that $f(-,n)\simeq h(-)$. While Turing-complete in a loose sense, this $f$ is much less powerful than the "canonical" function $(x,y)\mapsto\varphi_y(x)$ in a precise sense: the (unique) "translation map" $t$ satisfying $\varphi_e(-)\simeq f(-,t(e))$ is not computable, whereas there is a computable translator in the other direction (that is, a computable $s$ satisfying $f(-,e)\simeq \varphi_{s(e)}(-)$). See here for more details.

Answer 2

Noah Schweber has given a valid answer. For a direct proof, consider the following:

Suppose we had a function $code$ which outputed the simplest code for a given recursive function. In particular, suppose we have two recursive functions $k, j$ such that for all $x$, $k(x)$ simplifies if and only if $j(x)$ simplifies, and whenever $k(x)$ and $j(x)$ simplify, we have $k(x) = j(x)$. Then $code(j) = code(k)$.

Given a recursive function $f$, define a new recursive function $g$ which first computes $f(0)$, then outputs $0$. So $g(x)$ simplifies to a value if and only if $f(0)$ terminates, and $g(x)$ will always simplify to $0$ if it simplifies to anything.

Now define the recursive function $h$ by $h(x) = 0$.

Then we see that $code(h) = code(g)$ if and only if $g(x)$ simplifies for all $x$, if and only if $f(0)$ simplifies.

So we would be able to solve the halting problem for recursive functions.