8299308014

1.2.2 Maszyny Turinga

Jeśli język jest na tyle skomplikowany, że dla rozpoznania jego słów nie wystarczy już przymierzanie ich do wzorca i potrzebne są obliczenia, to korzystamy z innych modeli.

Najpotężniejszym prostym modelem obliczeń, jakim dysponują matematycy, jest t.zw. maszyna Turinga, zaproponowany przez Alana Turinga wiatach 1930. Można powiedzieć, że składa się ona z automatu skończonego oraz nieskończonego „notesu”, w którym można zapisywać informacje potrzebne do rozpoznawania słów. Potęga maszyn Turinga bierze się właśnie z nieskończoności tego notesu. Tradycyjnie mówi się o nieskończonej w obie strony „taśmie”, którą maszyna może przewijać w przód i w tył, i na której może zapisywać i odczytywać litery.

1.2.2.1 Określenie

Definicja 1.7

Maszyną Turinga nazywamy siódemkę M — (Q,r,.,E,S,qo,F)

gdzie

•    Q jest skończonym zbiorem t.zw. stanów;

•    r jest skończonym zbiorem t.zw. symboli pomocniczych; zbiór T jest zwykle nazywany alfabetem pomocniczym; symbole pomocnicze mogą być zapisywane na taśmie maszyny;

•    .eT jest symbolem pustej klatki; jest to jedyny symbol, który może występować w nieskończenie wielu klatkach taśmy;

•    E C T \ {.} jest skończonym zbiorem t.zw. liter; zbiór E jest zwykle nazywany alfabetem-, akceptowane słowa napisane są literami tego alfabetu;

•    S:QxT—>QxTx {L, R} to częściowa funkcja przejścia maszyny; nieformalnie mówiąc, dla każdego stanu i litery na taśmie pod głowicą wyznacza ona

—    stan wynikowy,

—    symbol, jaki należy napisać na taśmie pod głowicą zamiast symbolu aktualnie obserwowanego,

—    informację, czy głowicę należy przesunąć po taśmie w lewo czy w prawo; ale może też nie dać żadnego wyniku (na tym polega jej częściowość);

•    Qo £ Q jest wyróżnionym stanem początkowym;

•    F C Q jest wyróżnionym zbiorem stanów końcowych lub akceptujących.

Podobnie jak w przypadku automatu skończonego, akceptowanie słów przez maszynę Turinga może być traktowane jak gra, w której pionek porusza się po planszy takiej jak na rys. 1.1. Słowo do sprawdzenia powinno być napisane na taśmie, pozostałe klatki taśmy powinny być puste (wypełnione symbolem .), a głowica ustawiona na pierwszym pustym symbolu po prawej stronie od tego słowa. Jeśli w którymś momencie dojdzie do stanu i litery na taśmie, dla których funkcja przejścia ó nie daje wyniku, to gra się kończy. Jeśli pion pozostaje wtedy w stanie końcowym, to słowo jest zaakceptowane, w przeciwnym przypadku jest niezaakceptowane.

7