TOiZO

1. Akceptuje język - jeżeli maszyna akceptuje dane słowo wtw gdy należy do języka
2. Rozstrzyga - akceptuje, lub explicite odrzuca
3. Enumerator
   1. Głowica się nie cofa

1. Dowód E=>MT

   Annotations:

   • for y e L(E):   if x = y then accept reject
2. Dowód MT => E

   Annotations:

   • for k = 1 ... niesk    for x e Sigma<=k       if M(x) acc w k krokach then         wylicz x
   1. Dove tailing

1. R - istnieje MT rozstrzygająca
2. RE - istnieje MT akceptująca
3. coRE dopełnienie jezyka e RE
4. R - RE n coRE
5. Właśności -> wykład 2

1. Odwzorowanie MT w alfabecie
2. H Język wszystkich możliwych reprezentacji MT
   1. Język z RE

Annotations:

• Każda MT może być zmodyfikowana tak, by powstała M' akceptująca lub rozstrzygająca ten sam język i mająca dostęp do <M'>

1. funcja obliczalna - q0x |- qyf(x)
2. Redukcja typu many-one
   1. A<=B : xeA => f(x) eB
   2. A<=B i B<=C => A<=C
   3. A<=B i BeR => AeR
   4. A<=B i AnieR => B nieR

1. Balfa - {<M> | L(M)e alfa}
2. Twierdzenie Rice'a

   Annotations:

   • Jeżeli alfa!=zb pustego i alfa!=RE yo Balfa rozstrzygalny