Obliczalność i nierozstrzygalność

Opinie czytelników

Książka Martina Davisa „Computability and Unsolvability” stanowi formalne i rygorystyczne podejście do teorii obliczalności i jej implikacji w matematyce i informatyce. Choć została doceniona za swoją głębię i dokładność, wielu czytelników zwróciło uwagę na trudną notację i brak konkretnych przykładów, co czyni ją mniej przystępną dla osób bez silnego zaplecza matematycznego.

⬤ Kompleksowe i rygorystyczne potraktowanie obliczalności i teorii funkcji rekurencyjnych.
⬤ Dobrze zorganizowana struktura; twierdzenia skutecznie się ze sobą łączą.
⬤ Wartościowe treści dotyczące głębokich pytań o obliczalność i dziesiąty problem Hilberta.
⬤ Niedrogi przedruk z Dover.

⬤ Wysoce formalny styl, który może być trudny dla czytelników niezaznajomionych z matematyką.
⬤ Brak konkretnych przykładów ilustrujących pojęcia.
⬤ Dowody mogą wydawać się nużące i mogą pomijać kroki niezbędne do zrozumienia.
⬤ Niektóre sekcje są krytykowane za suchość lub brak życia.

(na podstawie 12 opinii czytelników)

Oryginalny tytuł:

Computability and Unsolvability

Zawartość książki:

W tym klasycznym tekście dr Davis zapewnia przejrzyste wprowadzenie do obliczalności na zaawansowanym poziomie licencjackim, które zaspokaja potrzeby zarówno specjalistów, jak i niespecjalistów.

W części pierwszej (rozdziały 1-5) profesor Davis nakreśla ogólną teorię obliczalności, omawiając takie tematy jak funkcje obliczalne, operacje na funkcjach obliczalnych, funkcje rekurencyjne, maszyny Turinga, samozastosowanie i nierozwiązywalne problemy decyzyjne. Autor był ostrożny, zwłaszcza w pierwszych siedmiu rozdziałach, aby nie zakładać specjalnego przygotowania matematycznego ze strony czytelnika.

Część druga (rozdziały 6-8) zawiera zwięzłe omówienie zastosowań ogólnej teorii, włączając materiał dotyczący problemów kombinatorycznych, równań diofantycznych (w tym dziesiątego problemu Hilberta) i logiki matematycznej. Ostatnie trzy rozdziały (Część 3) przedstawiają dalszy rozwój ogólnej teorii, obejmujący hierarchię Kleene'a, obliczalne funkcjonały i klasyfikację nierozwiązywalnych problemów decyzyjnych.

Po raz pierwszy opublikowana w 1958 roku, praca ta wprowadziła terminologię, która od tego czasu stała się standardem w informatyce teoretycznej. Rzeczywiście, ranga tej książki jest taka, że wielu informatyków uważa ją za swoje teoretyczne wprowadzenie do tematu. Nowe wydanie Dover sprawia, że ten pionierski, powszechnie podziwiany tekst jest dostępny w niedrogim formacie.

Do wydania Dover dr Davis dołączył nową Przedmowę i Dodatek, Hilbert's Tenth Problem Is Unsolvable, ważny artykuł opublikowany w The American Mathematical Monthly w 1973 roku, który został nagrodzony przez American Mathematical Society i Mathematical Association of America. Te dodatki jeszcze bardziej zwiększają wartość i użyteczność niezwykle jasnej i stymulującej ekspozycji (Centre National de la Recherche Scientifique, Paryż) dostępnej teraz po raz pierwszy w miękkiej oprawie.