Turing Machine:
• Turing Machine accepts the recursively enumerable language. It is more powerful than any
other automata such as FA, PDA, and LBA. It computes the partial recursive function. It can be
further divided into Deterministic Turing Machine(DTM) or Non-Deterministic Machine(NTM).
By default, Turing Machine is DTM, and the power of DTM and NTM are the same.
• This machine acts as a Recognizer or Acceptor and as an Enumerator.
• The machine is said to be as acceptor which accepts or recognizes the strings of a
recursively enumerable language (L) over the input alphabet(∑ ) and the machine is said to be
as enumerator which enumerates the string of recursively enumerable language over the input
alphabet ∑.
The restricted Turing machines can be of the following types :
• Halting Turing Machine : A Turing Machine is said to be a halting Turing machine if it
always halts for every input string. It can accept the recursive language and is less powerful
than Turing machine.
• Linear Bounded Automata : It behaves as a Turing machine but the storage space of tape
is restricted only to the length of the input string. It is less powerful than a Turing machine but
more powerful than push down automata.
• Unidirectional Turing Machine : The head of this type of turing machine can move only in
one direction. It can accept the only regular language. It has the same power as finite
automata but less powerful than push down automata.
• Read Only Turing Machine : It is equivalent to finite automata. It contains a read head
only which doesn’t have written capability. It accepts only regular languages.
• Read Only-Unidirectional Turing Machine : It is similar to finite automata. It contains a
read-only head and can move only in one direction. It accepts a regular language.
Variants or Modifications or Types of Turing Machine:
1. Multiple track Turing Machine:
• A k-track Turing machine (for some k>0) has k-tracks and one R/W head that reads
and writes all of them one by one.
• A k-track Turing Machine can be simulated by a single-track Turing machine.
2. Two-way infinite Tape Turing Machine:
• Infinite tape of two-way infinite tape Turing machine is unbounded in both directions
left and right.
• Two-way infinite tape Turing machine can be simulated by one-way infinite Turing
machine (standard Turing machine).
3. Multi-tape Turing Machine:
• It has multiple tapes and is controlled by a single head.
• The Multi-tape Turing machine is different from k-track Turing machine but
expressive power is the same.
• Multi-tape Turing machine can be simulated by single-tape Turing machine.
4. Multi-head Turing Machine:
• A multi-head Turing machine contains two or more heads to read the symbols on the
same tape.
• In one step all the heads sense the scanned symbols and move or write
independently.
• Multi-head Turing machine can be simulated by a single head Turing machine.
5. Multi-dimensional Tape Turing Machine:
• It has multi-dimensional tape where the head can move in any direction that is left,
right, up or down.
• Multi dimensional tape Turing machine can be simulated by one-dimensional Turing
machine.
6. Off-line Turing Machine:
An off-line Turing machine has two tapes:
• One tape is read only and holds the input string.
• Second tape is read-write tape which is initially blank.
7. Non-deterministic Turing Machine:
• A non-deterministic Turing machine has a single, one-way infinite tape.
• For a given state and input symbol has at least one choice to move (finite number of
choices for the next move), each choice has several choices of the path that it might
follow for a given input string.
• A non-deterministic Turing machine is equivalent to the deterministic Turing
machine.
Hint: Write 7-tuple for every variant to get good marks.
Unrestricted Grammar
In automaton, Unrestricted Grammar or Phrase Structure Grammar is the most general in the Chomsky Hierarchy of
classification. This is type0 grammar, generally used to generate Recursively Enumerable languages. It is called
unrestricted because no other restriction is made on this except each of their left hand sides being non-empty. The left
hand sides of the rules can contain terminal and non-terminal, but the condition is at least one of them must be non-
terminal.
A Turning Machine can simulate Unrestricted Grammar and Unrestricted Grammar can simulate Turning
Machine configurations. It can always be found for the language recognized or generated by any Turning Machine.
Formal Definition
The unrestricted grammar is 4 tuple -
G = (N,Σ,P,S)
N - A finite set of non-terminal symbols or variables,
Σ - It is a set of terminal symbols or the alphabet of the language being described, where N ∩ Σ = φ,
P - It is a finite set of "productions" or "rules",
S - It is a start variable or non-terminal symbol.
If, α and β are two strings over the alphabet N ∪ Σ. Then, the rules or productions are of the form α → β. The
start variable S appears on the left side of the rule.
