Automaton?
Both have a finite-state machine as a central component, both have
additional storage.
3. What are the types of Turing machines?
(a) Deterministic Turing machine.
(b) Non-deterministic Turing machine.
4. Define a Turing machine.
A Turing machine is a 7-Tuple
( , , , , , # , )
Q
q
F
Σ Γ δ 0
where
Q is a set of states
Σ is a finite set of sym bols, “Input alpha bet”
Γ is a finite set of sym bols, “Tape alpha bet”
δ is the par tial tran si tion func tion
# ∈T is a sym bol called ‘blank’
q Q
0 ∈ is the ini tial state
F Q
⊆ is a set of final states
5. Define the Transition Function for Turing Machine (TM)
δ :
{ , }
Q
Q
L R
× → × ×
Γ
Γ
is the tran si tion func tion.
When a machine is in a given state (Q) and reads a given symbol (Γ)
from the tape, it replaces the symbol on the tape with some other symbol
(Γ), goes to some other state (Q), and moves the tape head one square
left (L) or right (R).
6. State the requirements of an instantaneous description or configuration
of a TM.
TM requires:
(a) the state the TM is in
(b) the contents of the tape
(c) the position of the tape head on the tape.
7. How is move of a Turing machine expressed?
It is expressed as a pair of instantaneous descriptions, separated by a
symbol |–.
8. What do you understand by “programming” a Turing machine?
Creating a list:
(current state, symbol read, symbol written, direction, next state) is
called ‘Programming’ a Turing machine.
9. What are the reasons for a TM not accepting its input?
(a) The TM could halt in a nonfinal state.
(b) The TM could never stop i.e., it enters an “infinite loop”.
10. How is a Turing machine used as a Transducer?
Turing Machines
207