Function that can be computed by two distinct Turing machines

78 Views Asked by At

Could there be a function $f$ such that, for distinct numbers $n$ and $m$, $n$ and $m$ both code Turing Machines that compute $f$?

The coding scheme of a Turing machine is $p_1^{k_1+1}p_2^{k_2+1}\dots p_m^{k_m+1}$, where ${k_i}$ is a number sequence corresponding to symbols of a command line. For example, the direction is $r$ (move to the right) and corresponds to $0$.

I think the answer is yes, for example, there exist two algorithms that correspond to the same task (i.e. they compute the same function), and each algorithm corresponds to a unique Turing machine and consequently to two distinct natural numbers. Is that correct?

1

There are 1 best solutions below

2
On

The answer is yes. Its not entirely clear to me what your formal defintion of TM is, but the idea is this: We can add "useless" moves to our TMs after they finish computing. For example, suppose we have a TM A that computes successor. Such a TM has an accept state. We create a different TM D which is entirely the same except that A's accept state is just a normal state b, and the TM has a new accept state c accessed only after b.

Alternatively, if you are using a formalism without accept states, say like Davis 1995, then just add another quadruple to the table that only moves to the right and can only be accessed after the original TM would have finished computing.

Then, it is clear that A, D compute the same function, but under the the encoding correspond to two different machines