Vypočítateľnosť a neriešiteľnosť

Recenzie čitateľov

Kniha Martina Davisa „Computability and Unsolvability“ (Vypočítateľnosť a neriešiteľnosť) poskytuje formálne a dôsledné spracovanie teórie vypočítateľnosti a jej dôsledkov v matematike a informatike. Hoci bola ocenená pre svoju hĺbku a dôkladnosť, mnohí čitatelia si všimli jej náročný zápis a nedostatok konkrétnych príkladov, čo ju robí menej prístupnou pre tých, ktorí nemajú silné matematické zázemie.

⬤ Komplexné a dôsledné spracovanie teórie vypočítateľnosti a rekurzívnych funkcií.
⬤ Dobre organizovaná štruktúra; tvrdenia sú efektívne prepojené.
⬤ Cenný obsah týkajúci sa hlbokých otázok o vypočítateľnosti a Hilbertovho desiateho problému.
⬤ Cenovo dostupný reprint z vydavateľstva Dover.

⬤ Vysoko formálny štýl, ktorý môže byť náročný pre čitateľov, ktorí nie sú dobre zbehlí v matematike.
⬤ Chýbajú konkrétne príklady na ilustráciu pojmov.
⬤ Dôkazy môžu byť zdĺhavé a môžu vynechať kroky potrebné na pochopenie.
⬤ Niektoré časti sú kritizované za suchopárnosť alebo neživotnosť.

(na základe 12 čitateľských recenzií)

Pôvodný názov:

Computability and Unsolvability

Obsah knihy:

V tomto klasickom texte Dr. Davis poskytuje prehľadný úvod do vypočítateľnosti na úrovni pokročilého vysokoškolského štúdia, ktorý slúži potrebám odborníkov aj neodborníkov.

V prvej časti (kapitoly 1 až 5) profesor Davis načrtáva všeobecnú teóriu vypočítateľnosti a rozoberá témy ako vypočítateľné funkcie, operácie na vypočítateľných funkciách, rekurzívne funkcie, Turingove stroje, samoaplikovateľné a neriešiteľné rozhodovacie problémy. Autor si dal záležať, najmä v prvých siedmich kapitolách, aby nepredpokladal žiadne špeciálne matematické vzdelanie čitateľa.

Druhá časť (kapitoly 6 až 8) obsahuje stručné spracovanie aplikácií všeobecnej teórie, pričom zahŕňa materiál o kombinatorických problémoch, diofantických rovniciach (vrátane Hilbertovho desiateho problému) a matematickej logike. Posledné tri kapitoly (3. časť) predstavujú ďalší rozvoj všeobecnej teórie, ktorý zahŕňa Kleenovu hierarchiu, vypočítateľné funkcionály a klasifikáciu neriešiteľných rozhodovacích problémov.

Táto práca, ktorá bola prvýkrát publikovaná v roku 1958, zaviedla mnoho terminológie, ktorá sa odvtedy stala štandardom v teoretickej informatike. Kniha má skutočne také postavenie, že ju mnohí informatici považujú za teoretický úvod do tejto témy. Toto nové vydanie vydavateľstva Dover sprístupňuje tento priekopnícky, široko obdivovaný text v lacnom formáte.

Dr. Davis pripravil pre vydanie vydavateľstva Dover nový predslov a prílohu Hilbertov desiaty problém je neriešiteľný, dôležitý článok, ktorý uverejnil v časopise The American Mathematical Monthly v roku 1973 a ktorý bol ocenený cenami Americkej matematickej spoločnosti a Mathematical Association of America. Tieto dodatky ešte viac zvyšujú hodnotu a užitočnosť neobyčajne prehľadného a podnetného výkladu (Centre National de la Recherche Scientifique, Paríž), ktorý je teraz prvýkrát k dispozícii v brožovanej podobe.