Jazyk
L
NepřijmeSámSebe
1/3
4
1/45
Myšlenka:
L
NepřijmeSámSebe
=
L
PřijmeSámSebe
Definice:
L
NepřijmeSámSebe
= {0, 1}
*
–
L
PřijmeSámSebe
TS
M
•
Přijímá
T
S
M
řetězec
d
(
M
) =
1110…1
?
D
1
…
TS
M
1
1
0
…
1
…
d
(
M
)
d
(
M
)
Ï
L
PřijmeSámSebe
d
(
M
)
Î
L
PřijmeSámSebe
ANO
N
E
Zakódování TS
M
:
d
(
M
) =
1110…1