8299308017

1.2.2.2 Maszyny Turinga jako akceptory

Automat skończony w każdym kroku pracy „zjada” jedną literę z wejścia, a gdy „zje” wszystkie, to się zatrzymuje. Natomiast krok pracy maszyny Turinga może zmniejszyć liczbę symboli na taśmie przez zamianę którejś na symbol pusty, ale może też ją powiększyć przez zamianę symbolu pustego na niepusty. W dodatku jej zatrzymywanie nie jest związane z wyczerpaniem liter — nawet po całkiem pustej taśmie¹ maszyna może nadal się poruszać. Wobec tego maszynie Turinga może się przydarzyć, że sprawdzanie słowa nigdy się nie zakończy („ślepa pętla”). Ten fakt trzeba wziąć pod uwagę przy klasyfikowaniu języków ze względu na działania maszyn Turinga.

Definicja 1.10

Zbiór słów £CS* nazywamy językiem rekurencyjnie przeliczalnym, jeśli istnieje maszyna Turinga M taka, że £ = L(M). Zbiór słów £ C E* nazywamy językiem rekurencyjnym jeśli istnieją maszyny Turinga M⁺ i M~ takie, że

£ = L(M⁺) i E* \ £ = L(M~)

O różnicy między językami rekurencyjnymi i rekurencyjnie przeliczalnymi zostanie powiedziane niżej. Na razie wystarczy zauważyć, że każdy język rekurencyjny jest rekurencyjnie przeliczalny.

Zajmijmy się teraz związkami języków rekurencyjnych z językami regularnymi, czyli językami automatów. Poniższe twierdzenie i następujący po nim przykład pokazują, że maszyny Turinga są potężniejszym narzędziem do akceptowania języków niż automaty skończone:

Twierdzenie 1.11

Dla każdego automatu skończonego A istnieją maszyny Turinga M⁺ i M~ takie, że L(A) = L(M⁺) i E* \ L(A) = L(M~)

Przykład 1.12

Maszyna Turinga z przykładu 1.8 określa język

{o*6^fc | fe > o}

o którego nieregularności już wiemy (por. przykład 1.5).

Nietrudno zmienić ją na maszynę akceptującą uzupełnienie tego języka (zamienić stany akceptujące na nieakceptujące i odwrotnie). Wobec tego ten język jest rekurencyjny.

□

Wniosek 1.13

Każdy język regularny jest rekurencyjny. Nie każdy język rekurencyjny jest regularny.

10

1

Czyli wypełnionej symbolami pustymi .