What is Turing machine?

 A Turing machine is a mathematical model of

computation that defines an abstract machine, which
manipulates symbols on a strip of tape according to a
table of rules.
 It is a generalized machine which can accept all the
type of languages i.e. regular , context free, context
sensitive, recursive and recursive enumerable
languages .
 There are two purposes for a Turing machine:
deciding formal languages and solving mathematical
functions.
 Model of Turing Machine
a b c c a b a a a b
L R
R/W Input
head Tape

q
Finite State
Control
Mathematical Definition of Turing
Machine (TM)
A Turing machine is described by a 7-tuple
M=(Q, Σ, Γ, δ, q0, B, F) where,

 Q is the finite set of states,

 Σ ⊆ Γ is the set of input symbols
 Γ is the set of tape symbols,
 q0 ∈ Q is the initial state,
 B ∈ Γ is a blank symbol
 F is the set of final states, and
 δ is a transition function which is defined as following:-
 δ: Q×Γ  Q×Γ×{L, R}
where,
L represents left direction and R represents right direction.
Instantaneous Description(ID)
An instantaneous description of TM is a string of the
following form:-
αqβ
Where, α, β ∈ Γ*, q ∈ Q.
αβ denotes the whole contents of the tape.
q is a current state.
R/W head of machine will be at the leftmost symbol of β.
Initial ID will be q0w . where w ∈ Σ*
 Move relation
This relation exist between two consecutives ID’s. It is
dented by .
Consider an ID of a TM at any instant is
a1a2a3………..ai-1qaiai+1……….an.
(1) If δ(q, ai) = (p, y, R) then move of machine will be
a1a2a3………..ai-1qaiai+1……….an a1a2a3………..ai-1 ypai+1……….an

(2) If δ(q, ai) = (p, y, L) then move of machine will be

a1a2a3………..ai-1qaiai+1……….an a1a2a3………..pai-1 yai+1……….an
 Language accepted by TM
The language accepted by Turing machine M is defined as
following:-
L(M) = { w ! q0w * α p β where w ∈ Σ* ,
p ∈ F and α, β ∈ Γ* and machine halts on the final state.}
 Representation of TM
Two representations are used for TM.
(1) By transition table (2) By transition diagram
By transition table
δ Tape symbols

States 0 1 x y B

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
Turing Machine
Part-2
 Representation of TM(continue)
By transition diagram
(0, 0 ,L)
(0, 0 ,R) (y, y, L)
(y, y, R)

(0, x ,R) (1, y ,L)

q0 q1 q2

(y, y, R)
(x, x ,R)
(B, B ,R)
q3 q4

(y, y, R)
 Processing or working of TM
Ex. Check the acceptability of following strings
(1) 0011 (2) 011 (3) 00101
by the TM in the previous example.
Solution:
(1) For string 0011
q00011 ⊢ xq1011 ⊢ x0q111 ⊢ xq20y1 ⊢ q2x0y1 ⊢ xq00y1 ⊢
xxq1y1 ⊢ xxyq11 ⊢ xxq2yy ⊢ xq2xyy ⊢ xxq0yy ⊢ xxyq3y ⊢
xxyyq3B ⊢ xxyyBq4B (machine halts at final state)
Since machine halts at final state, therefore this string is
accepted by TM.
Processing or working of TM(continue)
(2) For string 011
q0011 ⊢ xq111 ⊢ q2xy1 ⊢ xq0y1 ⊢ xyq31 (machine halts at
non-final state)
Since machine halts at non-final state, therefore this string is
not accepted by TM.
(3) For string 00101
q000101 ⊢ xq10101 ⊢ x0q1101 ⊢ xq20y01 ⊢ q2x0y01 ⊢
xq00y01 ⊢ xxq1y01 ⊢ xxyq101 ⊢ xxy0q11 ⊢ xxyq20y ⊢
xxq2y0y ⊢ xq2xy0y ⊢ xxq0y0y ⊢ xxyq30y (machine halts at
non-final state)
Since machine halts at non-final state, therefore this string is
not accepted by TM.
 Construction of TM
In this section, we shall see how TM’s can be constructed.

Ex. Construct TM for the following languages:-

