Language LNonSelfAcceptance 2/3
42/45
Theorem: LNonSelfAcceptance is accept by no TM.
Proof (by
contradiction):
• Assume that LNonSelfAcceptance is accepted by a TM.
Consider this
infinite table:
…
All TMs
Mi mi = d(Mi) SelfAcceptance(Mi)
111001001001101
11101010111100101
1110010001010001001001
…
…
Note:
• SelfAcceptance(Mi ) = Yes if mi Î LSelfAcceptance
No if mi Ï LSelfAcceptance