Language
L
SelfAcceptance
2/2
4
0/45
Theorem:
L
SelfAcceptance
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
) =
L
SelfAcceptance
, thus theorem holds.
Illustration:
D
1
…
M
double
1
1
0
…
1
…
D
1
…
1
1
0
…
1
…
1
…
1
1
0
…
1
U
d
(
M
)
w
=
d
(
M
)
+
V