szó jelentését keresi. A DICTIOUS-ban nem csak a
szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
szót egyes és többes számban mondani. Minden, amit a
szóról tudni kell, itt található. A
szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
Turing machine (tsz. Turing machines)
- (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.
🧠 1. Mi az a Turing-gép?
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
⚙️ 2. Hivatalos definíció (determinista eset)
A Turing-gépet egy 7-tuple írja le:
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:

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
🖥️ 3. Hogyan működik?
- A gép az első szalagra írt bemenettel indul és az olvasófej az első karakterre mutat.
- 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.
- 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.
📏 4. Mit tud a Turing-gép?
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).
🧩 5. Típusai
- 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)
🧪 6. Példa feladat – bináris szám visszafelé írása
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.
🧾 7. Összefoglalás
- 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.