Types of TM: Deterministic TM, non-deterministic TM
Transition function of TM: δ :
{ , }
Q
Q
L R
× → × ×
Γ
Γ
Configuration of TM: Requires
(i) state of TM
(ii) contents of the tape
(iii) position of the tape head on the tape.
Move of a TM: Pair of instantaneous descriptions, separated by |–.
Programming a TM: Creating current state, symbol read, symbol written,
direction, next state.
Transducer: TM is used as a Tranducer by treating the entire nonblank
portion of the initial tape as input, and treating the entire nonblank
portion of the tape when the machine halts as output.
N-Track Turing machine: One in whch each square of the tape holds an
ordered n-tuple of symbols from the tape alphabet.
Semi-infinite tape TM: TM having an semi-infinite tape, with the non-blank
input at the extreme left of the tape.
Offline TM: TM having two tapes, one tape is read-only and has the input,
the other is read-write and is initially blank.
Multi-tape TM: TM having finite number of tapes, each having its own
independently controlled tape head.
Standard TM: Multi-tape TMs are called so.
Binary TM: One whose tape alphabet consists of exactly two symbols.
Turing Thesis (Weak form): TM can compute anything that can be.
computed by a general-purpose digital computer.
Turing Thesis (Strong Form): TM can compute anything that can be
computed.
Recursively enumerable (R.E.): Language is R.E. if there exists a TM that
accepts every string of the language and does not accept strings that are
not in the language.
REVIEW QUESTIONS
1. What is a Turing machine?
2. What are the types of Turing machines?
3. Give the definition of a Turing machine.
4. Define the term ‘Transition function’ of a TM.
5. Define the term ‘Instantaneous description’ of a TM.
6. Define the term ‘move’ in a TM.
7. What are the requirements of the ‘configuration’ of a TM?
8. How will you program a Turing machine?
9. Explain “Turing machine as acceptors”.
204
Theory of Automata, Formal Languages and Computation
Transition function of TM: δ :
{ , }
Q
Q
L R
× → × ×
Γ
Γ
Configuration of TM: Requires
(i) state of TM
(ii) contents of the tape
(iii) position of the tape head on the tape.
Move of a TM: Pair of instantaneous descriptions, separated by |–.
Programming a TM: Creating current state, symbol read, symbol written,
direction, next state.
Transducer: TM is used as a Tranducer by treating the entire nonblank
portion of the initial tape as input, and treating the entire nonblank
portion of the tape when the machine halts as output.
N-Track Turing machine: One in whch each square of the tape holds an
ordered n-tuple of symbols from the tape alphabet.
Semi-infinite tape TM: TM having an semi-infinite tape, with the non-blank
input at the extreme left of the tape.
Offline TM: TM having two tapes, one tape is read-only and has the input,
the other is read-write and is initially blank.
Multi-tape TM: TM having finite number of tapes, each having its own
independently controlled tape head.
Standard TM: Multi-tape TMs are called so.
Binary TM: One whose tape alphabet consists of exactly two symbols.
Turing Thesis (Weak form): TM can compute anything that can be.
computed by a general-purpose digital computer.
Turing Thesis (Strong Form): TM can compute anything that can be
computed.
Recursively enumerable (R.E.): Language is R.E. if there exists a TM that
accepts every string of the language and does not accept strings that are
not in the language.
REVIEW QUESTIONS
1. What is a Turing machine?
2. What are the types of Turing machines?
3. Give the definition of a Turing machine.
4. Define the term ‘Transition function’ of a TM.
5. Define the term ‘Instantaneous description’ of a TM.
6. Define the term ‘move’ in a TM.
7. What are the requirements of the ‘configuration’ of a TM?
8. How will you program a Turing machine?
9. Explain “Turing machine as acceptors”.
204
Theory of Automata, Formal Languages and Computation