computability theory

Angol

computability theory (tsz. computability theories)

(informatika) Computability theory (számíthatóságelmélet) a számítástudomány és a matematikai logika egyik legmélyebb és legelméletibb ága, amely azt vizsgálja:

Mely problémák oldhatók meg számítógéppel (vagy elméleti géppel), és melyek nem?

Más néven: recursion theory. Ez a terület rakta le az alapjait annak, amit ma „algoritmusokkal megoldhatónak” nevezünk.

Milyen problémákra létezik algoritmus (formális lépéssor)?
Mik azok a problémák, amelyeket nem lehet kiszámítani – azaz nem számíthatók?
Mik a formális modellek, amelyek segítségével vizsgálható, mit tud egy gép kiszámolni?

Modell	Leírás
Turing-gép	Absztrakt gép végtelen szalaggal és szabályrendszerrel
Lambda-kalkulus	Függvények rekurzív alkalmazása
µ-recursive függvények	Primitív és teljes rekurzív függvények halmaza
Register machine	Véges számú regiszter (egyszerűbb gépmodell)

Church–Turing-tézis:

Bármit, amit algoritmusosan kiszámíthatónak gondolunk, az kiszámítható egy Turing-géppel.

Probléma	Miért nem számítható?
Halting problem (leállási probléma)	Nem létezik algoritmus, ami minden programra eldönti, hogy megáll-e
Entscheidungsproblem	Nincs algoritmus, ami minden elsőrendű logikai formula igazságát eldönti
Kolmogorov-komplexitás	Egy string legrövidebb programleírása – nem algoritmikusan kiszámítható
Rice-tétel	Bármilyen nemtriviális tulajdonság egy Turing-gép nyelvéről nem eldönthető

Kategória	Leírás
Eldönthető (decidable)	Létezik algoritmus, ami minden esetben helyesen dönt
Félig eldönthető (semi-decidable)	Létezik algoritmus, ami csak az „igen” válaszra garantál leállást
Nem eldönthető	Még „igen” válaszra sincs algoritmus, ami mindig leállna

Probléma	Eldönthetőség
Egy szám osztható-e 3-mal?	✅ Eldönthető
Egy Turing-gép leáll-e adott bemenetre?	❌ Nem eldönthető
Van-e megoldás egy Diophantoszi egyenletre?	❌ Nem eldönthető (Matiyasevich-tétel)
Egy string legrövidebb kódolása?	❌ Nem eldönthető (Kolmogorov)

Van-e olyan gép, ami bármelyik másik gépről és bemenetről megmondja, hogy az megáll-e?

Alan Turing 1936-ban bebizonyította, hogy nem: Nincs általános algoritmus erre.

Church–Turing-tézis: minden intuitíve kiszámítható függvény kiszámítható Turing-géppel.
Rice-tétel: minden nemtriviális tulajdonság Turing-gép által elfogadott nyelvekre nézve eldönthetetlen.
Gödel-féle nemteljességi tételek: vannak igaz állítások, amelyeket nem lehet bizonyítani a formális rendszeren belül.

Terület	Kérdés
Számíthatóságelmélet	Mi számolható ki egyáltalán?
Komplexitáselmélet	Mennyi időbe/memóriába kerül a számítás?
Automataelmélet	Milyen nyelveket képes felismerni egy adott géptípus?

Fogalom	Leírás
Computability theory	Formálisan vizsgálja a kiszámíthatóság határait
Alapmodell	Turing-gép
Fő kategóriák	Eldönthető, félig eldönthető, nem eldönthető
Híres probléma	Halting problem
Fontos tétel	Rice, Church–Turing, Gödel