Here\'s the statement: Take a set of finite inputs from some alphabet. If for an
ID: 647698 • Letter: H
Question
Here's the statement:
Take a set of finite inputs from some alphabet. If for any two turing machines:
All inputs in the set produce the same output for both machines
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?
Explanation / Answer
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:N?{0}?N,n?n2
g:N?{0}?N,n?2n
and two turing machines Mf,Mg which compute f and g, respectively. Without loss of generality, we may exclude 0 because I think it might require special handling in Mg, 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:
nf(n)g(n):::1,1,2,2,4,4,3,9,8,4,16,16,5,25,32,.........
We see that for an input set I={2,4}, then Mf and Mg compute the same value for all input values, and since ?n?I:n>1, they would also need all of their transitions. Still for any input value n?1,n?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 2n 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 n2 is similar, except that for doubling the output n times, you add n to n exactly n times.