Turing machine

Turing machine (tsz. Turing machines)

1. (informatika) Turing-gép

A Turing-gép egy elméleti számítógépmodell, amelyet Alan Turing brit matematikus alkotott meg 1936-ban. Ez a modell a számításelmélet alapja, és azt hivatott bemutatni, hogy mi tekinthető kiszámítható műveletnek. A Turing-gép egy egyszerű, absztrakt gép, amely mégis képes bármilyen algoritmus leírására és végrehajtására, amit egy valódi számítógép is képes elvégezni.

Egy Turing-gép egy formális modell, amely meghatározott szabályok alapján műveleteket hajt végre egy szalagon lévő szimbólumokon, miközben egy állapotgép vezérli a működését.

A Turing-gép a következő fő részekből áll:

• Egy végtelen hosszú szalag, amelyen szimbólumokat tárol
• Egy olvasó/író fej, amely egyszerre egy szimbólumot olvas és ír
• Egy állapotmemória, amely a gép aktuális állapotát tartja nyilván
• Egy átmenetfüggvény, amely megmondja, mit tegyen adott szimbólum és állapot esetén

A Turing-gépet egy 7-tuple írja le:

$${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{\text{accept}},q_{\text{reject}})}$$

Ahol:

• Q – A véges állapothalmaz

• Σ – A bemeneti ábécé (nem tartalmazza az üres szimbólumot)

• Γ – A szalagábécé, amely tartalmazza Σ-t és egy speciális üres szimbólumot (pl. ␣ vagy □)

• δ – Az átmenetfüggvény:

  $${\displaystyle \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}}$$

  Ez azt jelenti: olvasott szimbólum alapján → új állapot, szimbólum írása, fej mozgatása

• q₀ – A kezdőállapot

• qₐ𝚌𝚌𝑒𝑝𝑡 – Az elfogadó állapot

• qᵣₑⱼₑ𝒸𝓉 – Az elutasító állapot

1. A gép az első szalagra írt bemenettel indul és az olvasófej az első karakterre mutat.
2. Az aktuális állapot és a szalagon olvasott szimbólum alapján:
   • új állapotba lép,
   • új szimbólumot ír a szalagra,
   • balra vagy jobbra mozgatja az olvasófejet.
3. Ez a folyamat addig ismétlődik, amíg:
   • elfogadó állapotba ér → a bemenetet elfogadja,
   • vagy elutasító állapotba ér → a bemenetet elutasítja,
   • vagy soha nem áll le → végtelen számítás.

A Turing-gép képes:

• Alapvető számítási műveletek (összeadás, kivonás, szorzás) modellezésére
• Logikai döntések szimulálására
• Feltételes elágazásra, ciklusokra
• Bármilyen algoritmus végrehajtására, amit bármilyen valódi számítógép is tud

Ha egy probléma megoldható egy programmal, akkor az megoldható egy Turing-géppel is – ez az egyetemesség elve (Turing-teljesség).

• Deterministic Turing Machine (DTM) – minden lépés pontosan meghatározott
• Nondeterministic Turing Machine (NTM) – lépésenként több lehetőség is megengedett, elméleti modell
• Multitape Turing Machine – több szalaggal és fejjel rendelkezik
• Universal Turing Machine – képes szimulálni bármely más Turing-gépet (elvileg egy teljes számítógép)

Tegyük fel, a bemenet 10110. A Turing-gép célja, hogy a számjegyeket visszafelé írja a szalagra:

• Először elmegy a végére
• Majd karakterenként visszafelé másolja őket egy másik helyre

Ezt a műveletet akár több szalagos Turing-gép is könnyebben el tudja végezni.

• A Turing-gép egy formális és absztrakt számítási modell, amely a modern számítógépek elméleti alapját képezi.
• Meg tud oldani minden olyan problémát, ami algoritmikusan megoldható.
• A Turing-gép az egyik legalapvetőbb fogalom a számíthatóságelméletben, komplexitáselméletben, és a programozáselméletben is.

• Turing machine - Szótár.net (en-hu)
• Turing machine - Sztaki (en-hu)
• Turing machine - Merriam–Webster
• Turing machine - Cambridge
• Turing machine - WordNet
• Turing machine - Яндекс (en-ru)
• Turing machine - Google (en-hu)
• Turing machine - Wikidata
• Turing machine - Wikipédia (angol)