1) L = { 0m1n ! m, n ≥ 1}
2) L= the set of all strings of 0 and 1 which contain 001 as
a substring.
3) L= the set of all strings of 0 and 1 ending with 101.
4) L= the set of strings of a and b which contains at least
one a’s and exactly two b’s.
 Ex. L = { m
0 1 n ! m, n ≥ 1}
Solution:
Procedure: First check given language is regular or not.
If language is regular then first construct DFA for that
language. After, convert it into TM.
Since this language is regular, Therefore the TM for this
language will be
(1,1,R)
(0, 0 ,R)

(0, 0 ,R) (1, 1 ,R)

q0 q1 q2
 Ex. L= the set of all strings of 0 and 1 which
contain 001 as a substring.
Solution:
Since this language is regular, therefore the TM for this
language is

(1, 1, R)
(0, 0, R)
(1, 1 , R) (0, 0, R)
(1, 1, R)

(0, 0 , R) (0, 0 , R) (1, 1, R)

q0 q1 q2
q3
Turing Machine
Part-3
Ex. Construct Turing machine for the language
L = { 0n1n ! n ≥ 1 }.
Solution:
To construct Turing for a language, first we have to identify the
pattern of strings belongs in to L. Some strings are 01, 0011,
000111 etc.
Now, you have to think, how machine move from initial ID to
final ID.
Procedure: Initially machine starts at the initial state q0.
machine scan the tape string. If the current tape symbol is 0,
then machine change its state, replace the current input
symbol 0 by another tape symbol and also the head of machine
move in the right direction.
Machine move in the right direction until 1 appears in
the tape. As soon as 1 appears in the tape, machine replaces 1
by some another tape symbol, return to back i.e. move in the
left direction and change its state.
 L={ n
01 n !n≥1}
Machine move in the left direction till leftmost 0
appears in tape. As soon as, machine be reached at
leftmost 0, its state becomes q0.
we repeat the whole process till any 0 in the tape.
As soon as, all 0’s are deleted from tape, we check number
of 1’s in tape. If there is any 1’s in the tape, then machine
reject the string otherwise machine may accept the string.
Therefore, the TM corresponding to this language will be
M=( {q0,q1,q2,q3, q4}, {0, 1}, {0, 1, x, y, B}, q0, B, {q4})
 L={ n
01 n !n≥1}
Transition table is

q4
 L={ n
01 n !n≥1}
Transition diagram is (0, 0 ,L)
(0, 0 ,R) (y, y, L)
(y, y, R)

(0, x ,R) (1, y ,L)

q0 q1 q2

(y, y, R)
(x, x ,R)
(B, B ,R)
q3 q4

(y, y, R)
 Processing and Verification of TM
Acceptance
Consider string w = 0011 .
q00011 ⊢ xq1011 ⊢ x0q111 ⊢ xq20y1 ⊢ q2x0y1 ⊢ xq00y1 ⊢ xxq1y1
⊢ xxyq11 ⊢ xxq2yy ⊢ xq2xyy ⊢ xxq0yy ⊢ xxyq3y ⊢ xxyyq3B ⊢
xxyyBq4B (machine halts at final state)
Since machine halts at final state, therefore this string is accepted by
TM.

Rejection
Consider string w = 011 .
q0011 ⊢ xq111 ⊢ q2xy1 ⊢ xq0y1 ⊢ xyq31 (machine halts at non-
final state)
Since machine halts at non-final state, therefore this string is not
accepted by TM.
Ex. Construct Turing machine for the language
L = { 0n1n2n! n ≥ 1 }.
Solution:
The TM corresponding to this language is (0, 0 ,L)
(y, y, L)
(0, 0 ,R) (1, 1,R) (1, 1, L)
(y, y, R) (z, z, R) (z, z, L)

(0, x ,R) (1, y ,R) (2, z ,L)

q0 q1 q2 q3

(y, y, R)
(x, x ,R)
(B, B ,R)
q4 q5

