A számíthatóság matematikai alapjai

Olvasói vélemények

Jelenleg nincsenek olvasói vélemények. Az értékelés 2 olvasói szavazat alapján történt.

Eredeti címe:

A Mathematical Primer on Computability

Könyv tartalma:

A könyv önálló bevezetést nyújt a kiszámíthatósági elméletbe a matematika és informatika felsőfokú tanulmányokat folytató, illetve a felsőfokú tanulmányok elején álló hallgatók számára. A szakmai anyagot rengeteg példa, teljesen kidolgozott megoldásokkal ellátott feladatok, valamint számos javasolt feladat illusztrálja.

Az I. rész az alapvető kiszámíthatósági fogalmakra és eredményekre összpontosít, kezdve a számítási modell (egy absztrakt magas szintű programozási nyelv), a kiszámítható függvény, a megdönthető és listázható halmaz, a megfelelő univerzális függvény, a döntési probléma és a megdönthetőségi és listázhatósági tulajdonságok átvitelének redukciós technikájával. Bemutatjuk és illusztráljuk az alapvető eredményeket, nevezetesen a Rice-tételt, a Rice-Shapiro-tételt, a Rice-Shapiro-McNaughton-Myhill-tételt, valamint a Rogers-tételt és a rekurziós tételt. Vizsgáljuk a sok-egyhez redukálhatóságot és a sok-egyhez fokozatokat. Rövid bevezetést adunk az orákulumokkal való számításba is. Bemutatjuk a kiszámítható és a nem kiszámítható operátorokat, valamint a monoton és véges operátorokat. A közöttük lévő kapcsolatot tárgyaljuk, különösen a Myhill-Shepherdson-tételen keresztül. A Kleene-féle legkisebb fixpont-tételt is bemutatjuk. Végül az I. rész a Turing-számítási modell, a Turing-redukálhatóság és a Turing-fokozatok rövid ismertetésével zárul.

A könyv II. része a kiszámíthatóság alkalmazásaira koncentrál több területen, nevezetesen a logikában (az aritmetika eldönthetősége, kielégíthetőség az állítólagos logikában, eldönthetőség a modális logikában), az euklideszi geometriában, a gráfokban és a Kolmogorov-féle komplexitásban. Mindazonáltal nem szükséges előzetes ismeretekkel rendelkezni ezekben a témakörökben. Az alkalmazások megértéséhez szükséges alapvető részleteket közöljük.