Decidability in Turing Machine

Decidable/Undecidable problems
B.Tech IV Semester

Nisha Vasudeva
Assistant Professor
Department of Computer Science Engineering & Information Technology
Arya College of Engineering & I.T.
 Decidability vs. Undecidability
• There are two types of TMs (based on halting):
(Recursive)
TMs that always halt, no matter accepting or non-accepting 
DECIDABLE PROBLEMS
(Recursively enumerable)
TMs that are guaranteed to halt only on acceptance. If non-
accepting, it may or may not halt (i.e., could loop forever).

• Undecidability:
– Undecidable problems are those that are not recursive

Arya College of Engg. & I.T 2

 Recursive, RE, Undecidable languages

No TMs exist
TMs that always halt
LBA
Non-RE Languages TMs that may or
all other languages for which may not halt
no TMs can be built)

Enumerable (RE)
Recursively
sensitive
Context-

Context
Regular

Recursive
(DFA)
free
(PDA)

“Decidable” problems “Undecidable”

Arya College of Engg. & I.Tproblems 3
 Recursive Languages &
Recursively Enumerable (RE) languages

• Any TM for a Recursive language is going to

look like this:
“accept”
w M
“reject”

• Any TM for a Recursively Enumerable (RE)

language is going to look like this:
“accept”
w M
Arya College of Engg. & I.T 4
 Deciding: Definition
• Let T = (Q, , , , s) be a TM.
• T decides a language L* if T computes the
characteristic function of L.
• T decides a language L* if
– for any string w in L, T halts on w with output 1,
– for any string w inL, T halts on w with output 0.

Arya College of Engg. & I.T 5

 Accepting/Deciding: Example
S
TM decidinging
accepting L={0
L={01010|n0}
n n n n
|n0}

/@,R
0/,L
/,L 1/,L Hang when
/,L
input = 02n
/,L 1/,R
r1 p1 q1
Hang when input
@/,R

@/,R
,

0/,R

0/0,L = 0n 1 … 0n+m
/

1/1,L
0/0,R If the input x is in L,
r2 p4 p2 1/1,R q2
T halts with output 1.
If the input x is not in L,
/1,L
/0,L

/,L
 ,L

T hangs.
0 /

1/,L
/,L p3 h Hang when input
h
= 0n+m …0n
Arya College of Engg. & I.T 6
Recursively enumerable languages
• A language L is recursively enumerable if
there is a Turing machine T accepting L.
• A language L is Turing-acceptable if there is a
Turing machine T accepting L.
• Example:
{0n10n|n0} is a recursively-enumerable
language.

Arya College of Engg. & I.T 7

 Recursive languages
• A language L is recursive if there is a Turing
machine T deciding L.
• A language L is Turing-decidable if there is a
Turing machine T deciding L.
• Example:
{0n10n|n0} is a recursive language.

Arya College of Engg. & I.T 8

Closure Properties of the Class of
Recursive Languages
 Closure Property Under Complementation

Theorem: Let L be a recursive language over .

Then,L is recursive.
Proof:
Let L be a recursive language over .
Then, there exists a TM T computing L.
Construct a tape TM M computing L. as follows:
 T  TmoveRight 0 Twrite1
1
Twrite0

Then,L is recursive.
Arya College of Engg. & I.T 10
 Recursive Languages are closed
under complementation
– If L is Recursive, L is also Recursive

M
“accept” “accept”
w M
w “reject” “reject”

Arya College of Engg. & I.T 11

Are Recursively Enumerable Languages
closed under complementation? (NO)
– If L is RE, L need not be RE

M
“accept” “accept”?
w M
w “reject”
?

Arya College of Engg. & I.T 12

 Closure Property Under Union

Theorem: Let L1 and L2 be recursive languages over

. Then, L1L2 is recursive.
Proof:
Let L1 and L2 be recursive languages over .
Then, there exist TM’s T1 and T2 computing L1 and
L2, respectively.
Construct a 2-tape TM M as follows:
® TcopyTape1ToTape2  T1  TmoveRight 0 TcopyTape2ToTape1  T2
1

Arya College of Engg. & I.T 13

 Closure Property Under Union
® TcopyTape1ToTape2  T1  TmoveRight 0 TcopyTape2ToTape1  T2

If the input w is not in L1 and L2, L1(w) and L2(w)=0.

Thus, both T1 and T2 must run, and M halts with
output 0.
If the input w is in L1, L1(w)=1. Thus, M halts with
output 1.
If the input w is not in L1 but is in L2, L1(w)=0 and
L2(w)=1. Thus, M halts with output 1.
That is, M computes characteristic function of L.
Then, L1L2 is recursive. Arya College of Engg. & I.T 14
 Closure Property Under Intersection

Theorem: Let L1 and L2 be recursive languages over

. Then, L1L2 is recursive.
Proof:
Let L1 and L2 be recursive languages over .
Then, there exist TM’s T1 and T2 computing L1 and
L2, respectively.
Construct a 2-tape TM M as follows:
® TcopyTape1ToTape2  T1  TmoveRight 1 TcopyTape2ToTape1  T2
0

Arya College of Engg. & I.T 15

 Closure Property Under Intersection

 TcopyTape1ToTape2  T1  TmoveRight 1 TcopyTape2ToTape1  T2

If the input w is in L1L2, L1(w) and L2(w)=1. Thus, M halts

with output 1.
If the input w is not in L1, L1(w)=0. Thus, M halts with output 0.
If the input w is in L1 but is not in L2, L1(w)=1 and L2(w)=0.
Thus, M halts with output 0.
That is, M computes characteristic function of L1L2.

Then, L1L2 is recursive.

Arya College of Engg. & I.T 16

 Closure Properties of the Class of
Recursively Enumerable Languages
 Closure Property Under Union

