computability theory (tsz. computability theories)
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.
| 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.
| 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 |