Un abecedar matematic asupra calculabilității

Recenzii ale cititorilor

În prezent, nu există recenzii ale cititorilor. Evaluarea se bazează pe 2 voturi.

Titlul original:

A Mathematical Primer on Computability

Conținutul cărții:

Cartea oferă o introducere de sine stătătoare în teoria calculabilității pentru studenții avansați de licență sau absolvenți timpurii de matematică și informatică. Materialul tehnic este ilustrat cu o mulțime de exemple, probleme cu soluții complet elaborate, precum și o serie de exerciții propuse.

Partea I este centrată pe noțiunile și rezultatele fundamentale ale calculabilității, începând cu conceptele de bază ale modelului computațional (un limbaj abstract de programare la nivel înalt), funcția calculabilă, setul decidabil și listabil, funcția universală proprie, problema deciziei și tehnica de reducere pentru transferul proprietăților de decidabilitate și listabilitate. Sunt prezentate și ilustrate rezultatele esențiale, și anume Teorema lui Rice, Teorema lui Rice-Shapiro, Teorema lui Rice-Shapiro-McNaughton-Myhill, precum și Teorema lui Rogers și Teorema recursivității. Sunt analizate reductibilitatea și gradele „mulți la unu”. De asemenea, este inclusă o scurtă introducere în calculul cu oracole. Sunt introduși operatorii calculabili și necalculabili, precum și operatorii monotoni și finitari. Se discută relația dintre aceștia, în special prin intermediul teoremei lui Myhill-Shepherdson. De asemenea, este prezentată Teorema punctului fix cel mai mic a lui Kleene. În cele din urmă, partea I se încheie cu o prezentare succintă a modelului de calcul Turing, a reductibilității Turing și a gradelor Turing.

Partea a II-a a cărții se concentrează pe aplicațiile calculabilității în mai multe domenii, și anume în logică (indecidabilitatea aritmeticii, satisfiabilitatea în logica propozițională, decidabilitatea în logica modală), geometria euclidiană, grafurile și complexitatea Kolmogorov. Cu toate acestea, nu este necesară nicio cunoaștere prealabilă a acestor subiecte. Sunt furnizate detaliile esențiale pentru înțelegerea aplicațiilor.