(z, z, R)
(y, y, R)
Processing and Verification of TM
Acceptance
Consider string w = 001122 .
q0001122 ⊢ xq101122 ⊢ x0q11122 ⊢ x0yq2122 ⊢ x0y1q222 ⊢
x0yq31z2 ⊢ x0q3y1z2 ⊢ xq30y1z2 ⊢ q3x0y1z2 ⊢ xq00y1z2 ⊢
xxq1y1z2 ⊢ xxyq11z2 ⊢ xxyyq2z2 ⊢ xxyyzq22 ⊢ xxyyq3zz ⊢
xxyq3yzz ⊢ xxq3yyzz ⊢ xq3xyyzz ⊢ xxq0yyzz ⊢ xxyq4yzz ⊢
xxyyq4zz ⊢ xxyyzq4z ⊢ xxyyzzq4B ⊢ xxyyzzBq5B
(machine halts at final state)
Since machine halts at final state, therefore this string is accepted
by TM.
Rejection
Consider string w = 00112 .
q000112 ⊢ xq10112 ⊢ x0q1112 ⊢ x0yq212 ⊢ x0y1q22 ⊢
x0yq31z ⊢ x0q3y1z ⊢ xq30yq11z ⊢ q3x0y1z ⊢ xq00y1z
⊢ xxq1y1z ⊢ xxyq11z ⊢ xxyyq2z ⊢ xxyyzq2B
(machine halts at non-final state)
Since machine halts at non-final state, therefore this string is
not accepted by TM.
Turing Machine
Part-4
Ex. Construct TM to accept the language
L = { wcwR ! w ∈ {a, b}* }
Solution:
Some strings of this set are c, aca, bcb, abcba, bacab, aabcbaa etc.
Clearly all these strings are palindrome. That is, first symbol and
last symbol are same. Similarly, second symbol and second last
symbol are same , and so on.
Procedure: TM is constructed in following steps. Let q0 is the
initial state.
If the first input symbol is a, then remove it and change its
state to q1. After this, machine move to the last input symbol, if last
input symbol is a, then machine remove it and back to first input
symbol of string. This process continue.
If the first input symbol is b, then remove it and change its
state to q5. After this, machine move to the last input symbol, if last
input symbol is b, then machine remove it and back to first input
symbol of string. This process continue.
 L={ wcw R ! w ∈ {a, b}* }
Transition diagram of TM is (a, a ,R)
(a, a ,R) (b, b, R)
(b, b, R) (a, a ,L)
(B, B, L) (b, b, L)
(c, c ,R)
(c, c, L)
q1 q2 q3
(a, B ,R)
(a, B, L)
(B, B, R)
q0 q4
(a, a ,R) (a, a ,R)
(b, b, R) (b, b, R)
(b, B ,R)
(c, c ,R) q5 q6 q7 (b, B, L)
(c, c ,R) (B, B, L)

(B, B ,R)
q8 q9
Processing and Verification of TM
Acceptance
Consider string w = aabcbaa .
q0aabcbaa ⊢ Bq1abcbaa ⊢ Baq1bcbaa ⊢ Babq1cbaa ⊢
Babcq2baa ⊢ Babcbq2aa ⊢ Babcbaq2a ⊢ Babcbaaq2B ⊢
Babcbaq3aB ⊢ Babcbq4aB ⊢ Babcq4baB ⊢ Babq4cbaB ⊢
Baq4bcbaB ⊢ Bq4abcbaB ⊢ q4BabcbaB ⊢ Bq0abcbaB ⊢
BBq1bcbaB ⊢ BBbq1cbaB ⊢ BBbcq2baB ⊢ BBbcbq2aB ⊢
BBbcbaq2B ⊢ BBbcbq3aB ⊢ BBbcq4bBB ⊢ BBbq4cbBB ⊢
BBq4bcbBB ⊢ Bq4BbcbBB ⊢ BBq0bcbBB ⊢ BBBq5cbBB ⊢
BBBcq6bBB ⊢ BBBcbq6BB ⊢ BBBcq7bBB ⊢ BBBq4cBBB ⊢
BBq4BcBBB ⊢ BBBq0cBBB ⊢ BBBcq8BBB⊢ BBBcBq9BB
(machine halts at final state)
Since machine halts at final state, therefore this string is
accepted by TM.
Rejection
Consider string w = abcaa .
q0abcaa ⊢ Bq1bcaa ⊢ Bq1bcaa ⊢ Bbq1caa ⊢ Bbcq2aa ⊢ Bbcaq2a
⊢ Bbcaaq2B ⊢ Bbcaq3aB ⊢ Bbcq4aB ⊢ Bbq4caB ⊢ Bq4bcaB ⊢
q4BbcaB ⊢ Bq0bcaB ⊢ BBq5caB ⊢ BBcq6aB ⊢
BBcaq6B ⊢ BBcq7aB (machine halts at non-final state)
Since machine halts at non-final state, therefore this string is
not accepted by TM.
Ex. Construct TM to accept the language
L = { wwR ! w ∈ {a, b}* }
Transition diagram of TM is
(a, a ,R)
(b, b, R)

(B, B, L) (a, a ,L)

