Turing Machines

Reading: Chapter 8

1
Turing Machines are…
 Very powerful (abstract) machines that
could simulate any modern day
computer (although very, very slowly!)
For every input,
answer YES or NO
 Why design such a machine?
 If a problem cannot be “solved” even using
a TM, then it implies that the problem is
undecidable

 Computability vs. Decidability 2

 A Turing Machine (TM)
This is like
 M = (Q, ∑, , , q0,B,F) the CPU &
program
counter

Finite
control Tape is the
memory
Tape head
Infinite tape with tape symbols
… B B B X1 X2 X3 … Xi … Xn B B …

Input & output tape symbols

B: blank symbol (special symbol reserved to indicate data boundary)
3
 You can also use:
 for R

Transition function  for L

 One move (denoted by |---)

in a TM does the following: X / Y,D
 (q,X) = (p,Y,D) q p

q is the current state

X is the current tape symbol pointed by
tape head

State changes from q to p

After the move:
 X is replaced with symbol Y
 If D=“L”, the tape head moves “left” by
one position.
Alternatively, if D=“R” the tape head
moves “right” by one position.

4
ID of a TM
 Instantaneous Description or ID :

X1X2…Xi-1qXiXi+1…Xn
means:

q is the current state

Tape head is pointing to Xi

X1X2…Xi-1XiXi+1…Xn are the current tape symbols

 (q,Xi) = (p,Y,R) is same as:

X1…Xi-1qXi…Xn |---- X1…Xi-1YpXi+1…Xn
 (q,Xi) = (p,Y,L) is same as:
X1…Xi-1qXi…Xn |---- X1…pXi-1YXi+1…Xn 5
Way to check for Membership
 Is a string w accepted by a TM?

 Initial condition:
 The (whole) input string w is present in TM,
preceded and followed by infinite blank symbols
 Final acceptance:
 Accept w if TM enters final state and halts
 If TM halts and not final state, then reject

6
 Example: L = {0n1n | n≥1}
 Strategy: w = 000111
…
B B 0 0 0 1 1 1 B B … B B X X 0 Y Y 1 B B …
… …
…
… B B X 0 0 1 1 1 B B … B B X X X Y Y 1 B B …
… …
… B B X 0 0 Y 1 1 B B … B B X X X Y Y Y B B …
…
… B B X X 0 Y 1 1 B B …
B B X X X Y Y Y B B …

Accept 7
 TM for {0n1n | n≥1}
Y / Y,R 1. Mark next unread 0 with X
0 / 0,R and move right
2. Move to the right all the way
0 / X,R to the first unread 1, and mark
q0 q1 it with Y
3. Move back (to the left) all the
1 / Y,L way to the last marked X, and
Y / Y,R then move one position to the
X / X,R right
q2
q3 4. If the next position is 0, then
Y / Y,R goto step 1.
Else move all the way to the
B / B,R Y / Y,L right to ensure there are no
0 / 0,L excess 1s. If not move right to
q4
the next blank symbol and
stop & accept.

8
 *state diagram representation preferred

TM for {0n1n | n≥1}

Next Tape Symbol

Curr. 0 1 X Y B
State
q0 (q1,X,R) - - (q3,Y,R) -

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

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

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

*q4 - -- - - -

Table representation of the state diagram

9
TMs for calculations
 TMs can also be used for calculating
values
 Like arithmetic computations
 Eg., addition, subtraction, multiplication,
etc.

10
 Example 2: monus subtraction
“m -- n” = max{m-n,0}
0m10n  ...B 0m-n B.. (if m>n)
...BB…B.. (otherwise)
Give state diagram

1. For every 0 on the left (mark X), mark off a 0 on the right
(mark Y)
2. Repeat process, until one of the following happens:
1. // No more 0s remaining on the left of 1
Answer is 0, so flip all excess 0s on the right of 1 to Bs
(and the 1 itself) and halt
2. //No more 0s remaining on the right of 1
Answer is m-n, so simply halt after making 1 to B

11
 Example 3: Multiplication
 0m10n1 (input), 0mn1 (output)

 Pseudocode:
1. Move tape head back & forth such that for every
Give state diagram

0 seen in 0m, write n 0s to the right of the last

delimiting 1
2. Once written, that zero is changed to B to get
marked as finished
3. After completing on all m 0s, make the
remaining n 0s and 1s also as Bs

12
 Calculations vs. Languages
The “language” for a certain
A “calculation” is one calculation is the set of strings of
that takes an input the form “<input, output>”, where
and outputs a value the output corresponds to a valid
(or values) calculated value for the input

A “language” is a set
E.g., The language Ladd for the addition operation
of strings that meet
certain criteria “<0#0,0>”
“<0#1,1>”
…
“<2#4,6>”
…
Membership question == verifying a solution
e.g., is “<15#12,27>” a member of Ladd ? 13
Language of the Turing
Machines
 Recursive Enumerable (RE) language

