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