TM

17/09/2023 1
 Turing Machine
Consists of:-
• A Tape
Tape is infinite extending on either sides, divided into cells, each
cell capable of holding one symbol

• Head-
Associated with tape is read-write head that can travel left or right
on tape and read a single symbol on each move

17/09/2023 2
 Turing Machine
Consists of:-
• Tape Symbols-
Finite set of symbols, consists of lowercase letters, digits, usual
punctuation marks and the Blank B

• States-
Set of states in which the machine can reside

17/09/2023 3
 Turing Machine

A Turing machine is a mathematical model of computation that

defines an abstract machine[1] that manipulates symbols on a
strip of tape according to a table of rules
-Wikipedia

17/09/2023 4
 Turing Machine
• Turing Machine was invented by Alan Turing in 1936
• Accepts Recursive Enumerable Languages (generated by Type-
0 Grammar).

17/09/2023 5
 TM: Formal Definition
TM is denoted by 7 Tuple: M=(Q, ∑, ᴦ, δ, q0, B, F) where

• Q:Finite set of Internal states of the Control Unit

• ∑:Finite input alphabet

• ᴦ: Finite Set of Tape Symbols

• δ:Q X ᴦ ->Q X ᴦ X {L,R,N}: Transition function(TF)

• q0: Start state of Control Unit, q0 ∈ Q

• B : Blank Symbol

• F: Set of Final States/ Accept State, F ⊆ Q

• ∑ ⊆ ᴦ -{B}
17/09/2023 6
 δ Function
δ Function:-
• δ:Q X ᴦ ->Q X ᴦ X {L,R,N}: Transition function(TF)

If δ(q,X)=(p,Y,L)
• If present state is q and the next symbol on the tape is X
then the Turing Machine changes the state to p, replaces the
symbol X by symbol Y and moves the tape head one position
left.

If δ(q,X)=(p,Y,R)
• If present state is q and the next symbol on the tape is X
then the Turing Machine changes the state to p, replaces the
symbol X by symbol Y and moves the tape head one position
right.
17/09/2023 7
 TM Example 1 Transition Rules
Construct a TM to replace each occurrence of ‘a’ by ‘b’ for the
strings over ∑={a,b}

17/09/2023 8
 TM Example 1 Simulation

Construct a TM to replace each occurrence of ‘a’ by ‘b’ for the

strings over ∑={a,b}

17/09/2023 9
 TM Example 2 Transition Rules and Simulation

Design a TM to replace all occurrences of ‘111’ by ‘101’ over

∑={0,1}

17/09/2023 10
 TM Example 2 Transition Diagram ,Table

Design a TM to replace all occurrences of ‘111’ by ‘101’ over

∑={0,1}

17/09/2023 11
 TM Example 3
Design a TM accept the language containing substring “aba”
over ∑={a,b}

Logic-
During the process if TM discovers “aba” on the tape, it halts
and thereby accepts entire input string

M=(Q, ∑, ᴦ, δ, q0, B, F)

17/09/2023 12
 TM Example 3
Design a TM accept the language containing substring “aba”
over ∑={a,b}

δ(q0,a)=(q1,a,R)
δ(q0,b)=(q0,b,R) self loop
δ(q1,a)=(q1,a,R) self loop
δ(q1,b)=(q2,b,R)
δ(q2,b)=(q0,b,R) go back
δ(q2,a)=(qf,a,N)

17/09/2023 13
 TM Example 4 Transition Rules

Design a TM to replace all occurrences of ‘101’ by ‘011’ over

∑={0,1}

17/09/2023 14
Modifications of Turing Machines or Variants of Turing Machines

• Multi Tape Turing Machine

• Non-Deterministic Turing Machine

17/09/2023 15
 Multi Tape Turing Machine
• A Multitape Turing Machine-

17/09/2023 16
 Multi Tape Turing Machine
• It is a Turing Machine with several tapes , each has its own
tape heads
• It consists of a finite control with k tape heads and k tapes
(k>1)
• The move of this Turing machine depends on the present
state of the finite control and the symbol scanned by each of
the tape heads.

