Wprowadzenie do maszyny Turinga
Maszyna Turinga to urządzenie akceptujące, które akceptuje języki (zestaw rekurencyjnie wyliczalny) generowane przez gramatyki typu 0. Został wynaleziony w 1936 roku przez Alana Turinga.
Definicja
Maszyna Turinga (TM) to model matematyczny składający się z taśmy o nieskończonej długości, podzielonej na komórki, na których podawane są dane wejściowe. Składa się z głowicy odczytującej taśmę wejściową. Rejestr stanu przechowuje stan maszyny Turinga. Po odczytaniu symbolu wejściowego jest zastępowany innym symbolem, zmienia się jego stan wewnętrzny i przechodzi z jednej komórki w prawo lub w lewo. Jeśli TM osiągnie stan końcowy, ciąg wejściowy jest akceptowany, w przeciwnym razie odrzucany.
TM można formalnie opisać jako 7-krotkę (Q, X, ∑, δ, q 0 , B, F), gdzie -
Q jest skończonym zbiorem stanów
X to alfabet taśmy
∑ jest alfabetem wejściowym
δjest funkcją przejścia; δ: Q × X → Q × X × {Przesunięcie_ w lewo, Przesunięcie_ w prawo}.
q0 jest stanem początkowym
B jest pustym symbolem
F jest zbiorem stanów końcowych
Porównanie z poprzednim automatem
Poniższa tabela przedstawia porównanie różnic między maszyną Turinga a automatem skończonym i automatem przesuwającym.
| Maszyna | Struktura danych stosu | Deterministyczne? |
|---|---|---|
| Automat skończony | NA | 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, ∑, δ, q 0 , B, F) z
- Q = {q 0 , q 1 , q 2 , q f }
- X = {a, b}
- ∑ = {1}
- q 0 = {q 0 }
- B = pusty symbol
- F = {q f }
δ jest podane przez -
| Symbol alfabetu taśmy | Stan obecny „q 0 ” | Stan obecny „q 1 ” | Stan obecny „q 2 ” |
|---|---|---|---|
| za | 1Rq 1 | 1Lq 0 | 1Lq f |
| b | 1Lq 2 | 1Rq 1 | 1Rq f |
Tutaj przejście 1Rq 1 oznacza, że symbol zapisu to 1, taśma przesuwa się w prawo, a następny stan to q 1 . Podobnie, przejście 1Lq 2 oznacza, że symbolem zapisu jest 1, taśma przesuwa się w lewo, a następny stan to q 2 .
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 inicjowana dla niektórych symboli wejściowych, a złożoność przestrzeni to liczba komórek zapisanych na taśmie.
Złożoność czasowa wszystkie rozsądne funkcje -
T(n) = O(n log n)
Złożoność przestrzeni TM -
S(n) = O(n)