Vypočitatelnost a neřešitelnost

Recenze čtenářů

Kniha Martina Davise „Computability and Unsolvability“ (Vypočitatelnost a neřešitelnost) poskytuje formální a důkladné pojednání o teorii vypočitatelnosti a jejích důsledcích v matematice a informatice. Ačkoli byla oceněna pro svou hloubku a důkladnost, mnoho čtenářů upozornilo na její náročný zápis a nedostatek konkrétních příkladů, což ji činí méně přístupnou pro ty, kteří nemají silné matematické zázemí.

⬤ Komplexní a důkladné pojednání o teorii vypočitatelnosti a rekurzivních funkcí.
⬤ Dobře uspořádaná struktura; věty jsou efektivně propojeny.
⬤ Cenný obsah týkající se hlubokých otázek o vypočitatelnosti a Hilbertově desátém problému.
⬤ Cenově dostupný dotisk z nakladatelství Dover.

⬤ Vysoce formální styl, který může být obtížný pro čtenáře, kteří nejsou dobře zběhlí v matematice.
⬤ Chybí konkrétní příklady k ilustraci pojmů.
⬤ Důkazy mohou působit zdlouhavě a mohou vynechávat kroky nezbytné pro pochopení.
⬤ Některé části jsou kritizovány za suchost nebo neživotnost.

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

Původní název:

Computability and Unsolvability

Obsah knihy:

V tomto klasickém textu Dr. Davis poskytuje srozumitelný úvod do výpočetní techniky na úrovni pokročilého studenta, který slouží potřebám odborníků i laiků.

V první části (kapitoly 1-5) profesor Davis nastiňuje obecnou teorii spočitatelnosti a probírá témata, jako jsou spočitatelné funkce, operace na spočitatelných funkcích, rekurzivní funkce, Turingovy stroje, samoúčelné a neřešitelné rozhodovací problémy. Autor se zejména v prvních sedmi kapitolách snažil nepředpokládat žádné zvláštní matematické vzdělání čtenáře.

Druhá část (kapitoly 6-8) obsahuje stručné pojednání o aplikacích obecné teorie, zahrnující materiál o kombinatorických problémech, diofantických rovnicích (včetně Hilbertova desátého problému) a matematické logice. Závěrečné tři kapitoly (část 3) představují další rozvoj obecné teorie, zahrnující Kleenovu hierarchii, vypočitatelné funkcionály a klasifikaci neřešitelných rozhodovacích problémů.

Tato práce, která byla poprvé publikována v roce 1958, zavedla mnoho terminologie, která se od té doby stala standardem v teoretické informatice. Kniha má takový význam, že ji mnoho informatiků považuje za teoretický úvod do této problematiky. Toto nové vydání nakladatelství Dover zpřístupňuje tento průkopnický, široce obdivovaný text v cenově dostupném formátu.

Dr. Davis připravil pro Doverovo vydání novou předmluvu a dodatek Hilbert's Tenth Problem Is Unsolvable, důležitý článek, který publikoval v The American Mathematical Monthly v roce 1973 a který byl oceněn cenami Americké matematické společnosti a Mathematical Association of America. Tyto dodatky dále zvyšují hodnotu a užitečnost neobyčejně přehledného a podnětného výkladu (Centre National de la Recherche Scientifique, Paris), který je nyní poprvé k dispozici v brožované podobě.