Maszyna Turinga

Maszyna Turinga

Przypomijmy sobie teorię autoamtów. Najwyżej w hierarchii stał tam automat MT, który mógł wykonać każdy algorytm. Przedstawiony wówczas automat został wymyślony w 1036 r. przez brytyjskiego matematyka Alana M. Turinga.

Maszyna Turinga składa się z:

1.    skończonego alfabetu symbli

2.    skończonego zbioru stanów

3.    ruchomej nieskończonej taśmy z zaznaczonymi kwadratami (klatkami), z których każdy może zawierać pojedynczy symbol, ruch taśmy odbywa się jednorazowo o jedną klatkę

4.    nieruchomej głowicy odczytująco — zapisującej

5.    diagramu przejść między stanami — (w skrócie diagramu przejść) zawierającego także instrukcje ruchu taśmy

Maszyna ma się zachowywać deterministycznie (jednoznacznie), czyli z jednego stanu nie mogą wychodzić dwa różne przejścia wyzwalane przez ten sam symbol wczytywany na taśmie roboczej (wyzwalacz). Mamy też stan początkowy i jeden lub wiele końcowych, z których nie wychodzą żadne przejścia.

Poprzednio wykorzystaliśmy automat MT do analizy słów pewnego języka. Obecnie omówimy realizację przez MT trzech kolejnych algorytmów:

Przykład 1:

Dzielenie całkowite (t.j. bez reszty) liczby całkowitej dodatniej przez 3.

Dane liczbowe, tak wejściowe jak i wyjściowe będziemy zapisywać za pomocą pałeczek — ilość pałeczek to wartość liczby.

Niech:

MT = ({q, p, r}, {\}, {\ #}, R, q, {q, p, r})

{q. p, r} — zbiór stanów maszyny Q

j\} — alfabet terminalny T (zbiór znaków do budowy danych wejściowych i wyjściowych)

{W} — zbiór znaków (alfabet) na taśmie roboczej lub wejściowej Z R — lista rozkazów (przejść) P q — stan początkowy {q, p, r} — zbiór stanów końcowych F Lista rozkazów:

R = {(q. V (P. #, stop), (p, \, #) -»(r, #, stop), (r, \, #) -»(q, \, lewo)}

Przypominamy interpretację rozkazów:

(p, X, A) -»(r, B, ruch)

(p, X, A) — nieorzeczytana część słowa wejściowego

maszyna zmienia stan z p na r, na tasiemce roboczej A jest zamieniane przez B, po czym następuje ruch taśmy zgodnie z jego opisem w rozkazie.

Działanie:

Dzielną umieszczamy na tasiemce wejściowej, po przeczytaniu całej zawartości tasiemki wejściowej i osiągnięciu stanu końcowego zawartość tasiemki wyjściowej uważamy za wynik działania algorytmu.

Dzielimy 4 przez 3:

(q. M. #) =» (P, \W. ^A#) =» (r,    =» (q. \,\*$) * (P,    \*$)

Czyli otrzymaliśmy wynik 1.