The Acceptance Problem for TMs Engineering Mathematics Notes | EduRev

Engineering Mathematics : The Acceptance Problem for TMs Engineering Mathematics Notes | EduRev

 Page 1


Lecture 6
Page 2


Lecture 6
The Acceptance Problem for TMs
A
TM
 = { <M,w> | M  is a TM & w ? L(M) }
Theorem:  A
TM
 is T uring recognizable
Pf: It is recognized by a TM U that, on input <M,w>, simulates 
M on w step by step.  U accepts iff M does.   ?
U is called a Universal Turing Machine
(Ancestor of the stored-program computer)
Note that U is a recognizer, not a decider.
Page 3


Lecture 6
The Acceptance Problem for TMs
A
TM
 = { <M,w> | M  is a TM & w ? L(M) }
Theorem:  A
TM
 is T uring recognizable
Pf: It is recognized by a TM U that, on input <M,w>, simulates 
M on w step by step.  U accepts iff M does.   ?
U is called a Universal Turing Machine
(Ancestor of the stored-program computer)
Note that U is a recognizer, not a decider.
A
TM
 is Undecidable
A
TM
 = { <M,w> | M  is a TM & w ? L(M) }
Suppose it’s decidable, say by TM H.  Build a new TM D:
“on input <M> (a TM), run H on <M,<M>>; when it 
halts, halt & do the opposite, i.e. accept if H rejects 
and vice versa”
D accepts <M> iff H rejects <M,<M>>    (by construction)
                        iff M rejects <M>           (H recognizes A
TM
)
D accepts <D> iff D rejects <D>            (special case)
Contradiction!
Page 4


Lecture 6
The Acceptance Problem for TMs
A
TM
 = { <M,w> | M  is a TM & w ? L(M) }
Theorem:  A
TM
 is T uring recognizable
Pf: It is recognized by a TM U that, on input <M,w>, simulates 
M on w step by step.  U accepts iff M does.   ?
U is called a Universal Turing Machine
(Ancestor of the stored-program computer)
Note that U is a recognizer, not a decider.
A
TM
 is Undecidable
A
TM
 = { <M,w> | M  is a TM & w ? L(M) }
Suppose it’s decidable, say by TM H.  Build a new TM D:
“on input <M> (a TM), run H on <M,<M>>; when it 
halts, halt & do the opposite, i.e. accept if H rejects 
and vice versa”
D accepts <M> iff H rejects <M,<M>>    (by construction)
                        iff M rejects <M>           (H recognizes A
TM
)
D accepts <D> iff D rejects <D>            (special case)
Contradiction!
Let M
i
 be the TM 
encoded by w
i
, i.e. 
<M
i
> = w
i
(M
i 
= some default machine, if 
w
i
 is an illegal code.)
i, j entry tells whether 
M
i
 accepts w
j
Then L
D
 is not recognized 
by any TM
A speci?c non-T uring-
recognizable language
w
1
1
w
2
w
3
w
4
w
5
w
6
<M
1
>
>
<M
2
>
<M
3
>
<M
4
>
<M
5
>
<M
6
>
0 0 0 0 0 0
1 1 1 1 1 1
0 1 0 1 0 1
0 1 0 0 0 0
1 1 1 0 0 0
0 1 0 0 0 1
L
D
1 0 1 1 1 0 ...
...
...
...
Note:  The above TM D, if 
it existed, would recognize 
exactly the language L
D
 
de?ned in this 
diagonalization proof 
(which we already know is 
not recognizable)
Page 5


Lecture 6
The Acceptance Problem for TMs
A
TM
 = { <M,w> | M  is a TM & w ? L(M) }
Theorem:  A
TM
 is T uring recognizable
Pf: It is recognized by a TM U that, on input <M,w>, simulates 
M on w step by step.  U accepts iff M does.   ?
U is called a Universal Turing Machine
(Ancestor of the stored-program computer)
Note that U is a recognizer, not a decider.
A
TM
 is Undecidable
A
TM
 = { <M,w> | M  is a TM & w ? L(M) }
Suppose it’s decidable, say by TM H.  Build a new TM D:
“on input <M> (a TM), run H on <M,<M>>; when it 
halts, halt & do the opposite, i.e. accept if H rejects 
and vice versa”
D accepts <M> iff H rejects <M,<M>>    (by construction)
                        iff M rejects <M>           (H recognizes A
TM
)
D accepts <D> iff D rejects <D>            (special case)
Contradiction!
Let M
i
 be the TM 
encoded by w
i
, i.e. 
<M
i
> = w
i
(M
i 
= some default machine, if 
w
i
 is an illegal code.)
i, j entry tells whether 
M
i
 accepts w
j
Then L
D
 is not recognized 
by any TM
A speci?c non-T uring-
recognizable language
w
1
1
w
2
w
3
w
4
w
5
w
6
<M
1
>
>
<M
2
>
<M
3
>
<M
4
>
<M
5
>
<M
6
>
0 0 0 0 0 0
1 1 1 1 1 1
0 1 0 1 0 1
0 1 0 0 0 0
1 1 1 0 0 0
0 1 0 0 0 1
L
D
1 0 1 1 1 0 ...
...
...
...
Note:  The above TM D, if 
it existed, would recognize 
exactly the language L
D
 
de?ned in this 
diagonalization proof 
(which we already know is 
not recognizable)
Decidable     Recognizable
recognizable
decidable
co-
recognizable
? 
?
L
D
L
D
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Content Category

Related Searches

Semester Notes

,

Previous Year Questions with Solutions

,

Objective type Questions

,

study material

,

mock tests for examination

,

MCQs

,

The Acceptance Problem for TMs Engineering Mathematics Notes | EduRev

,

Sample Paper

,

pdf

,

Extra Questions

,

ppt

,

video lectures

,

Free

,

Exam

,

Summary

,

Viva Questions

,

shortcuts and tricks

,

past year papers

,

practice quizzes

,

The Acceptance Problem for TMs Engineering Mathematics Notes | EduRev

,

The Acceptance Problem for TMs Engineering Mathematics Notes | EduRev

,

Important questions

;