(b, b, L)
q1 q2
(a, B ,R)
(a, B, L)
(B, B, R)
q0 q3
(a, a ,R)
(b, b, R)
(b, B ,R)
q4 q5 (b, B, L)
(B, B ,R)
(B, B, L)

q6
Processing and Verification of TM
Acceptance
Consider string w = abba.
q0abba ⊢ Bq1bba ⊢ Bbq1ba ⊢ Bbbq1a ⊢ Bbbaq1B⊢ Bbbq2aB ⊢
Bbq3bBB ⊢ Bq3bbBB ⊢ q3BbbBB ⊢ Bq0bbBB ⊢ BBq4bBB ⊢
BBbq4BB ⊢ BBq5bBB ⊢ Bq3BBBB ⊢ BBq0BBB ⊢ BBBq6BB
(machine halts at final state)
Since machine halts at final state, therefore this string is accepted
by TM.
Rejection
Consider string w = abaa .
q0abaa ⊢ Bq1baa ⊢ Bbq1aa ⊢ Bbaq1a ⊢ Bbaaq1B ⊢ Bbaq2aB ⊢
Bbq3aBB ⊢ Bq3baBB ⊢ q3BbaBB ⊢ Bq0baBB ⊢ BBq4aBB ⊢
BBaq4BB ⊢ BBq5aBB (machine halts at non-final state)
Since machine halts at non-final state, therefore this string is not
accepted by TM.
 Some additional problems
Construct TM for the following languages:-
(1) L = { an+2bn ! n ≥ 1}
(2) L = { anbncm ! m, n ≥ 0}
(3) L = {anbncn ! n ≥ 1}
Turing Machine
Part-5
 Turing computable function
Def. A function f : Nn N is said to be Turing computable
function if there exist a Turing machine which compute
this function.
Here Nn = N×N×N……………………………×N(upto n times)
Note:
1) In the designing of Turing machine, we use unary
number to represent a number. Here we use the unary
number as a string of 1’s.
Ex. 4 = 1111, 3 = 111 and so on.
2) If the function has multiple arguments, then we separate
the arguments by 0.
Ex. Construct Turing machine for the following function
1) f(n) = n+2 n∈N
2) f(m,n) = m+n m, n ∈ N
Solution:
1) In this function, if input is 1111 then output will be 111111.
i.e. q01111 ⊢* qf111111
TM for this function will be
(1, 1 ,L)
(B, 1 ,L) (B, 1 ,L)
q0 q1 q2

Computation by this machine

q01111 ⊢ q0B1111 ⊢ q1B11111 ⊢ q2B111111 (machine halt at final
state)
(2) f(m,n) = m+n m, n ∈ N
Solution:
In this function if the input is 110111 then output will be 11111.
TM for this function will be

(1, 1 ,R) (1, 1 ,R)

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

Computation by this machine

q0110111⊢ 1q010111 ⊢ 11q00111 ⊢ 111q1111 ⊢ 1111q111 ⊢ 11111q11 ⊢
111111q1B ⊢ 11111q21 B⊢ 11111Bq3B (machine halt at final state)
Ex. Show that following function is Turing computable:-
f(n) = 3*n n≥1
Solution:
A function is said to be Turing computable if there exist a TM for
this.
Therefore, we shall construct TM for this function.
In this function, if the input is 2 then output will be 6. That is if
input is 11 then output will be 111111.
First, we shall show that how string 11 is converted into 111111.
After this, we construct Turing machine for this.
Suppose initial state is q0.
q011 ⊢yq11 ⊢y1q1B⊢y1Bq2B ⊢y1B1q3B ⊢y1B11q4B ⊢y1B1q511
⊢y1Bq5111 ⊢y1q5B111 ⊢yq51B111 ⊢q5y1B111 ⊢yq01B111
⊢yyq1B111 ⊢yyBq2111⊢yyB1q211⊢yyB11q21⊢yyB111q2B
⊢yyB1111q3B ⊢yyB11111q4B ⊢yyB1111q511B ⊢yyB111q5111B
⊢yyB11q51111B ⊢yyB1q511111B ⊢yyBq5111111B
⊢yyq5B111111B ⊢yq5yB111111B ⊢yyq0B111111B ⊢yyBq6111111B
 Therefore, the Turing machine corresponding above
function is constructed as following:-

(1, 1 ,L)
(1, 1 ,R) (B, B, L)

(B, B ,R) (B, 1 ,R) (B, 1 ,R) (B, 1 ,L)

