Language LSelfAcceptance 2/2
40/45
Theorem: LSelfAcceptance is accept by some TM.
Proof (idea):
•We construct a DTM V, which:
1) Replace an input string w = d(M) with d(M)d(M)
2) Simulate an activity of a universal TM U
•Then, L(V) = LSelfAcceptance, thus theorem holds.
Illustration:
D
1
…
Mdouble
1
1
0
…
1
…
D
1
…
1
1
0
…
1
…
1
…
1
1
0
…
1
U
d(M)
w = d(M)
+
V