Calculabilitate și nerezolvabilitate

Recenzii ale cititorilor

Cartea lui Martin Davis „Computability and Unsolvability” oferă un tratament formal și riguros al teoriei calculabilității și al implicațiilor sale în matematică și informatică. Deși a fost apreciată pentru profunzimea și rigurozitatea sa, mulți cititori au remarcat notarea dificilă și lipsa de exemple concrete, ceea ce o face mai puțin accesibilă pentru cei care nu au o pregătire matematică solidă.

⬤ Tratarea cuprinzătoare și riguroasă a calculabilității și a teoriei funcțiilor recursive.
⬤ Structură bine organizată; teoremele se interconectează eficient.
⬤ Conținut valoros privind întrebări profunde despre calculabilitate și a zecea problemă a lui Hilbert.
⬤ Retipărire accesibilă de la Dover.

⬤ Stil foarte formal care poate fi dificil pentru cititorii care nu sunt versați în matematică.
⬤ Lipsă de exemple concrete pentru a ilustra conceptele.
⬤ Demonstrațiile pot părea plictisitoare și pot sări peste pașii necesari pentru înțelegere.
⬤ Unele secțiuni sunt criticate pentru că sunt seci sau lipsite de viață.

(pe baza a 12 recenzii ale cititorilor)

Titlul original:

Computability and Unsolvability

Conținutul cărții:

În acest text clasic, Dr. Davis oferă o introducere clară în calculabilitate, la un nivel universitar avansat, care răspunde deopotrivă nevoilor specialiștilor și nespecialiștilor.

În prima parte (capitolele 1-5), profesorul Davis schițează teoria generală a calculabilității, discutând subiecte precum funcțiile calculabile, operațiile asupra funcțiilor calculabile, funcțiile recursive, mașinile Turing, problemele de decizie autoaplicabile și nerezolvabile. Autorul a avut grijă, în special în primele șapte capitole, să nu presupună o pregătire matematică specială din partea cititorului.

Partea a doua (capitolele 6-8) cuprinde o tratare concisă a aplicațiilor teoriei generale, încorporând materiale privind problemele combinatorii, ecuațiile diofantice (inclusiv a zecea problemă a lui Hilbert) și logica matematică. Ultimele trei capitole (Partea 3) prezintă dezvoltarea ulterioară a teoriei generale, cuprinzând ierarhia Kleene, funcționalele calculabile și clasificarea problemelor de decizie nerezolvabile.

Când a fost publicată pentru prima dată în 1958, această lucrare a introdus multă terminologie care a devenit de atunci standard în informatică teoretică. Într-adevăr, statura cărții este de așa natură încât mulți informaticieni o consideră drept introducerea lor teoretică în domeniu. Această nouă ediție Dover face ca acest text de pionierat, admirat pe scară largă, să fie disponibil într-un format necostisitor.

Pentru ediția Dover, Dr. Davis a oferit o nouă prefață și un apendice, Hilbert's Tenth Problem Is Unsolvable, un articol important pe care l-a publicat în The American Mathematical Monthly în 1973, care a fost premiat de American Mathematical Society și Mathematical Association of America. Aceste adăugiri sporesc și mai mult valoarea și utilitatea unei expuneri neobișnuit de clare și stimulative (Centre National de la Recherche Scientifique, Paris), disponibilă acum pentru prima dată în format paperback.