Theory of
Computation
• Turing Machine
• Design of Turing Machine
• Universal Turing Machine
• Church Turing Thesis
Topics to be covered
• What is Turing Machine?
• Formal Definition: Turing Machine
• Design of Turing Machine
• Universal Turing Machine
• Church Turing Thesis
Introduction
Finite Automata Pushdown Automata Turing Machine
• Recursively
Input Strings enumerable
• Inputlanguage
Strings the machine halts
• Input Strings
for input strings which are in language •L. but
• Stack Tape for
a b strings
input a a which are not in L, it may halt or may not
• Special symbol
Stack Accept
halt. When we come to Control
I/p recursive| Reject
language it always
• Control portion
halt whether it is accepted by the machine aorbnot.
Δ a a b Δ
TM
Tape
PDA Stack Head
FA Recursively enumerable language
Context free language
Regular language
Turing Machine
Δ b a ab b a Δ
Head
• The tape can perform following three operations:
• Read a symbol above the tape head.
• Modify/Update a symbol above the tape head.
• Shifting either to previous square or next square.
Turing Machine
𝑞2 𝑞3
𝑞1 𝑞4 Δ b a a b a Δ
Head
𝑞5 𝑞6
Tape
Control portion
Turing Machine = Control portion + Tape
Turing Machine
Operation to be performed by TM:
• Read a symbol above the tape head.
• Modify/Update a symbol above the tape head.
• Shifting either to previous square or next square.
Δ b a ab b a Δ
Head
Some other Ex:
Update b | a, L
Read Shift (L or R or S) a | Δ, R
a | b, R a | a, R
𝑞0 𝑞1
a | A, S
Definition: Turing Machine
• A Turing machine is a 5-tuple 𝑇 = (𝑄, Σ, ┌, 𝑞0, δ) where,
𝑄 ∶ is a finite set of states, assumed not to contain ha
(Acceptance State) and hr(Rejection State).
Σ : input Symbols
┌ ∶tape alphabets
𝑞0 : is initial state, is an element of Q.
δ : is a transition function.
∗
Turing Machine Accepting 𝑎𝑏 𝑎
∗
Design a Turing Machine Accepting 𝑎𝑏 𝑎
L = {ab*a} {(ab)*a)} {(a+b)*a} {a*b*a}
Tape
Strings accepting in given L are:
aa Δ a
A b
B a
A Δ
aba
abba
abbba
Δ aA B
b b
B aA Δ
Logic:
1. Read ‘a’, replace ‘a’ by ‘A’ (a→A)
2. Read all ‘b’ one by one & replace it by ‘B’ (b→B)
Δ Aa Aa Δ
if no ‘b’ found: SKIP step 2
3. Read ‘a’, replace ‘a’ by ‘A’ (a→A)
∗
Design a Turing Machine Accepting 𝑎𝑏 𝑎
Tape
Δ a
A b
B a
A Δ
ℎ𝑟
b|B,R a|A,R
b|B,R b|B,R
Δ|Δ,R a|A,R a|A,R Δ|Δ,S
𝑞0 𝑞1 𝑞2 𝑞3 ℎ𝑎
Control portion
Turing Machine Accepting {𝑎𝑛 𝑏 𝑛 | 𝑛 ≥ 1 }
Design a Turing Machine Accepting {𝑎𝑛 𝑏 𝑛 | 𝑛 ≥ 1 }
L = {anbn}
Tape
Strings accepting in given L are:
ab Δ a
A a
A B
b b
B Δ
aabb
aaabbb
Logic:
1. Read ‘a’, replace ‘a’ by ‘A’ (a→A)
2. Move RIGHT to first ‘b’ Δ aA aA Aa Bb b
B b
B Δ
if none : REJECT
3. Replace ‘b’ by ‘B’ (b→B)
4. Move LEFT to leftmost ‘a’
5. Repeat the above steps until no more a’s
6. Make sure no more b’s remain.
Design a Turing machine for accepting {𝑎𝑛 𝑏𝑛 𝑛 ≥ 1
aaabba
Δ A
a Aa bB B
b Δ
B/B,R B/B,L
a/a,R a/a,L
Δ/Δ,R a/A,R b/B,L
𝑞0 𝑞1 𝑞2 𝑞3
B/B,R
A/A,R
𝑞4
B/B,R
Δ/Δ,S
ℎ𝑎
Turing Machine Accepting {𝑎𝑛 𝑏 𝑛 𝑐 𝑛 | 𝑛 ≥ 0 }
Design a Turing machine for accepting {𝑎𝑛 𝑏 𝑛 𝑐 𝑛 | 𝑛 ≥ 0 }
a/a,R b/b,R C/C,L
B/B,R C/C,R a/a,L
b/B,R c/C,L b/b,L
Δ A a bB b
a A B C
c C
c Δ 𝑞2 𝑞3 𝑞4 B/B,L
a/A,R A/A,R
Δ/Δ,R
𝑞0 𝑞1
Δ/Δ,S
B/B,R ℎ𝑎
𝑞5 C/C,R Δ/Δ,S
𝑞6
B/B,R
C/C,R
TM Accepting same no of 0’s and 1’s
Design a TM for accepting same no of 0’s and 1’s
L = Same no. of 0’s and 1’s
Strings accepting in given L are:
Δ 1x 0x x0 1x Δ
01
10
0101 Δ 0x 1x 1x 0x 0x 1x Δ
1100
100011
Logic:
1. Move right, Read first leftmost 0, replace 0 with X (0→X)
2. Keep moving to the left until you encounter Δ
3. Move right, Read first leftmost 1, replace 1 with X (1→X)
4. Keep moving to the left until you encounter Δ
5. Repeat the above steps until no more 0’s and 1’s left in string.
Design a TM for accepting same no of 0’s and 1’s
Δ 1X 0
X 0X 1
X Δ
1/1,R x/x,L x/x,R x/x,L
x/x,R 1/1,L 0/0,R 0/0,L
Δ/Δ,R
0/x,L Δ/Δ,R 1/x,L
𝑞0 𝑞1 𝑞2 𝑞3 𝑞4
Δ/Δ,L
Δ/Δ,R
Δ/Δ,S
𝑞5 ℎ𝑎
x/x,L
Turing Machine Accepting Palindrome
strings of Even & Odd length
Design a TM for accepting Palindrome strings of
even & odd length.
L = Palindrome string
Tape
Strings accepting in given L are:
aa Δ aΔ Δ
b b
Δ Δa Δ
bab Even Length
abba
babab
Δ Δ Δ
b a Δ
b Δ b
a Δ Δ
Logic: Odd Length
1. Read leftmost symbol , replace it with Δ
2. Keep moving to the right until the rightmost symbol,
If matched with leftmost symbol then replace it with Δ
Otherwise : REJECT the String
3. Repeat the above steps until no more symbol left in string.
Design a TM for accepting Palindrome strings of even &
odd length.
a/a,R
b/b,R Δ/Δ,R (odd pal)
Δ a
Δ b
Δ b
Δ a
Δ Δ
Δ/Δ,L
𝑞2 𝑞3
a/a,L
b/b,L
a/Δ,R a/Δ,L
Δ/Δ,R Δ/Δ,R
𝑞0 𝑞1 𝑞4 ℎ𝑎
b/Δ,R b/Δ,L
Δ/Δ,L Δ/Δ,R
Test string: 𝑞5 𝑞6 (odd pal)
ababa
a/a,R
babab b/b,R
Δ/Δ,R (even pal)
String Tracing
├ (q0,△ a a △)
├ (q1,△ a a △)
├ (q2,△ △ a △)
├ (q2,△ △ a △ )
├ (q3,△ △ a △)
├ (q4,△ △ △ △)
├ (q1,△ △ △ △)
├ (ha, △ △ △ △)
Accept
Exercise
1. aba
2. abab
TM Accepting same no of a’s, b’s & c’s
Design a TM for Accepting {𝑥 ∊ {𝑎, 𝑏, 𝑐}∗ | 𝑛𝑎 𝑥 = 𝑛𝑏 𝑥 = 𝑛𝑐(𝑥) }
X Xa cX cX Xa b
Δ b X Δ
x/x,R x/x,L x/x,R x/x,L x/x,R x/x,L
b/b,R b/b,L a/a,R a/a,L b/b,R b/b,L
c/c,R c/c,L c/c,R c/c,L a/a,R a/a,L
Δ/Δ,R a/x,L Δ/Δ,R b/x,L Δ/Δ,R c/x,L
𝑞0 𝑞1 𝑞2 𝑞3 𝑞4 𝑞5 𝑞6
Δ/Δ,L Δ/Δ,R
Δ/Δ,S
𝑞7 ℎ𝑎
x/x,L
Turing machine to delete a symbol
Design a Turing machine to delete a symbol
ΔaabΔ
Δ a Δ
b a b Δ
Logic:
1. Replace the symbol you want to delete by Δ.
2. Keep moving to the Right until you encounter Δ.
3. One by one Keep shifting every symbol one step to left until you encounter Δ.
Design a Turing machine to delete a symbol
a/a,L
Δ a Δa
b ab bΔ Δ
𝑞3
a/a,R
b/b,R
a/Δ,R a/Δ,L Δ/a,S
Δ/Δ,R
b/Δ,R
Δ/Δ,L b/a,L a/b,L
𝑞0 𝑞1 𝑞2 ℎ𝑎
b/Δ,L Δ/b,S
Δ/Δ,S 𝑞4
Check for b a a b b b/b,L
Turing machine to copy a string
Design a Turing machine to copy a string
String:
Δ aa
A bB Δ a
Δ Δ
b Δ
Δ ab Δ ab
Original Pasted
Δ bab Δ bab
Δ aA bB b
B a
A Δ aΔ b
Δ b
Δ Δa Δ
Original Pasted
Design a Turing machine to copy a string
a/a,R a/a,R
b/b,R b/b,R
Δ aa
A b
B Δ aΔ Δb Δ
Δ/Δ,R
𝑞2 𝑞3
a/a,L
Δ/a,L a/a,L b/b,L
b/b,L
a/A,R
Δ/Δ,R Δ/Δ,L
𝑞0 𝑞1 𝑞4 𝑞5
Δ/Δ,L b/B,R
Δ/b,L
Δ/Δ,S Δ/Δ,R
ℎ𝑎 𝑞8 𝑞6 𝑞7 a/a,R
a/a,R b/b,R
b/b,R A/A,R
A/a,L
B/b,L B/B,R
Universal Turing Machine
Universal Turing Machine
The language
𝑨𝑻𝑴 = < 𝑴, 𝒘 > 𝑴 𝒊𝒔 𝒂 𝑻𝒖𝒓𝒊𝒏𝒈 𝒎𝒂𝒄𝒉𝒊𝒏𝒆 & 𝑴 𝒂𝒄𝒄𝒆𝒑𝒕𝒔 𝒘
is Turing Recognizable
• Question : Given the description of a Turing Machine and some
input string, can we decide the machine accepts it?
• Answer: Just Run the TM on the input.
• Possible results:
1. M accepts w: will halt and accept
2. M rejects w: will halt and reject
3. M loops on w: will not halt
Input & Action on Universal Turing Machine
Input:
1. M=description of TM
2. w=input string for M
Action:
1. Simulate M
2. Behave just like M (May accept, reject or loop)
Universal Turing Machine vs Turing Machine:
A Universal Turing Machine is just a Turing Machine whose
programming simulates other Turing Machines. That is, the input to
the UTM is a description of a Turing Machine T and an input for T,
and the UTM simulates T on that input.
Church Turing Thesis
Church Turing Thesis
• What does computable mean?
• Meaning of term Computable was given by:
1. Alonzo church (Lambda calculus)
2. Allen Turing (Turing Machine)
• Any algorithmic procedure that can be carried out at all, by a
human computer or a team of humans or an electronic computer,
can be carried out by a TM. This statement usually referred to as
Church’s thesis, or the Church-Turing thesis.
Church Turing Thesis
• Here is an informal summary of some of the evidence.
1. Humans normally work with a two-dimensional sheet of paper. A TM tape
could be organized to simulate two dimensions; one likely consequence
would be that the TM would require more moves to do what a human
could do in one.
2. Various enhancements of the TM model have been suggested to make the
operation more like that of a human computer, or more convenient &
efficient. The multi tape TM is an example.
3. Other theoretical models includes abstract machines with two stacks or
with a queue.
4. Since the introduction of the Turing machine, no one has suggested any
type of computation that ought to be included in the category of
“algorithmic procedure” and cannot be implemented on a TM.
Exercise:
• Design a TM for Accepting {SS | S ∈ {0,1}*}
Logic: 101101→Y0110Y→YX11XY→YXYYXY→
101YXY→Y01_XY→YX1__Y→YXY___→
No 0 and 1 → Replace X and Y with _ → Accepted
2𝑛
• Design a TM for Accepting {0 | n >= 0}
Example:
0 – Accepted
00 – Accepted
000 – Not Accepted
0000 – Accepted
00000 – Not Accepted
000000 – Not Accepted
0000000 – Not Accepted
00000000 – Accepted
End of Unit
Solution (Exercise):
• Design a TM for Accepting {SS | S ∈ {0,1}*}
Solution (Exercise):
2𝑛
• Design a TM for Accepting {0 | n >= 0}
• 0 – Accepted
• 00 – Accepted
• 000 – Not Accepted
• 0000 – Accepted
• 00000 – Not Accepted
• 000000 – Not Accepted
• 0000000 – Not Accepted
• 00000000 – Accepted