Maszyna Turinga to urządzenie akceptujące języki (zbiór rekurencyjnie wyliczalny) generowane przez gramatyki typu 0. Została wynaleziona w 1936 roku przez Alana Turinga.
Definicja
Maszyna Turinga (TM) jest modelem matematycznym, który składa się z nieskończonej długości taśmy podzielonej na komórki, na które podawane są dane wejściowe. Składa się z głowicy, która odczytuje taśmę wejściową. Rejestr stanu przechowuje stan maszyny Turinga. Po odczytaniu symbolu wejściowego jest on zastępowany innym symbolem, jej stan wewnętrzny ulega zmianie, a ona sama przesuwa się z jednej komórki w prawo lub w lewo. Jeśli TM osiągnie stan końcowy, to łańcuch wejściowy jest akceptowany, w przeciwnym razie odrzucany.
TM może być formalnie opisana jako 7-tuple (Q, X, ∑, δ, q0, B, F) gdzie –
-
Q jest skończonym zbiorem stanów
-
X jest alfabetem taśmy
-
∑ jest alfabetem wejścia
-
δ jest funkcją przejścia; δ : Q × X → Q × X × {Left_shift, Right_shift}.
-
q0 jest stanem początkowym
-
B jest symbolem pustym
-
F jest zbiorem stanów końcowych
Porównanie z poprzednim automatem
Poniższa tabela przedstawia porównanie czym różni się automat Turinga od automatu skończonego i automatu wypychającego.
| Maszyna | Stack Data Structure | Deterministic? |
|---|---|---|
| Finite Automaton | N.A | Tak |
| Pushdown Automaton | Last In First Out(LIFO) | Nie |
| Maszyna Turinga | Nieskończona taśma | Tak |
Przykład maszyny Turinga
Maszyna Turinga M = (Q, X, ∑, δ, q0, B, F) with
- Q = {q0, q1, q2, qf}
- X = {a, b}
- ∑ = {1}
- q0 = {q0}
- B = symbol pusty
- F = {qf }
δ jest dany przez –
| Symbol alfabetu taśmowego | Obecny stan 'q0′ | Obecny Państwo 'q1′ | Present Państwo 'q2′ |
|---|---|---|---|
| a | 1Rq1 | 1Lq0 | 1Lqf |
| b | 1Lq2 | 1Rq1 | 1Rqf |
Tutaj przejście 1Rq1 oznacza, że symbolem zapisu jest 1, taśma przesuwa się w prawo, a następnym stanem jest q1. Podobnie, przejście 1Lq2 implikuje, że symbol zapisu wynosi 1, taśma przesuwa się w lewo, a następny stan to q2.
Złożoność czasowa i przestrzenna maszyny Turinga
W przypadku maszyny Turinga, złożoność czasowa odnosi się do miary liczby ruchów taśmy, gdy maszyna jest inicjalizowana dla pewnych symboli wejściowych, a złożoność przestrzenna jest liczbą komórek taśmy zapisanej.
Złożoność czasowa wszystkie rozsądne funkcje –
T(n) = O(n log n)
Złożoność przestrzennaTM. –
S(n) = O(n)