Hodnotenie:
Momentálne nie sú žiadne recenzie čitateľov. Hodnotenie je založené na 2 hlasoch.
A Mathematical Primer on Computability
Kniha poskytuje samostatný úvod do teórie vypočítateľnosti pre pokročilých študentov bakalárskeho štúdia alebo pre začiatok štúdia matematiky a informatiky. Odborný materiál je ilustrovaný množstvom príkladov, úloh s kompletne spracovanými riešeniami, ako aj radom navrhovaných cvičení.
Prvá časť je zameraná na základné pojmy a výsledky vypočítateľnosti, počnúc základnými pojmami výpočtový model (abstraktný vysokoúrovňový programovací jazyk), vypočítateľná funkcia, rozhodnuteľná a vymenovateľná množina, vlastná univerzálna funkcia, rozhodovací problém a redukčná technika na prenos vlastností rozhodnuteľnosti a vymenovateľnosti. Uvádzajú sa a ilustrujú základné výsledky, konkrétne Riceova veta, Riceova-Shapirova veta, Riceova-Shapirova-McNaughtonova-Myhillova veta, ako aj Rogersova veta a veta o rekurzii. Skúma sa redukovateľnosť mnoho k jednej a stupne mnoho k jednej. Súčasťou je aj krátky úvod do výpočtov s veštcami. Zavádzajú sa vypočítateľné aj nevypočítateľné operátory, ako aj monotónne a konečné operátory. Diskutuje sa o vzťahu medzi nimi, najmä prostredníctvom Myhill-Shepherdsonovej vety. Uvádza sa aj Kleeneho veta o najmenšom pevnom bode. Nakoniec sa časť I končí stručnou informáciou o Turingovom výpočtovom modeli, Turingovej redukovateľnosti a Turingových stupňoch.
Druhá časť knihy sa zameriava na aplikácie vypočítateľnosti v niekoľkých oblastiach, konkrétne v logike (nerozhodnuteľnosť aritmetiky, splniteľnosť vo výrokovej logike, rozhodnuteľnosť v modálnej logike), euklidovskej geometrii, grafoch a Kolmogorovovej zložitosti. Napriek tomu sa nevyžadujú žiadne predchádzajúce znalosti týchto predmetov. Uvádzajú sa podstatné podrobnosti na pochopenie aplikácií.