17/09/2023 17
 Multi Tape Turing Machine
• In each move, depending on the present state and the
symbols scanned by each of the tape heads , the machine can
– change state of the finite control
– print a new symbol on each of cells scanned by each of the
tape heads
– move each tape one cell left or one cell right
independently

17/09/2023 18
 Multi Tape Turing Machine

• The transition function of Multitape turing machine is :

• δ:Q X {ᴦ1 X ᴦ2 X ………. ᴦk} ->Q X {ᴦ1 X ᴦ2 X ………. ᴦk} X
{ {L,R,N} X {L,R,N} ……………{L,R,N} k times}

• δ(q1, (a1,a2,……ak) )=(p,(b1,b2,…….bk),(L,R,L,L……k times))

17/09/2023 19
 Multi Tape Turing Machine

• All Variants have same power, every multitape turing

machine has an equivalent single tape Turing machine

17/09/2023 20
 Multi Tape Turing Machine
• Let M be a k tape Turing Machine(k>1)

• Let us construct a single tape turing machine M1, which

simulates M as follows:-

17/09/2023 21
 Multi Tape Turing Machine

• M1 stores the information available on the k tapes of M on

its tape, using a symbol $ as delimiter

• To keep a track of the head positions for each tape of M, the

symbols below each of these tape heads are written with
underline on the tape of M1

17/09/2023 22
 Multi Tape Turing Machine

• M1 scans its tape starting from first $ up to (k+1)st $ for tape

symbols that are underlined to simulate the move by
replacing these symbols according to the move of M

• δ(q, (0,a,X) )=(p,(1,b,Y),(L,L,R))

• After this move the contents of the tape are-

17/09/2023 23
 Non-Deterministic Turing Machine

• Turing Machine which at any point while carrying out

computation , may proceed according to several possibilities
• For a tape symbol scanned, The machine has a finite number
of choices of next move
• The transition function defines mapping from
• Q X ᴦ to a finite subset of Q X ᴦ X {L,R,N}
• It accepts input, if some sequence of choices of moves lead
to an accepting state

17/09/2023 24
 Non-Deterministic Turing Machine

• All variants have the same power, thus Every Non-

Deterministic Turing Machine has an equivalent
deterministic Turing machine

17/09/2023 25
 Non-Deterministic Turing Machine

• For a Non-Deterministic Turing machine M,

• It is always possible to construct a turing machine M1,
which tries all possible sequences of computations or
branches of computations of M
• If M enters into an accept state on any of these branches,
M1 accepts otherwise continues to simulate Mwithout
termination
• Thus, M1 is accepting the same language as M

17/09/2023 26
 TM Example 5 Transition Rules

Design a TM which recognizes the language L=01*0 for ∑={0,1}

Lets take string 0110

17/09/2023 27
 TM Example 5
Design a TM which recognizes the language L=01*0 for ∑={0,1}

0 1 1 0 B
X Y Y X B

17/09/2023 28
 TM Example 5
Design a TM which recognizes the language L=0N1N for ∑={0,1}

17/09/2023 29
 TM Example 5
Design a TM which recognizes the language L=0N1N for ∑={0,1}

Algorithm-
• Change 0 to X
• Move Right to first “1”
• If None:Reject
• Change “1” to “y”
• Move LEFT to Leftmost “0”
• Repeat the above steps until no more “0”s
• Make sure no more “1”s remain

17/09/2023 30
 TM Example 5
Simulation for L=0N1N , String 00001111

Algorithm-
• Change 0 to X
• Move Right to first “1”
• If None:Reject
• Change “1” to “y”
• Move LEFT to Leftmost “0”
• Repeat the above steps until no more “0”s
• Make sure no more “1”s remain

17/09/2023 31
 TM Example 5
Design a TM which recognizes the language L=0N1N for ∑={0,1}

Algorithm-
Change 0 to X
Move Right to first “1”
If None:Reject
Change “1” to “y”
Move LEFT to Leftmost “0”
Repeat the above steps until no more “0”s
Make sure no more “1”s remain
17/09/2023 32