UNIT 5 : TURING MACHINE (TM)

❑ Definition, Design of TM as generator, decider and acceptor

❑ Variants of TM: Multitrack, Multitape, Universal TM

❑ Applications

❑ Power and Limitations of TMs.

TCS : UNIT 5 1
TCS : UNIT 5 2
 TURING MACHINE (TM)
Turing Machine was invented by Alan Turing in 1936 and it is used to accept Recursive Enumerable
Languages (generated by Type-0 Grammar).
A turing machine consists of a tape of infinite length on which read and writes operation
can be performed. The tape consists of infinite cells on which each cell either contains input symbol
or a special symbol called blank. It also consists of a head pointer which points to cell currently
being read and it can move in both directions.

TCS : UNIT 5 3
 TURING MACHINE (TM)
❖ A TM is expressed as a 7-tuple (Q, T, B, ∑, δ, q0, F) where:

➢Q is the set of states

➢∑ is the set of input symbols
➢ T is the tape alphabet (symbols which can be written on Tape)
➢ q0 is the initial state
➢B is blank symbol (every cell is filled with B except input alphabet initially)
➢F is the set of final states
➢δ is a transition function which maps Q × T → Q × T × {L,R}.
Depending on its present state and present tape alphabet (pointed by head pointer), it
will move to new state, change the tape symbol (may or may not) and move head pointer to
either left or right.

TCS : UNIT 5 4
 ASSIGNMENT 5: Q1
Example : Construct Turing Machine for language {an bn | n ≥ 1}
OR
Construct Turing Machine for language {0n 1n | n > 0}
Soln: language = L = {an bn | n > 0}
δ: Q×T → Q × T × {L,R}

B a a a b b b B
R/W
FC

B X a a b b b B
R/W
FC
B X a a Y b b B

R/W
TCS : UNIT 5 5
FC
 Language = {an bn | n > 0}
δ: Q×T → Q × T × {L,R}

B X X a Y b b B

R/W
FC

B X X a Y Y b B

R/W
FC

B X X X Y Y Y B

R/W
FC

TCS : UNIT 5 6
 Q/T a b X Y B

-> q0 (q1,X,R) -- -- (q3,Y,R) --

q1 (q1,a,R) (q2,Y,L) -- (q1,Y,R) --

q2 (q2,a,L) -- (q0,X,R) (q2,Y,L) --

q3 -- -- -- (q3,Y,R) (q4,B,L)

q4 -- -- -- -- --

TCS : UNIT 5 7
Example : Construct Turing Machine for language {an bn cn | n ≥ 1}
Soln: language = L = {an bn cn | n ≥ 1}
δ: Q×T → Q × T × {L,R}
B a a b b c c B

TCS : UNIT 5 8
 Q/T a b c X Y Z B

-> q0 (q1,X,R) -- -- (q4,Y,R) -- --

q1 (q1,a,R) (q2,Y,R) -- -- (q1,Y,R) -- --

q2 -- (q2,b,R) (q3,Z,L) -- -- (q2,Z,R) --

q3 (q3,a,L) (q3,b,L) -- (q0,X,R) (q3,Y,L) (q3,Z,L) --

q4 -- -- -- -- (q4,Y,R) (q4,Z,R) (q5,B,L)

q5 -- -- -- -- -- -- --

TCS : UNIT 5 9
Example : Construct Turing Machine to obtain one’s complement

OR
Q/T 0 1 B

-> q0 (q0,1,R) (q0,0,R) (q1,B,L)

q1 (q1,0,L) (q1,1,L) (q2,B,R)

q2 -- -- --
TCS : UNIT 5 10
 OR
Approach:
1.Scanning input string from left to right
2.Converting 1’s into 0’s
3.Converting 0’s into 1’s
4.Stop when you reach the end of the string (when
BLANK is encountered)
States:
•q0: Initial state
•qH: Final state
Symbols:
•0, 1: Binary digits
•B: Blank symbol Turing Machine to obtain one’s complement
•R, L: Right and left movements
Steps:
•Step-1. Convert all 0’s into 1’s and all 1’s into 0’s and if
B is found go to right.
•Step-2. Stop the machine.

TCS : UNIT 5 11
 Example : Construct Turing Machine to obtain two’s complement
ASSIGNMENT 5: Q2

2’s complement of a binary number is 1 added to the 1’s complement of the binary number.

Approach:
1.Start from the end of the input string.
2.Pass all consecutive ‘0’s.
3.When you encounter the first ‘1’, do nothing.
4.After that, replace ‘1’ with ‘0’ and ‘0’ with ‘1’.
5.Stop when you reach the beginning of the
string.

Writing transition function is mandatory for

all TM design
TCS : UNIT 5 12
Steps:
•In state q0, move right until you encounter a BLANK symbol. Then, transition to state q1 and go to left.
•In state q1, continue moving left until you encounter the first ‘1’. Transition to state q2.
•In state q1, if BLANK symbol is encountered, then transition to state qH.
•In state q2, replace ‘1’ with ‘0’ and ‘0’ with ‘1’.
•If BLANK symbol is encountered, then transition to state qH.
•In state qH, halt the machine.

Explanation for Understanding:

•Using state ‘q0’ we reach the end of the string.
•When BLANK is reached, move towards the left.
•Using state ‘q1’ we pass all 0’s and move left till first ‘1’ is found.
•If before finding ‘1’ we encounter BLANK, it implies the number is 0 i.e. it contains no 1.
•Hence its 2s complement is 0 itself. So no need to change any symbols and just halt the machine.
•If ‘1’ is encountered, skip that ‘1’ and move left.
•Using state ‘q2’ we complement the each digit and move left.
•When BLANK is reached, move towards the right and reach the final state qH.

TCS : UNIT 5 13
Example : Construct a Turing Machine for checking well formedness of parenthesis

Steps:
1. Move to right till you get first closing bracket i.e. ) {
ignore all opening brackets in the path , don’t change
them}
2. Change first closing bracket to X and move to left till you
get opening bracket ( { ignore X in the path if any}
3. Mark the opening bracket as X and move to left to
search for next closing bracket , continue till all opening
and closing brackets are marked X
4. Once all input cells are marked X at state q0 after self
loop of X if blank cell B comes, it indicates that
parenthesis are well formed.

REMAINING NEUMERICLE TYPES

SOLVED IN CLASS – REFER CLASS
Writing transition function is mandatory for NOTES
all TM design TCS : UNIT 5 14
 VARIANTS OF TURING MACHINE
1. 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).

2. Multi-tape Turing Machine:

•It has multiple tapes and is controlled by a single head.
•Multi-tape Turing machine can be simulated by single-tape Turing machine.

3. Multi-tape Multi-head Turing Machine:

The multi-tape Turing machine has multiple tapes and multiple heads
•Each tape is controlled by a separate head
•Multi-Tape Multi-head Turing machine can be simulated by a standard Turing machine.

4.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

TCS : UNIT 5 15
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. 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.

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.
TCS : UNIT 5 16