(1, y ,R)
q0 q1 q2 q3 q4 q5

(B, B ,R) (y, y ,R)

q6
Turing Machine
Part-6
Ex. Show that following function is Turing computable:-
f(m, n) = m-n m≥n
= 0 otherwise
Solution: Clearly this function is proper subtraction function.
We have to find TM corresponding to this function.
There are two cases of this function.
Case-1: If m ≥ n then value of the function is m-n. i.e. if m= 6
and n=4 then value = 2.
Case-2: If m < n then value of the function is 0. i.e. if m= 4 and
n=6 then value = 0.
Before constructing TM for this function, first we process the
input and develop rules through which machine move from initial
ID to final ID.
Case-1: when m ≥ n.
q01111011 ⊢ 1q0111011 ⊢ 11q011011 ⊢ 111q01011 ⊢
1111q0011 ⊢11110q111 ⊢1111q20y1 ⊢ 111q210y1 ⊢
111yq00y1⊢ 111y0q1y1⊢ 111y0yq11 ⊢111y0q2yy ⊢ 111yq20yy
⊢ 111q2y0yy⊢ 11q21y0yy⊢ 11yq0y0yy⊢ 11yyq00yy
⊢ 11yy0q1yy⊢ 11yy0yq1y⊢ 11yy0yyq1B⊢ 11yy0yq3yB
(machine halts at final state)
Case-2: when m < n.
q01101111 ⊢* yy0yyq111 ⊢ yy0yq2yy1 ⊢* q2Byy0yyy1 ⊢
Bq4yy0yyy1 ⊢* Byy0yyyq41 ⊢ Byy0yyyyq4B⊢ Byy0yyyq3yB

(machine halts at final state)

Therefore, the TM corresponding this function will be
constructed as following:-

(y, y , L) (y, y , R)
(1, 1 ,R) (0, 0, L) (0, 0, R)
(y, y, R) (y, y , R) (1, y, R)

(0, 0, R) (1, y , L) (B, B ,R)

q0 q1 q2 q4

(1, y , R)
(B, B ,L)
(B, B ,L)

q3
Ex. Construct Turing machine for the following function
f(m,n) = m*n m, n ∈ N
Solution: This function multiply two numbers.
If inputs are 2 and 3 then output will be 6.
Processing:
q0110111 ⊢xq110111 ⊢ x1q10111 ⊢ x10q2111 ⊢ x10yq211 ⊢
x10yyq21 ⊢ x10yyyq2B ⊢ x10yyq3yB ⊢ x10yy1q4B ⊢ x10yy1B q5B⊢
x10yy1q6B1⊢ x10yyq31B1⊢ x10yq3y1B1
⊢ x10y1q41B1⊢ x10y11q4B1⊢ x10y11Bq51⊢ x10y11B1q5B⊢
x10y11Bq611⊢ x10y11q6B11 ⊢ x10y1q31B11 ⊢ x10yq311B11⊢
x10q3y11B11⊢ x101q411B11⊢ x1011q41B11⊢ x10111q4B11⊢
x10111Bq511⊢ x10111B1q51⊢ x10111B11q5B⊢ x10111B1q611⊢
x10111Bq6111⊢ x10111q6B111⊢ x1011q31B111⊢ x101q311B111⊢
x10q3111B111 ⊢ x1q30111B111 ⊢ xq310111B111 ⊢ q3x10111B111⊢
xq010111B111 ⊢ *xxq00111B111111 ⊢xxBq7111B111111
⊢xxBBq711B111111 ⊢xxBBBq71B111111 ⊢xxBBBBq7B111111
⊢xxBBBBBq8111111 (machine halts at final state)
 Therefore, the TM corresponding this function will be
constructed as following:-

(1, 1 ,L)
(0, 0, L) (1, 1 ,R)
(1, 1 ,R) (1, y ,R) (1, 1 ,R)

(1,x, R) (0, 0, R) (B, B, L) (y, 1 ,R) (B, B ,R)

q0 q1 q2 q3 q4 q5

(B, 1, L)
(0,B, R) (x, x, R)
(B, B, L)
(B, B ,R) q6
q7 q08

(1, B ,R) (1, 1, L)

Turing Machine
Part-7
 Variations or types of TM
1) Non-deterministic Turing Machine(TM)
2) Multi-tape Turing Machine(TM)
3) Multi-head Turing Machine(TM)
4) Multi-directional Turing Machine(TM)
Non-deterministic Turing Machine(TM)
 A non-deterministic TM is a Turing machine which,
