4.3.2 Semi-infi nite tape/Offline/Multitape/ND Turing Machines
(a) 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.
(b) 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”.
(c) 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”.
(d) 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.”
4.3.3 Mul ti di men sional/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 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.
4.4 CHURCH–TURING’S THESIS
Alan Turing defined Turing machines in an attempt to formalize the notion of
an “effective producer” which is usually called as ‘algorithm’ these days.
Simultaneously mathematicians were working independently on the same
problem.
Emil Post
→ Production Systems
Alonzo Church
→ Lambda Calculus
196
Theory of Automata, Formal Languages and Computation
(a) 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.
(b) 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”.
(c) 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”.
(d) 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.”
4.3.3 Mul ti di men sional/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 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.
4.4 CHURCH–TURING’S THESIS
Alan Turing defined Turing machines in an attempt to formalize the notion of
an “effective producer” which is usually called as ‘algorithm’ these days.
Simultaneously mathematicians were working independently on the same
problem.
Emil Post
→ Production Systems
Alonzo Church
→ Lambda Calculus
196
Theory of Automata, Formal Languages and Computation