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)