Language LSelfAcceptance 1/2
39/45
Gist: LSelfAcceptance is
the language over {0, 1}*, which contain a string d(M),
if and only DTM M accepts d(M).
Definition:
LSelfAcceptance = {d(M): M is a DTM, d(M) Î L(M)}
Illustration:
TM M
Description
of M:
d(M) = 1110…1
• Does TM
M accept d(M) = 1110…1
?
D
1
…
TM M
1
1
0
…
1
…
d(M)
d(M) Î LSelfAcceptance
d(M) Ï LSelfAcceptance
YES
NO