like nondeterministic finite automata, at any state it is
in and for the tape symbol it is reading, can take any
action selecting from a set of specified actions rather
than taking one definite predetermined action.
 Even in the same situation it may take different actions
at different times.
 It differs from deterministic TM only by transition
function.
 The transition function of non-deterministic TM is
defined as following:-
δ: Q×Γ  2Q×Γ×{L, R}
Multi-tape Turing Machine(TM)
Model of TM a b c c a b a a a b
R/W head

a b c c a b a a a b
R/W head

a b c c a b a a a b
R/W head

q
Finite State
Control
 Multi-tape Turing Machine(TM)
This type of machine consists of n number of tapes.
Since number of tapes is n, therefore the number of
heads will also be n.
Transition function will be
δ: Q×Γn  Q×Γn×{L, R}n
Where
Γn = Γ× Γ× Γ×……………….. × Γ(upto n times)
{L, R}n = {L, R}× {L, R}× {L, R}×……………….. × {L, R}
(upto n times)
 Multi-head Turing Machine(TM)
Model of TM
Tape

a b c c a b a a a b
R/W head R/W head
R/W head

q
Finite State
Control
Multi-head Turing Machine(TM)
This type of machine consists of one tape with n heads.
Transition function will be
δ: Q×Γn  Q×Γn×{L, R}n
Where
Γn = Γ× Γ× Γ×……………….. × Γ(upto n times)
{L, R}n = {L, R}× {L, R}× {L, R}×……………….. × {L, R}
(upto n times)
Multi-dimensional Turing Machine(TM)
Tow-dimensional tape
Model of TM

L Head R
D

q
Finite State
Control
Multi-dimensional Turing Machine(TM)
 This type of machine consists of one multi-dimensional
tape with one heads.
 The head of machine move in many directions.
 If tape is n-dimensional then head move in 2n directions.
 Transition function of two-dimensional TM is defined as
δ: Q×Γ  Q×Γ×{L, R, U, D}
Where
L Left direction
R Right direction
U Up direction
D Down direction
Recursive and Recursive Enumerable language
Recursive language:
A language L is said to be recursive if there exists a Turing
machine M which accepts all the strings w belong into L and
rejects all the strings which do not belong into L.
Y
w
M
N

Recursive Enumerable language:

A language L is said to be recursive enumerable if there exists
a Turing machine M which accepts all the strings w belong
into L and rejects or goes into an infinite loop for all the
strings which do not belong into L.
RE
w
M Y R
 Properties of Recursive and Recursive
Enumerable languages
1) If L is recursive language then L is also recursive language.
2) If L and L are recursive enumerable languages then L will be
recursive language.
3) The union of two recursive languages is also recursive i.e. if
L1 and L2 are recursive then L1 L2 will be also recursive.
4) The union of two recursive enumerable languages is also
recursive enumerable i.e. if L1 and L2 are recursive
enumerable then L1 L2 will be also recursive enumerable.
5) The intersection of two recursive languages is also recursive
i.e. if L1 and L2 are recursive then L1 L2 will be also
recursive.
6) The intersection of two recursive enumerable languages is
also recursive enumerable i.e. if L1 and L2 are recursive
enumerable then L1 L2 will be also recursive enumerable .
Theorem: If L is recursive language then complement of L i.e. L is
also recursive language.
Proof: Since L is recursive language, therefore there exists a TM
which accepts all strings belong into L and rejects all strings which
do not belong into L. Let this TM is M. Therefore M will be

Y Y
Y w
w M
M N
N N
M’
Now, we construct a TM M’ using M as above.
Clearly, if w is accepted by M then w is rejected by M’ and if w is
rejected by M then w is accepted by M’. Since L is accepted by M,
therefore complement of L i.e. L is accepted by M’.
Since there exists a TM M’ corresponding to L, therefore L is
recursive language.
Theorem: If L and L are recursive enumerable languages then L will be
recursive language.
Proof: Since L and L are recursive enumerable language, therefore there exists
TM M1 and M2 corresponding to L and L respectively. M1 accepts all strings
belong into L and M2 accepts all strings belong into and L. These are

w Y w Y
M1 Y
M1

w Y Y N
M2 M2
M

Now, we construct a TM M using M1 and M2 as above.

