Jazyk LPřijmeSámSebe 2/2
40/45
Tvrzení: LPř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) = LPřijmeSámSebe, tedy tvrzení platí.
Ilustrace:
D
1
…
Mzdvojení
1
1
0
…
1
…
D
1
…
1
1
0
…
1
…
1
…
1
1
0
…
1
U
d(M)
w = d(M)
+
V