Turingova vypočitatelnost: Teorie a aplikace

Recenze čtenářů

Kniha je vyčerpávajícím a inspirativním zkoumáním Turingovy spočitatelnosti, se silným historickým příběhem a autorovou odborností, která je patrná v celém textu. Osloví zejména studenty, kteří usilují o hlubší pochopení teorie spočitatelnosti.

⬤ Inspirativní a vyčerpávající
⬤ podrobný historický kontext
⬤ dobře napsané a poutavé
⬤ vhodné pro studenty, kteří chtějí prohloubit své znalosti
⬤ autor prokazuje jasné odborné znalosti v oboru.

Pro některé čtenáře může být kniha náročná, pokud nejsou s oborem obeznámeni, protože se zdá, že je určena těm, kteří mají předchozí znalosti teorie spočitatelnosti.

(na základě 2 hodnocení čtenářů)

Původní název:

Turing Computability: Theory and Applications

Obsah knihy:

Turing ve svém slavném článku z roku 1936 zavedl formální definici výpočetního stroje, Turingova stroje. Tento model vedl jak k vývoji skutečných počítačů, tak k teorii spočitatelnosti, tedy ke studiu toho, co stroje mohou a nemohou spočítat. Tato kniha představuje klasickou teorii vypočitatelnosti od Turinga a Posta až po současné výsledky a metody a jejich využití při studiu informačního obsahu algebraických struktur, modelů a jejich vztahu k Peanově aritmetice. Autor představuje předmět jako umění, které je třeba praktikovat, a to umění v estetickém smyslu vrozené krásy, kterou všichni matematici ve svém předmětu uznávají.

V první části jsou důkladně rozvedeny základy spočetnosti, od definice Turingových strojů až po argumenty o prioritě konečného zranění. Mezi klíčová témata patří relativní spočitatelnost a spočitatelné množiny, tedy takové, které lze efektivně vypsat, ale ne nutně efektivně rozhodnout, jako jsou věty Peanovy aritmetiky. Část II zahrnuje studium vypočitatelně otevřených a uzavřených množin reálů a bázové a nebázové věty pro efektivně uzavřené množiny. Část III se zabývá minimálními Turingovými stupni. Část IV je úvodem do her a jejich využití při dokazování teorémů. V závěru části V je uvedena stručná historie teorie spočitatelnosti.

Autor zdokonaloval obsah po desetiletí podle zpětné vazby od studentů, přednášejících a výzkumných pracovníků z celého světa. Většina kapitol obsahuje cvičení a látka je pečlivě strukturována podle důležitosti a obtížnosti. Kniha je vhodná pro pokročilé studenty bakalářského a magisterského studia informatiky a matematiky a pro vědecké pracovníky zabývající se vypočitatelností a matematickou logikou.