a 1. If the second symbol is 1, the machine should more into a final state. If the
second symbol is not a 1, the machine should not halt or it should halt in a
non-final state.
To construct such a machine, we include the five-tuples (q 0 , 0, q 1 , 0, R) and
(q 0 , 1, q 1 , 1, R) to read in the first symbol and put the Turing machine in state
q 1 .
Next, we include the five-tuples (q 1 , 0, q 2 , 0, R) and (q 1 , 1, q 3 , 1, R) to read
in the second symbol and either move to state q 2 if this symbol is a 0, or to state
q 3 if this symbol is a 1.
We do not want to recognize strings that have a 0 as their second bit, so q 2
should not be a final state. We want q 3 to be a final state. Therefore we can
include the 5-tuple (q 2 , 0, q 2 , 0, R). As we do not want to recognize the empty
string nor a string with one bit, we also include the 5-tuples (q 0 , B, q 2 , 0, R) and
(q 1 , B, q 2 , 0, R).
The Turing machine T consisting of seven 5-tuples given above will
terminate in the final state q 3 if and only if the bit string has at least two bits and
the second bit of the input string is a 1. If the bit string contains fewer than two
bits or if the second bit is not a 1, the machine will terminate in the non final
state q 2 .
4.3 MODIFICATION OF TURING MACHINES
Two automata are said to be equivalent if they accept the same language. Two
transducers are said to be equivalent if they compute the same function.
A class of automata e.g., Standard Turing machines is equivalent to
another class of automata e.g., nondeterministic Turing machines, if for each
transducer in one class, an equivalent transducer can be found in another class.
At each move of a Turing machine, the tape head may move either left or
right. We can augment this with a “Stay option”, i.e., we will add “don’t move”
to the set {L, R}.
“Turing machines with a stay option are equivalent to Standard
Turing Machines.”
4.3.1 N-Track Turing Machine
An N-track Turing Machine is one in which each square of the tape holds an
ordered n-tuple of symbols from the tape alphabet. This can be thought of as a
Turing machine with multiple tape heads, all of which move in lock-step
mode.
“N-Track Turing machines are equivalent to standard Turing
machines”.
Turing Machines
195
second symbol is not a 1, the machine should not halt or it should halt in a
non-final state.
To construct such a machine, we include the five-tuples (q 0 , 0, q 1 , 0, R) and
(q 0 , 1, q 1 , 1, R) to read in the first symbol and put the Turing machine in state
q 1 .
Next, we include the five-tuples (q 1 , 0, q 2 , 0, R) and (q 1 , 1, q 3 , 1, R) to read
in the second symbol and either move to state q 2 if this symbol is a 0, or to state
q 3 if this symbol is a 1.
We do not want to recognize strings that have a 0 as their second bit, so q 2
should not be a final state. We want q 3 to be a final state. Therefore we can
include the 5-tuple (q 2 , 0, q 2 , 0, R). As we do not want to recognize the empty
string nor a string with one bit, we also include the 5-tuples (q 0 , B, q 2 , 0, R) and
(q 1 , B, q 2 , 0, R).
The Turing machine T consisting of seven 5-tuples given above will
terminate in the final state q 3 if and only if the bit string has at least two bits and
the second bit of the input string is a 1. If the bit string contains fewer than two
bits or if the second bit is not a 1, the machine will terminate in the non final
state q 2 .
4.3 MODIFICATION OF TURING MACHINES
Two automata are said to be equivalent if they accept the same language. Two
transducers are said to be equivalent if they compute the same function.
A class of automata e.g., Standard Turing machines is equivalent to
another class of automata e.g., nondeterministic Turing machines, if for each
transducer in one class, an equivalent transducer can be found in another class.
At each move of a Turing machine, the tape head may move either left or
right. We can augment this with a “Stay option”, i.e., we will add “don’t move”
to the set {L, R}.
“Turing machines with a stay option are equivalent to Standard
Turing Machines.”
4.3.1 N-Track Turing Machine
An N-track Turing Machine is one in which each square of the tape holds an
ordered n-tuple of symbols from the tape alphabet. This can be thought of as a
Turing machine with multiple tape heads, all of which move in lock-step
mode.
“N-Track Turing machines are equivalent to standard Turing
machines”.
Turing Machines
195