1
$\begingroup$

Here's the statement:

Take a set of finite inputs from some alphabet. If for any two turing machines:

  1. All inputs in the set produce the same output for both machines
  2. In both machines, the following is true: every state transition (i.e. every row in the state table) occurs at least once for at least one of the inputs in the set before halting

Then both machines will produce the same output as each other for any input.

This is an informal statement, it probably needs a bit of refining. But for now the question is, is this true?

$\endgroup$
  • 1
    $\begingroup$ @usul Could you say what you understand by condition 2? Because if that's what you were referring to by "that both do the same thing", I'm not sure you're understanding exactly what I mean. $\endgroup$ – Ben Aaronson Mar 6 '15 at 14:20
  • $\begingroup$ Ah, ok, I misread that condition! My bad! $\endgroup$ – usul Mar 6 '15 at 14:22
  • $\begingroup$ @usul If you have any suggestion of a way to clarify it, let me know $\endgroup$ – Ben Aaronson Mar 6 '15 at 14:22
  • $\begingroup$ I think it's fine, just my fault for misreading. I'll delete my earlier comments. $\endgroup$ – usul Mar 6 '15 at 14:24
3
$\begingroup$

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&:& &1,& &2,& &3,& &4,& &5,& ... \\ f(n)&:& &1,& &\color{green}{4},& &9,& &\color{green}{16},& &25,& ... \\ g(n)&:& &2,& &\color{green}{4},& &8,& &\color{green}{16},& &32,& ... \\ \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 > 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 <input>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.

$\endgroup$
  • $\begingroup$ Maybe I'm veering off into madness here, but what if we allow multiple halting states and define the "output" as which halting state it ends up in, rather than what's written on the tape when it halts? (Obviously this narrows the range of functions which can be represented this way, based on the number of states) $\endgroup$ – Ben Aaronson Mar 6 '15 at 16:12
  • $\begingroup$ I have written an example of such a turing machine, check out the edit to my answer. About your second question, I think it would be the same answer. In my example code, the halting state is always reached from the transition from state 3 at input 0, and I suggest this would be equivalently the case for $n^2$, if I understand your question correctly. $\endgroup$ – Stefan Lutz Mar 6 '15 at 16:51
  • $\begingroup$ Thanks for going to that trouble! And for the followup, I mean a system where the function being computed is from your input to a finite number of outputs, each of which is represented by a different halting state. Instead of writing the output to the tape, the machine gives output by arriving at the right state. For example, a function from some input to a boolean answer would have a 'true' halting state and 'false' halting state. Whatever was left on the tape once it reached one of these would be disregarded. $\endgroup$ – Ben Aaronson Mar 6 '15 at 17:13
  • $\begingroup$ I think the second statement is true, but I'm not quite sure how to prove it. This reminds me of the reduction of finite automata to their minimal variants. Maybe open up a new question. $\endgroup$ – Stefan Lutz Mar 6 '15 at 17:32
  • $\begingroup$ I may do that. Thanks for all your input! $\endgroup$ – Ben Aaronson Mar 6 '15 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.