Courses

# 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)
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)
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
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)
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
not recognizable)
Decidable     Recognizable
recognizable
decidable
co-
recognizable
?
?
L
D
L
D
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;