A kiszámíthatósági elmélet, más néven rekurzióelmélet, a matematikai logika, a számítástudomány és a számításelmélet egyik ága, amely az 1930-as években alakult ki a kiszámítható függvények és a Turing-fokok tanulmányozásával. A terület azóta kibővült az általánosított kiszámíthatóság és a definiálhatóság vizsgálatával is. Ezeken a területeken a kiszámíthatóság-elmélet átfedésben van a bizonyításelmélettel és az effektív leíró halmazelmélettel.
A kiszámíthatósági elmélet által vizsgált alapvető kérdések közé tartoznak a következők:
Mit jelent az, hogy egy természetes számokon értelmezett függvény kiszámítható? Hogyan osztályozhatók a nem kiszámítható függvények hierarchiába a nem-kiszámíthatóságuk foka alapján?
Bár az ismeretek és a módszerek tekintetében jelentős az átfedés, a matematikai kiszámíthatóság-elmélet kutatói a relatív kiszámíthatóság elméletét, a redukálhatósági fogalmakat és a fokszámszerkezeteket vizsgálják; ezzel szemben a számítástechnika területén dolgozók a szubrekurzív hierarchiák, a formális módszerek és a formális nyelvek elméletére összpontosítanak. Azt a vizsgálatot, hogy mely matematikai konstrukciók végezhetők el hatékonyan, néha rekurzív matematikának nevezik.
Bevezetés A kiszámíthatósági elmélet az 1930-as években jött létre Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene és Emil Post munkásságának köszönhetően.
A kutatók által elért alapvető eredmények megalapozták a Turing-féle kiszámíthatóságot, az effektív kiszámíthatóság intuitív elképzelésének helyes formális megfogalmazásaként. Ezek az eredmények vezették Kleene-t 1952-ben arra, hogy megalkossa a „Church-tézis” és a „Turing-tézis” elnevezéseket. Manapság ezekre gyakran egyetlen hipotézisként a Church–Turing-tézisként hivatkoznak, amely kimondja, hogy minden olyan függvény, amely egy algoritmussal kiszámítható, kiszámítható függvény.
Az effektív kiszámíthatóság definíciójának megszületésével megjelentek az első olyan bizonyítások is, amelyek szerint léteznek olyan problémák a matematikában, amelyeket nem lehet hatékonyan eldönteni. 1936-ban Church és Turing (Gödel hiányossági tételeinek bizonyítására használt technikáira alapozva) egymástól függetlenül bebizonyították, hogy az effektív módon nem dönthető el. Ez az eredmény rávilágított arra, hogy nem létezik olyan algoritmikus eljárás, amely képes lenne helyesen eldönteni tetszőleges matematikai állítások igaz vagy hamis voltát.
Számos matematikai probléma eldönthetetlennek bizonyult ezen kezdeti példák felállítása után. 1947-ben Markov és Post egymástól függetlenül megjelentetett dolgozataikban mutatták meg, hogy a félcsoportokra vonatkozó szöveges probléma nem oldható meg effektíven. Ezt az eredményt kiterjesztve Pjotr Novikov és William Boone az 1950-es években egymástól függetlenül bizonyították be, hogy a csoportokra vonatkozó szöveges probléma nem oldható meg effektíven: nincs olyan effektív eljárás, amely egy végesen ábrázolt csoportban lévő szó esetén eldönti, hogy a szó által reprezentált elem a csoport egységeleme-e. 1970-ben Jurij Matijasevics ( Julia Robinson eredményeit felhasználva) bebizonyította Matijasevics tételét, amelyből az következik, hogy Hilbert tizedik problémájának nincs effektív megoldása; ez a probléma azt vizsgálta, hogy létezik-e effektív eljárás annak eldöntésére, hogy egy egész számok feletti Diofantikus egyenletnek van-e megoldása az egész számokban.
Turing-féle kiszámíthatóság A területen tanulmányozott kiszámíthatóság fő formáját Turing vezette be 1936-ban. A természetes számok egy halmazát kiszámítható halmaznak (más néven eldönthető, rekurzív vagy Turing-féle kiszámítható halmaznak) nevezzük, ha létezik olyan Turing-gép, amely tetszőleges n szám esetén 1 kimenettel áll meg, ha n eleme benne van a halmazban, és 0 kimenettel áll meg, ha n eleme nincs benne a halmazban. A természetes számok halmazán értelmezett és a természetes számok halmazába képező f függvény (Turing-) kiszámítható vagy rekurzív függvény, ha létezik olyan Turing-gép, amely n bemeneten megáll és f ( n ) értékét adja vissza. A Turing-gépek használata itt nem szükséges; számos más számítási modell létezik, amelyek ugyanolyan számítási teljesítménnyel rendelkeznek, mint a Turing-gépek; például a primitív rekurzióból kapott μ-rekurzív függvények és a μ operátor.
A kiszámítható függvények és halmazok terminológiája nem teljesen egységes. A μ-rekurzív függvények definíciója, valamint a rekurzív függvények egy másik, Gödeltől származó definíciója vezetett ahhoz a hagyományos elnevezéshez, hogy a Turing-gép által kiszámítható halmazokat és függvényeket „rekurzívnak” nevezik. Az „eldönthető” (decidable) szó a német Entscheidungsproblem kifejezésből ered, amelyet Turing és kortársai használtak az eredeti publikációikban. A mai szóhasználatban a „kiszámítható függvény” (computable function) kifejezésnek többféle definíciója létezik:Nigel J. Cutland szerint ez egy parciális rekurzív függvény (amely bizonyos bemenetekre lehet értelmezetlen is), mígRobert I. Soare szerint egy totális rekurzív függvény (amely minden bemenetre értelmezve van). Ez a szócikk az utóbbi egyezményt követi. Soare 1996-ban további megjegyzéseket fűzött a terminológiához.
Nem minden természetes számokból álló halmaz kiszámítható. A megállási probléma - amely a 0 bemeneten megálló Turing-gépek (leírásainak) halmaza -, egy jól ismert példa a nem kiszámítható halmazokra. Számos nem kiszámítható halmaz létezése abból a tényből következik, hogy csak megszámlálhatóan sok Turing-gép, és így csak megszámlálhatóan sok kiszámítható halmaz van, de a Cantor-tétel szerint megszámlálhatatlanul sok természetes számhalmaz létezik.
Bár a megállási probléma nem kiszámítható, lehetőség van a programok végrehajtásának szimulációjára, és ezáltal a ténylegesen leálló programok egy végtelen listájának előállítására. Így a megállási probléma egy példa a kiszámíthatóan felsorolható (ce) halmazra, vagyis az olyan halmazokra, amelyek elemei egy Turing-géppel felsorolhatóak (a kiszámíthatóan felsorolható fogalom egyéb elnevezései közé tartozik a rekurzívan felsorolható és a félig eldönthető is). Ezzel egyenértékű módon egy halmaz pontosan akkor kiszámíthatóan felsorolható, ha az megegyezik valamely kiszámítható függvény értékkészletével. A kiszámíthatóan felsorolható halmazokat – bár általánosságban nem eldönthetők – részletesen tanulmányozták a kiszámíthatóság-elméletben.
Kutatási területek A fentiekben bemutatott kiszámítható halmazok és függvények elméletéből kiindulva a kiszámíthatóság-elmélet területe számos, egymással szorosan összefüggő témakör tanulmányozásával bővült ki. Ezek nem egymástól független kutatási területek: mindegyik ág merít a többi terület ötleteiből és eredményeiből, és a legtöbb kiszámíthatóság-elméleti szakember a többségüket behatóan ismeri.
Relatív kiszámíthatóság és a Turing-fokok A kiszámíthatóság-elmélet a matematikai logikában hagyományosan a relatív kiszámíthatóságra összpontosít, amely a Turing által 1939-ben bevezetett, orákulum Turing-gépek definiált Turing-kiszámíthatóság egy általánosítása. Az orákulum Turing-gép egy hipotetikus eszköz, amely a hagyományos Turing-gépek műveleteinek végrehajtása mellett képes kérdéseket feltenni egy orákulumnak, amely természetes számok egy adott halmaza. Az orákulum gép csak "n benne van az orákulum halmazában?" alakú kérdéseket tehet fel. Minden kérdésre azonnal helyes válasz érkezik, még akkor is, ha az orákulum halmaz nem kiszámítható. Így egy nem kiszámítható orákulumú orákulum gép képes lesz olyan halmazokat kiszámítani, amelyeket egy orákulum nélküli Turing-gép nem tud.
Informálisan, egy természetes számok egy A halmaza Turing-redukálható egy B halmazhoz, ha létezik egy orákulumgép, amely helyesen megmondja, hogy a számok szerepelnek-e A-ban, amikor B-t orákulumhalmazként futtatjuk (ebben az esetben az A halmazt (relatíve) kiszámíthatónak is nevezzük B-ből, és rekurzívnak B-ben). Ha egy A halmaz Turing-visszavezethető egy B halmazra, és B Turing-visszavezethető A-ra, akkor a halmazokat azonos Turing-fokúnak (más néven megoldhatatlansági foknak ) nevezzük. Egy halmaz Turing-foka pontosan méri, hogy mennyire kiszámíthatatlan a halmaz.
A nem kiszámítható halmazok természetes példái – beleértve a leállási probléma különböző változatait kódoló számos különféle halmazt – két közös tulajdonsággal rendelkeznek:
Számítógéppel felsorolhatók, és mindegyik lefordítható bármelyik másikra egy sok-egyes redukcióval. Ez azt jelenti, hogy ha adottak az ilyen A és B halmazok, akkor létezik egy olyan totális kiszámítható f függvény, amelyre teljesül, hogy A = { x : f ( x ) ∈ B }. Ezeket a halmazokat sok-egy ekvivalenseknek (vagy m-ekvivalenseknek) nevezzük.
A sok-egy redukálhatóság „erősebb”, mint a Turing-redukálhatóság: ha egy A halmaz sok-egy redukálható egy B halmazra, akkor A egyben Turing-redukálható is B-re, de ez fordítottan nem mindig igaz. Bár a nem kiszámítható halmazok természetes példái mind sok-egy egyenértékűek, lehetséges olyan A és B kiszámíthatóan felsorolható halmazokat konstruálni, amelyekre A Turing redukálható B-re, de nem sok-egy redukálható B-re. Belátható, hogy minden kiszámíthatóan felsorolható halmaz sok-egy redukálható a megállási problémára, így a megállási probléma a legbonyolultabb kiszámíthatóan felsorolható halmaz mind a sok-egy redukálhatóság, mind a Turing-redukálhatóság tekintetében. 1944-ben Post feltette a kérdést, hogy vajon minden kiszámíthatóan felsorolható halmaz vagy kiszámítható, vagy pedig Turing-ekvivalens-e a megállási problémával – azaz létezik-e olyan kiszámíthatóan felsorolható halmaz, amelynek Turing-foka a kettő között helyezkedik el.
Köztes eredményként Post olyan természetes típusú kiszámíthatóan felsorolható halmazokat definiált, mint az egyszerű, hiperegyszerű és hiper-hiper-egyszerű halmazokat. Post megmutatta, hogy ezek a halmazok a sok-egy redukálhatóság tekintetében szigorúan a kiszámítható halmazok és a megállási probléma között helyezkednek el. Azt is igazolta, hogy némelyikük szigorúan köztes helyzetű más, a Turing-redukálhatóságnál erősebb redukciófogalmak szerint is. Post azonban nyitva hagyta a fő kérdést, vagyis a köztes Turing-fokú, kiszámíthatóan felsorolható halmazok létezését; ez a kérdés Post problémájaként vált ismertté. Tíz évvel később, 1954-ben Kleene és Post megmutatták, hogy léteznek köztes Turing-fokok a kiszámítható halmazok és a megállási probléma fokai között, de azt nem sikerült igazolniuk, hogy ezen fokok bármelyike tartalmazna kiszámíthatóan felsorolható halmazt. Nem sokkal ezután Friedberg és Muchnik egymástól függetlenül megoldották a Post-problémát azáltal, hogy bebizonyították a köztes fokú, kiszámíthatóan felsorolható halmazok létezését. Ez az áttörést jelentő eredmény tág teret nyitott a kiszámíthatóan felsorolható halmazok Turing-fokainak tanulmányozásának, amelyekről bebizonyosodott, hogy rendkívül bonyolult és nemtriviális struktúrával rendelkeznek.
Megszámlálhatatlanul végtelen sok olyan halmaz létezik, amely nem kiszámíthatóan felsorolható, és az összes halmaz Turing-fokainak vizsgálata éppolyan központi jelentőségű a kiszámíthatóság-elméletben, mint a kiszámíthatóan felsorolható Turing-fokok kutatása. Számos különleges tulajdonságú fokot konstruáltak a kutatók: a hiperimmun-mentes (hyperimmune-free) fokokat, amelyeknél minden az adott fokra nézve relatívan kiszámítható függvényt majorál egy (orákulum nélküli) kiszámítható függvény; a magas (high) fokokat, amelyekre nézve kiszámítható egy olyan f függvény, amely dominál minden kiszámítható g függvényt abban az értelemben, hogy létezik egy g-től függő c konstans úgy, hogy g(x) < f(x) teljesül minden x > c esetén; a véletlen (random) fokokat, amelyek algoritmikusan véletlenszerű halmazokat tartalmaznak; az 1-generikus halmazok 1-generikus fokait; és a határérték-számítható halmazok megállási problémája alatti fokokat.