Clearly, if w is accepted by M1 then w is also accepted by M and if w is
accepted by M2 then w is rejected by M. That is, if w ∈ L then it is accepted by
M and if w ∉ L then it is rejected by M.
Therefore, M is a TM which accepts all strings of L and rejects all strings
which are not belong into L.
Hence L is recursive language.
Theorem: The union of two recursive languages is also recursive i.e. if L1
and L2 are recursive then L1 L2 will be also recursive.
Proof: Since L1 and L2 are recursive languages then there exists TM M1
and M2 corresponding to L1 and L2 respectively are of the form:
E-> enable M
w Y
M1 Y
N w Y
M1
N
w Y Y
M2 E
N w M2
N
N
Consider a string w ∈ L1 L2. Then w ∈ L1 or w ∈ L2.
If w ∈ L1 then it is accepted by M1. therefore it is also accepted by M. If w ∈
L2 then it is accepted by M2. therefore it is also accepted by M.
But if w ∉ L1 L2 then w is neither accepted by M1 nor M2. therefore it is
also not accepted by M.
Hence M is a machine which accepts all strings belong into L1 L2 and
rejects all strings which do not belong into L1 L2.
Therefore L1 L2 is recursive language.
Theorem: The union of two recursive enumerable languages is also
recursive enumerable i.e. if L1 and L2 are recursive enumerable then
L1 L2 will be also recursive enumerable.
Proof: Since L1 and L2 are recursive enumerable languages then there
exists TM M1 and M2 corresponding to L1 and L2 respectively are of the
form:
M
w Y
M1 w Y
M1
Y
Y Y
w M2
M2

Consider a string w ∈ L1 L2. Then w ∈ L1 or w ∈ L2.

If w ∈ L1 then it is accepted by M1. therefore it is also accepted by M. If w ∈
L2 then it is accepted by M2. therefore it is also accepted by M.
But if w ∉ L1 L2 then w is neither accepted by M1 nor M2. therefore it is
also not accepted by M.
Hence M is a machine which accepts all strings belong into L1 L2 and
rejects all strings which do not belong into L1 L2.
Therefore L1 L2 is recursive language.
Theorem: The intersection of two recursive languages is also recursive i.e. if
L1 and L2 are recursive then L1 L2 will be also recursive.
Proof: Since L1 and L2 are recursive languages then there exists TM M1 and
M2 corresponding to L1 and L2 respectively are of the form:
E-> enable M

w Y
M1 Y Y
N w
M1 N
w Y Y
M2 E
N w M2
N
N
Consider a string w ∈ L1 L2. Then w ∈ L1 and w ∈ L2.
Since w ∈ L1 therefore it is accepted by M1. therefore it is also accepted by M. Since w
∈ L2 therefore it is accepted by M2. Clearly, therefore it is also accepted by M.
But if w ∉ L1 L2 then w is either not belong into L1 or not belong into L2. therefore it
is either not accepted by M1 or not accepted by M2. Clearly, therefore w is not
accepted by M.
Hence M is a machine which accepts all strings belong into L1 L2 and rejects all
strings which do not belong into L1 L2 .
Therefore L1 L2 is recursive language.
Theorem: The intersection of two recursive enumerable languages is also
recursive enumerable i.e. if L1 and L2 are recursive enumerable then L1 L2
will be also recursive enumerable.
Proof: Since L1 and L2 are recursive enumerable languages then there exists
TM M1 and M2 corresponding to L1 and L2 respectively are of the form:
E-> enable M

w Y
M1 M1 Y
w Y

w Y E Y
M2 M2
w

Consider a string w ∈ L1 L2. Then w ∈ L1 and w ∈ L2.

Since w ∈ L1 and w ∈ L2 , therefore it is accepted by both M1 and M2. Clearly,
therefore it is also accepted by M.
But if w ∉ L1 L2 then w is either not belong into L1 or not belong into L2. In
this case, we can not say that w is accepted or not accepted by M1 or M2.
Clearly, therefore we can also say that w is accepted or not by M.
Hence M is a machine which accepts all strings belong into L1 L2 and rejects
or goes into infinite loop for all strings which do not belong into L1 L2 .
Therefore L1 L2 is recursive enumerable language.
Post Correspondence Problem(PCP)
The PCP problem over an alphabet ∑ is stated as follows:−

Given the following two lists, X and Y of non-empty

