Ugrás a tartalomhoz

Turing completeness

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

Turing completeness (tsz. Turing completenesses)

  1. (informatika) Turing-teljesség (angolul Turing completeness) egy olyan elméleti fogalom a számítástudományban, amely azt írja le, hogy egy formális rendszer vagy programozási nyelv képes-e bármely számítható problémát megoldani, feltéve hogy elegendő idő és memória áll rendelkezésre.

Ez az egyik alapfogalom az algoritmusok és számításelmélet világában, és Alan Turing munkájára vezethető vissza, aki az 1930-as években megalkotta a Turing-gép fogalmát.


🧠 Mi az a Turing-gép?

A Turing-gép egy elméleti számítógépmodell, amely egy végtelen hosszú szalagon (memória), egy olvasó/író fejjel és egy állapotgép vezérléssel működik. A gép képes:

  1. Olvasni egy szimbólumot a szalagról
  2. Állapotától függően új szimbólumot írni
  3. Balra vagy jobbra mozogni a szalagon
  4. Megváltoztatni a belső állapotát

Bár egyszerű, ez a modell képes minden számítható művelet elvégzésére – ezért lett a számításelmélet alapmodellje.


📜 Turing-teljesség definíciója

Egy formális rendszer Turing-teljes, ha:

  • Képes feltételes elágazásra (if/else, goto, jump, stb.)
  • Képes ismétlésre vagy rekurzióra (pl. while, for, recursion)
  • Képes változók és memória kezelésére (akár véges, akár végtelen módon modellezve)

Ha ezek a képességek adottak, akkor a rendszer képes minden számítható probléma megoldására – ugyanazokra a feladatokra, mint egy Turing-gép.


⚙️ Példák Turing-teljes nyelvekre

Nyelv Turing-teljes? Megjegyzés
C, C++, Java, Python, Rust ✅ Teljes funkcionalitású programozási nyelvek
JavaScript, PHP ✅ Magas szintű, webes nyelvek
Brainfuck, Whitespace ✅ Esoteric nyelvek, de elméletileg teljesek
x86 Assembly ✅ Alacsony szintű, de Turing-teljes
SQL (alap) ❌ Nem általános célú, nincs ciklus/rekurzió (egyes dialektusok kivételek)
Regex (klasszikus) ❌ Nem Turing-teljes, nem képes memóriakezelésre
HTML, CSS ❌ Deklaratív nyelvek, nem rendelkeznek vezérlési szerkezettel


🤖 Példák nem Turing-teljes rendszerekre

  • Markdown – csak dokumentumformázás, nincs logikai vezérlés
  • CSS – stílusleírás, nincs ciklus, nincs változó (csak újabban limitált módon)
  • Klasszikus reguláris kifejezések – nem képesek rekurzióra


🔍 Miért fontos a Turing-teljesség?

✅ Elméleti okokból:

  • Meghatározza, hogy egy rendszer általános célú programozási nyelvként működhet-e.
  • Lehetővé teszi algoritmusok teljes körű implementációját.

⚠️ Gyakorlati szempontból:

  • Nem feltétlenül szükséges minden rendszernek Turing-teljesnek lennie (pl. HTML).
  • Bizonyos rendszereket szándékosan nem tesznek Turing-teljessé a biztonság, megbízhatóság vagy determinálhatóság érdekében (pl. sablonnyelvek, beágyazott rendszerek).


🌀 Turing-teljesség paradoxonai

  • Halting Problem: Nincs általános algoritmus, amely eldöntené, hogy egy Turing-teljes program megáll-e vagy végtelen ciklusban fut.
  • Számításelméleti határok: Vannak olyan problémák (pl. Goldbach-sejtés bizonyítása), amelyeket egy Turing-teljes gép sem tud garantáltan megoldani.


🧩 Turing-teljesség és esolangok

Sok esolang célja, hogy megmutassa: még egy extrém módon lebutított (vagy obskúrus) nyelv is lehet Turing-teljes. Pl.:

  • Brainfuck – 8 karakter, mégis teljes
  • Piet – színváltásokon alapuló nyelv, de Turing-teljes
  • Malbolge – szinte írhatatlan, de elméletileg teljes


🧠 Összefoglalás

Fogalom Leírás
Turing-teljesség Egy rendszer képessége bármilyen számítható művelet elvégzésére
Turing-gép Absztrakt számítógépmodell, amely ezt a fogalmat alapozza meg
Elvárások Ciklus/rekurzió, elágazás, változók
Jelentőség Alapja annak, hogy mit nevezünk teljes értékű programozási nyelvnek

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Turing_completeness&oldid=3497922”