Is the following statement about turing machines true?
This is an interesting statement, but it is not true. I'll give a proof sketch and leave the construction of the actual machines to you (read as: I am too lazy :) ). For example, take two functions

$f : \mathbb{N} \setminus \{0\} \to \mathbb{N}, n \mapsto n^2$

$g : \mathbb{N}\setminus \{0\} \to \mathbb{N}, n \mapsto 2^n$

and two turing machines $M_f, M_g$ which compute $f$ and $g$, respectively. Without loss of generality, we may exclude $0$ because I think it might require special handling in $M_g$, but this depends on the actual construction of the turing machine - it does not matter this way.

It is safe to assume that minimal turing machines for $f$ and $g$ would need each of its transitions for any value bigger than $1$ since they both have to implement some kind of looping scheme. This comes from the fact that $f$ and $g$ can be defined primitive-recursively, where $0$ and/or $1$ are the recursion base cases (depending on your exact definition). Now if we look at the values of these two functions:

$\begin{align}
n&amp;:&amp; &amp;1,&amp; &amp;2,&amp; &amp;3,&amp; &amp;4,&amp; &amp;5,&amp; ... \\
f(n)&amp;:&amp; &amp;1,&amp; &amp;\color{green}{4},&amp; &amp;9,&amp; &amp;\color{green}{16},&amp; &amp;25,&amp; ... \\
g(n)&amp;:&amp; &amp;2,&amp; &amp;\color{green}{4},&amp; &amp;8,&amp; &amp;\color{green}{16},&amp; &amp;32,&amp; ... \\
\end{align}$

We see that for an input set $I = \{ 2, 4 \}$, then $M_f$ and $M_g$ compute the same value for all input values, and since $\forall n \in I : n &gt; 1$, they would also need all of their transitions. Still for any input value $n \geq 1, n \notin I$, they would differ.

To generalize: Take any two sequences of numbers which are recursively defined and computable and also equal in at least two places, then the statement does not hold.



I overcame my laziness and did one turing machine for the calculation of $2^n$ in unary. The code can be executed on this turing machine simulator to check that for inputs $11$ and $1111$, every state transition is required.

; Compute 2^n in unary
; First go to the end of the input string and write a single 1.
; The tape content is then &lt;input&gt;01
 0 1 1 r 0 ; Move right until we are at the end of the input string.
0 _ 0 r 1 ; Write 0 separator
1 _ 1 l 2 ; Write an initial 1, since this is the value of 2^0.

; Then rewind to the beginning
2 1 1 l 2 ; Keep moving left without altering 1s
2 0 0 l 2 ; Keep moving left without altering 0s
2 _ _ r 3 ; We move back to the start.

; Now we double the string after the separating zero until
; there are no more 1s in the beginning (= decrement counter until 0)
3 1 _ r 4 ; Remove the first 1, this is equal to decrementing the counter
3 0 _ r halt ; if there are no more 1s, we are finished.
4 1 1 r 4 
4 0 0 r 5 ; Move right till the separator is found
5 1 1 r 5 ; Move to the end of the result string
5 _ _ l 6
6 1 _ r 7 ; And replace the last 1 with a blank, the initial position marker.
7 _ 1 l 8

; Now comes the actual doubling
8 1 1 l 8 ; Move left until the blank marker is found
8 _ 1 l 9 ; Move left until the blank marker is found
9 1 _ r 10 ; Shift the blank marker to the left
10 1 1 r 10 ; Move to the end of the string...
10 _ 1 l 8 ; ... and write a 1.
9 0 0 l 11 ; Once we hit 0, we are finished doubling

; And again rewind to the beginning
11 1 1 l 11 ; Keep moving left without altering 1s
11 _ _ r 3 ; We move back to the start.


The computation of $n^2$ is similar, except that for doubling the output $n$ times, you add $n$ to $n$ exactly $n$ times.