strings over ∑,
X = (x1, x2, x3,………, xn)
Y = (y1, y2, y3,………, yn)
We can say that there is a Post Correspondence Solution,
if for some (i1,i2,………… ik), where 1 ≤ ij ≤ n, the condition
xi1 xi2 …….xik = yi1 yi2 …….yik satisfies.
Ex. Find whether the lists X = (abb, aa, aaa) and
Y = (bba, aaa, aa) have a Post Correspondence Solution?
Solution:
Here,
x2x1x3 = ‘aaabbaaa’
and y2y1y3 = ‘aaabbaaa’
We can see that
x2x1x3 = y2y1y3
Hence, the solution is (2, 1,3). Another solution may be
also (2, 3), (3, 2).
Ex. Find whether the lists X = (b, bab3 ,ba) and
Y = (b3, ba, a) have a Post Correspondence Solution?
Solution:
x2x1x1x3 = bab3 b b ba
and y2y1y1y3 = ba b3 b3 a
Therefore the solution will be (2, 1, 1, 3).

Ex. Find whether the lists X = (ab, bab, bbaaa)and

Y = (a, ba, bab) have a Post Correspondence Solution?
Solution:
In this case there is no solution of this problem. Because the
length of each string in Y is less than corresponding string in X.
That is 𝑦𝑖 < 𝑥𝑖 , ∀ 𝑖.
Modified Post correspondence problem (MPCP)
The modified PCP problem over an alphabet ∑ is stated
as follows:−
Given the following two lists, X and Y of non-empty
strings over ∑,
X = (x1, x2, x3,………, xn)
Y = (y1, y2, y3,………, yn)
We can say that there is a Modified Post Correspondence
Solution, if for some (i1,i2,………… ik), where 1 ≤ ij ≤ n, the
condition x1 xi1 xi2 …….xik = y1 yi1 yi2 …….yik satisfies.
 Universal Turing machine(UTM)
 A universal Turing machine (UTM) behaves like a
general purpose computer. Instead of finite size
memory in computer, UTM uses infinite tape.
 UTM is a specified TM that can simulate the behavior
any TM.
 UTM is a Turing machine that accepts universal
language.
 Universal language is defined as:-
UL= { <M,w> ! M is a Turing machine that accepts input
string w.} Desciption of
TM Accept,
UTM Reject,
w Goes into infinite loop
Universal Turing machine(UTM)
Input to UTM:
Description of TM
Input string
Action of UTM:
Simulate TM
Behave like TM
UTM as Computer
TM as Program
UTM is a recognizer but not a decider.
UTM takes an encoding of a TM and the input data as its
input in its tape and behaves as that TM on the input data.
 Church-Turing Thesis
 It states that if there exists an algorithm to solve a
problem then there exists a Turing machine to solve
that problem and vice-versa.
 It states that a function on the natural numbers can be
computed by an algorithm if and only if it is
computable by a Turing machine.
 A problem can be solved by an algorithm iff it can be
solved by a Turing Machine.
 Algorithm Turing machine
 Halting Problem
Statement: Given Turing machine M and input string w,
is it possible to determine whether the machine will
ever halt on given input string?

In another words, the halting problem is the problem

of determining, from a description of an arbitrary
computer program and an input, whether the program
will finish running, or continue to run forever.

Halt: the machine will stop or halt at final or non-final

state after finite number steps.
No halt: Machine will never stop or halt.
Decidable or Undecidable Problem
 A problem is said to be decidable if there exists an
algorithm which can decide the problem in finite
amount of time.
 In this type of problems, the output of the algorithm
will be yes/no i.e. the answer of decidable problems is
yes or no.
 A problem is said to be undecidable if there does not
exist an algorithm which can decide the problem in
finite amount of time.
Turing decidable and Turing acceptable language
 A language L is said to be Turing decidable if there
exists a Turing machine which can accepts all strings
belong in to L and rejects all strings which do not
belong into L.
 A language L is said to be Turing acceptable if there
exists a Turing machine which can accepts all strings
belong in to L.
 Some undecidable problems
 Halting problem is undecidabe.
 PCP problem is undecidable.
 Modified PCP problem is undecidable.
 For a CFG G, is L(G) ambiguous ?
 For two arbitrary CFG G1 and G2,
deciding L(G1) L(G2)= φ or not, is undecidable.
Some decidable problems
 For a CFG G, is L(G) = φ or not, is decidable.
 For a CFG G, finding whether L(G) a finite or not, is
decidable.
 For regular language L1 and L2, finding whether
L1 L2 is regular, is decidable.
 Membership problem in CFG is decidable.