Theorem: Let L1 and L2 be recursively enumerable

languages over . Then, L1L2 is also recursively
enumerable.
Proof:
Let L1 and L2 be recursively enumerable languages
over .
Then, there exist TM’s T1 and T2 accepting L1 and L2,
respectively.
S T1
Construct an NTM M as follows.
T2

Arya College of Engg. & I.T 18

 Closure Property Under Union
S T1
T2
If w is in L1, but not in L2, then T1 in M runs and halts.
If w is in not L1, but in L2, then T2 in M runs and halts.
If w is in both L1 and L2, then either T1 or T2 runs and halts.
For these 3 cases, M halts.
If w is neither in L1 nor in L2, then either T1 or T2 runs
but both never halt. Then, M does not halt.
Thus, M accepts L1L2. That is, L1L2 is recursively
enumerable.
Arya College of Engg. & I.T 19
 Closure Property Under Intersection

Theorem: Let L1 and L2 be recursively enumerable

languages over . Then, L1L2 is also recursively
enumerable.
Proof:
Let L1 and L2 be recursively enumerable languages
over .
Then, there exist TM’s T1 and T2 accepting L1 and L2,
respectively.
Construct an NTM M as follows.
 TcopyTape1ToTape2  T1  TmoveRight 1 TcopyTape2ToTape1  T2

Arya College of Engg. & I.T 20

 Closure Property Under Intersection

 TcopyTape1ToTape2  T1  TmoveRight 1 TcopyTape2ToTape1  T2

If w is in not L1, then T1 in M does not halt. Then, M does

not halt.
If w is in L1, but not in L2, then T1 in M halts and T2 can
finally start, but does not halt. Then, M does not halt.
If w is in both L1 and L2, then T1 in M halts and T2 can
finally start, and finally halt. Then, M halts.
Thus, M accepts L1L2. That is, L1L2 is recursively
enumerable.
Arya College of Engg. & I.T 21
 Closure Property Under Union (II)

Theorem: Let L1 and L2 be recursively enumerable

languages over . Then, L1L2 is also recursively
enumerable.
Proof:
Let L1 and L2 be recursively enumerable languages over .
Then, there exist DTM’s T1 =(Q1, , , 1, s1) and T2 =(Q2,
, , 2, s2) accepting L1 and L2, respectively.
Construct a 2-tape TM M which simulates T1 and T2
simultaneously. Tape 1 represents T1’s tape and Tape 2
represents T2’s tape. Arya College of Engg. & I.T 22
 Closure Property Under Union (II)
Let M = (Q1Q2, , , , (s1,s2)) where
– ((p1,p2),a1,a2) = ((q1,q2),b1,b2,d1,d2) for
1(p1,a1)=(q1,b1,d1) and 2(p2,a2 )=(q2,b2,d2)
– ((p1,p2),a1,a2) = (h,b1,b2,d1,d2) for 1(p1,a1)=(h,b1,d1) or
2(p2,a2 )=(h,b2,d2)

If either T1 or T2 halt, M finally gets to the state h.

If neither T1 nor T2 halt, M never gets to the state h.

Arya College of Engg. & I.T 23

 Closure Property Under Intersection (II)

Theorem: Let L1 and L2 be recursively enumerable

languages over . Then, L1L2 is also recursively
enumerable.
Proof:
Let L1 and L2 be recursively enumerable languages over .
Then, there exist DTM’s T1 =(Q1, , , 1, s1) and T2 =(Q2,
, , 2, s2) accepting L1 and L2, respectively.
Construct a 2-tape TM M which simulates T1 and T2
simultaneously. Tape 1 represents T1’s tape and Tape 2
represents T2’s tape.
Arya College of Engg. & I.T 24
 Closure Property Under Intersection (II)
Let M = ((Q1{h})(Q2{h}), , , , (s1,s2)) where
– ((p1,p2),a1,a2) = ((q1,q2),b1,b2,d1,d2) for 1(p1,a1)=(q1,b1,d1)
and 2(p2,a2 )=(q2,b2,d2)
– ((h,p2),a1,a2) = ((h,q2),a1,b2,S,d2) for all p2,a1,a2 and
2(p2,a2)=(q2,b2,d2)
– ((p1,h),a1,a2) = ((q1,h),b1,a2,d1,S) for all p1,a1,a2 and
1(p1,a1)=(q1,b1,d1)
– ((h,h),a1,a2) = (h,a1,a2,S,S) for all a1,a2
If neither T1 nor T2 halt, M never gets to the state h.
If T1 halts and T2 does not halt, M gets to the state (h,p).
If T2 halts and T1 does not halt, M gets to the state (p,h).
If both T1 and T2 halt, M finally gets to the state h.
Arya College of Engg. & I.T 25
Relationship Between the Classes of
Recursively Enumerable and
Recursive Languages
 Relationship between RE and Recursive
Languages
Theorem: If L is a recursive language, then L is
recursively enumerable.
Proof:
Let L be a recursive language over .
Then, there is a TM T deciding L.
Then, T also accepts L.
Thus, L is recursively enumerable.

Arya College of Engg. & I.T 27

 Relationship between RE and Recursive
Languages
Theorem: Let L be a language. If L andL are recursively
enumerable, then L is recursive.
Proof:
Let L andL be recursively-enumerable languages over .
Then, there are a TM T accepting L, and a TMT acceptingL.
For any string w in *, w is either in L or inL.
That is, either T orT must halt on w, for any w in *.
We construct an NTM M as follows: S T accept
If w is in L, T halts on w and thus, M accepts w.
T reject
If w is not in L,T halts on w and thus, M rejects w.
Then, M computes the characteristic function of L. Then, L is
recursive.
Arya College of Engg. & I.T 28
Thank You

Arya College of Engg. & I.T 29