Regular Context-

sensitive

Enumerable
Recursively
Context
(DFA)
free
(PDA)

14
Variations of Turing Machines

15
 Generic description
Will work for both a=0 and a=1
TMs with storage
 E.g., TM for 01* + 10*Current
Tape Next
Current Storage symbol state
state symbol New
Storage
symbol
q Transition function :
storage
• ([q0,B],a) = ([q1,a], a, R)

Tape head
• ([q1,a],a) = ([q1,a], a, R)
B B 0 1 1 1 1 1 B B …
• ([q1,a],B) = ([q2,B], B,
R)
Are the standard TMs Yes
[q,a]: where q is current state,
a is the symbol in storage
equivalent to TMs with storage?
16
Multi-track Turing Machines
 TM with multiple tracks,
but just one unified tape head
control
One tape head to read
k symbols from the k tracks
at one step.
Track 1 … …
… …
Track 2
…
…

Track k … …

18
 Multi-Track TMs
 TM with multiple “tracks” but just one
head E.g., TM for {wcw | w {0,1}* }
but w/o modifying original input string

BEFORE AFTER
control control

Tape head Tape head

… B B 0 1 0 c 0 1 0 B … Track 1 … B B 0 1 0 c 0 1 0 B … Track 1

… B B B B B B B B B B … Track 2 … B B X X X c Y Y Y B … Track 2

19
Second track mainly used as a scratch space for marking
Multi-tape Turing Machines
 TM with multiple tapes, each tape with a
separate head
 Each head can move independently of the
others
control
k separate heads

Tape 1 … …
… …
Tape 2
…

Tape k … … 22
 Non-deterministic TMs  Deterministic
TMs

Non-deterministic TMs
 A TM can have non-deterministic moves:

(q,X) = { (q1,Y1,D1), (q2,Y2,D2), … }
 Simulation using a multitape deterministic
TM:
Control

Input tape
ID1 ID2 ID3 ID4
Marker tape * * * *
Scratch tape

26
Unrestricted Grammar
 An unrestricted grammar or phrase structured grammar is 4
tuple G=(V, T, P, S), where V and T are disjoint set of variables
and terminals, respectively. S is the element of V called the
starting symbol; and P is the set of productions of the form
αβ
where α,β ϵ(V U T)* and α contains at least one variable.

 Recall from CFG, the process of derivation from G

α==>* β
G

means that βcan be derived from α in zero or more

steps.
 The language of G is formally defined as
L(G)={x ϵ T* | S==>* x}.
G

27
An Unrestricted Grammar for
generating {anbn cn |n≥ 1}
 Let
L= {anbn cn |n≥ 1}

 The grammar to generate L has the productions

SFS1 S1ABCS1 S1ABC
BAAB CAAC CBBC
FAa aAaa aBab
bBbb bCbc cCcc

28
An Unrestricted Grammar for
generating {anbn cn |n≥ 1}
 Let us consider the string aabbcc

 The derivation for this string is as fallows.

S=>FS1 =>FABCS1 =>FABCABC
=>FABACBC =>FAABCBC =>FAABBCC
=>aABBCC =>aaBBCC =>aabBCC
=>aabbCC =>aabbcC =>aabbcc

29
Chomsky Hierarchy

Regular Context-

sensitive

Enumerable
Recursively
Context
(DFA)
free
(PDA)

30
Chomsky Hierarchy
Type Languages Forms of production in Accepting
grammar Device
3 Regular AaB, Aa DFA
(A,B ϵV, a ϵT)
2 Context free Aα PDA
(A ϵV, α ϵ(V UT)*)
1 Context αβ LBA
Sensitive (α, β ϵ(V UT)*, |β| ≥ |α|,
α contains a variable)
0 Recursively αβ TM
Enumerable (α, β ϵ(V UT)*,
α contains a variable)

31
Undecidability

Post’s Correspondence Problem (PCP)

An instance of PCP is called a correspondence system and

consists of a set of pairs (a1, b1), (a2, b2),……(an, bn),

where ai’s and bi’s are non null strings over an alphabet ∑.

 The question we are interested in for an instance like this is

whether there is a sequence of one or more integers i1, i2,
…., ik, each ik satisfying 1≤ ik ≤ n and ij’s are not necessarily
distinct, so that ai1, ai2,……,aik=bi1, bi2, …….,bik. 32
Undecidability

The instance is a yes-instance if there is a such a sequence,

and we call the sequence a solution sequence for the instance.
15234434 A B
10 101
01 100
0 10
100 0
1 010 33
Summary
 TMs == Recursively Enumerable languages
 TMs can be used as both:
 Language recognizers
 Calculators/computers
 Basic TM is equivalent to all the below:
1. TM + storage
2. Multi-track TM
3. Multi-tape TM
4. Non-deterministic TM
 TMs are like universal computing machines
with unbounded storage
34