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