Jazyk
L
PřijmeSámSebe
2/2
4
0/45
Tvrzení:
L
PřijmeSámSebe
je přijímán nějakým TS.
Důkaz
(
myšlenka
)
:
•
Sestrojme
DTS
V
,
který
:
1)
Zdvojí vstupní řetězec na pásce
w
=
d
(
M
)
na
d
(
M
)
d
(
M
)
2)
Odsimuluje činnost univerzálního TS
U
.
•
Potom
,
L
(
V
) =
L
PřijmeSámSebe
, t
edy tvrzení platí
.
Ilustrace:
D
1
…
M
zdvojení
1
1
0
…
1
…
D
1
…
1
1
0
…
1
…
1
…
1
1
0
…
1
U
d
(
M
)
w
=
d
(
M
)
+
V