Een Turing Machine is een accepterend apparaat dat de talen (recursief telbare verzameling) accepteert die worden gegenereerd door type 0 grammatica’s. Hij werd in 1936 uitgevonden door Alan Turing.
Definitie
Een Turing Machine (TM) is een wiskundig model dat bestaat uit een oneindig lange band, verdeeld in cellen waarop invoer wordt gegeven. Het bestaat uit een kop die de invoerband leest. Een toestandsregister slaat de toestand van de Turing machine op. Na het lezen van een invoersymbool wordt het vervangen door een ander symbool, de interne toestand wordt gewijzigd, en de machine gaat van de ene cel naar rechts of naar links. Als de TM de eindtoestand bereikt, wordt de ingevoerde string geaccepteerd, anders verworpen.
Een TM kan formeel worden beschreven als een 7-tupel (Q, X, ∑, δ, q0, B, F) waarin –
-
Q een eindige reeks toestanden is
-
X het bandalfabet is
-
∑ het invoeralfabet is
-
δ een overgangsfunctie is; δ : Q × X → Q × X × {Left_verschuiving, Rechts_verschuiving}.
-
q0 is de begintoestand
-
B is het blanco symbool
-
F is de verzameling eindtoestanden
Vergelijking met de vorige automaat
De volgende tabel toont een vergelijking van hoe een Turingmachine verschilt van Eindig Automaton en Pushdown Automaton.
| Machine | Stack Datastructuur | Deterministisch? |
|---|---|---|
| Finite Automaton | N.A | Ja |
| Pushdown Automaton | Last In First Out (LIFO) | Nee |
| Turing Machine | Eindeloze band | Ja |
Voorbeeld van Turing machine
Turing machine M = (Q, X, ∑, δ, q0, B, F) met
- Q = {q0, q1, q2, qf}
- X = {a, b}
- ∑ = {1}
- q0 = {q0}
- B = blanco symbool
- F = {qf }
δ wordt gegeven door –
| Tape alfabet symbool | Aanwezige staat ‘q0’ | Aanwezige Staat ‘q1’ | Aanwezige Staat ‘q2’ |
|---|---|---|---|
| a | 1Rq1 | 1Lq0 | 1Lqf |
| b | 1Lq2 | 1Rq1 | 1Rqf |
Hier houdt de overgang 1Rq1 in dat het schrijfsymbool 1 is, de tape beweegt naar rechts, en de volgende toestand is q1. Evenzo impliceert de overgang 1Lq2 dat het schrijfsymbool 1 is, de band naar links beweegt, en de volgende toestand q2 is.
Tijd- en ruimtecomplexiteit van een Turing Machine
Voor een Turing machine verwijst de tijdcomplexiteit naar de maat van het aantal keren dat de band beweegt wanneer de machine wordt geïnitialiseerd voor enkele invoersymbolen, en de ruimtecomplexiteit is het aantal cellen van de band dat wordt geschreven.
Tijdcomplexiteit alle redelijke functies –
T(n) = O(n log n)
TM’s ruimtecomplexiteit –
S(n) = O(n)