Obliczalność Turinga: Teoria i zastosowania

Opinie czytelników

Książka jest kompleksowym i inspirującym badaniem obliczalności Turinga, z silną narracją historyczną i ekspertyzą autora widoczną w całym tekście. Przemawia szczególnie do studentów poszukujących głębszego zrozumienia teorii obliczalności.

⬤ Inspirująca i kompleksowa
⬤ szczegółowy kontekst historyczny
⬤ dobrze napisana i wciągająca
⬤ odpowiednia dla studentów chcących pogłębić swoje zrozumienie
⬤ autor wykazuje wyraźną wiedzę w tej dziedzinie.

Niektórzy czytelnicy mogą uznać ją za trudną, jeśli nie są zaznajomieni z dziedziną, ponieważ wydaje się być skierowana do osób z wcześniejszą wiedzą na temat teorii obliczalności.

(na podstawie 2 opinii czytelników)

Oryginalny tytuł:

Turing Computability: Theory and Applications

Zawartość książki:

Słynna praca Turinga z 1936 roku wprowadziła formalną definicję maszyny obliczeniowej, maszyny Turinga. Model ten doprowadził zarówno do rozwoju rzeczywistych komputerów, jak i teorii obliczalności, badania tego, co maszyny mogą, a czego nie mogą obliczyć. Ta książka przedstawia klasyczną teorię obliczalności od Turinga i Posta do aktualnych wyników i metod oraz ich zastosowania w badaniu zawartości informacyjnej struktur algebraicznych, modeli i ich związku z arytmetyką Peano. Autor przedstawia temat jako sztukę, którą należy praktykować, oraz sztukę w estetycznym sensie nieodłącznego piękna, które wszyscy matematycy rozpoznają w swoim przedmiocie.

Część I zawiera dokładny rozwój podstaw obliczalności, od definicji maszyn Turinga do argumentów priorytetu skończonego uszkodzenia. Kluczowe tematy obejmują względną obliczalność i obliczalnie wyliczalne zbiory, które mogą być efektywnie wymienione, ale niekoniecznie efektywnie rozstrzygnięte, takie jak twierdzenia arytmetyki Peano. Część II obejmuje badanie obliczalnie otwartych i zamkniętych zbiorów liczb rzeczywistych oraz twierdzenia o podstawach i nie-podstawach dla efektywnie zamkniętych zbiorów. Część III obejmuje minimalne stopnie Turinga. Część IV stanowi wprowadzenie do gier i ich zastosowania w dowodzeniu twierdzeń. Część V zawiera krótką historię teorii obliczalności.

Autor przez dziesięciolecia doskonalił treść podręcznika w oparciu o opinie studentów, wykładowców i badaczy z całego świata. Większość rozdziałów zawiera ćwiczenia, a materiał jest starannie uporządkowany według ważności i trudności. Książka jest odpowiednia dla zaawansowanych studentów studiów licencjackich i magisterskich z informatyki i matematyki oraz badaczy zajmujących się obliczalnością i logiką matematyczną.