Modification Of Turing Machines

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.”

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”.

Semi-infinite tape/Offline/Multitape/ND Turing Machines

1. A Turing machine may have a “semi-infinite tape”, the nonblank input is at the extreme left end of the tape. Turing machines with semi-infinite tape are equivalent to Standard Turing machines.
2. An “Offline Turing Machine” has two tapes. One tape is read-only and contains the input, the other is read-write and is initially blank. Offline Turing machines are equivalent to Standard Turing machines”.
3. A “Multi-tape Turing Machine” has a finite number of tapes, each with its own independently controlled tape head. “Multi-tape Turing Machines are equivalent to Standard Turing Machines”.
4. A “Nondeterministic Turing Machine” is one in which the DFA controlling the tape is replaced with an NFA.

“Nondeterministic Turing machines are equivalent to Standard Turing Machines.”

Multidimensional/Two-state Turing Machine: A “Multidimensional Turing Machine” has a Multidimensional “tape”, for example, a two-dimensional Turing Machine would read and write on an infinite plane divided into squares, like a checkerboard. Possible directions that the tape head could move might be labelled {N, E, S,W}. A three-dimensional Turing machine might have possible directions

{N, E, S,W,V, D} and so on.

“Multidimensional Turing Machines are equivalent to Standard Turing Machines”.

A “Binary Turing Machine” is one whose tape alphabet consists of exactly two symbols.

Binary Turing machines are equivalent to Standard Turing Machines. A “Two-state Turing Machine” is one that has only two states. Two-state Turing machines are equivalent to Standard Turing Machines.