Matematyczny elementarz obliczalności

Opinie czytelników

Obecnie brak opinii czytelników. Ocena opiera się na 2 głosach.

Oryginalny tytuł:

A Mathematical Primer on Computability

Zawartość książki:

Książka stanowi samodzielne wprowadzenie do teorii obliczalności dla zaawansowanych studentów matematyki i informatyki. Materiał techniczny jest zilustrowany licznymi przykładami, problemami z pełnymi rozwiązaniami, a także szeregiem proponowanych ćwiczeń.

Część I koncentruje się na podstawowych pojęciach i wynikach obliczalności, zaczynając od filarowych pojęć modelu obliczeniowego (abstrakcyjnego języka programowania wysokiego poziomu), funkcji obliczalnej, zbioru rozstrzygalnego i listowalnego, właściwej funkcji uniwersalnej, problemu decyzyjnego i techniki redukcji do przenoszenia właściwości rozstrzygalności i listowalności. Przedstawiono i zilustrowano podstawowe wyniki, a mianowicie twierdzenie Rice'a, twierdzenie Rice-Shapiro, twierdzenie Rice-Shapiro-McNaughton-Myhill, a także twierdzenie Rogersa i twierdzenie o rekursji. Zbadano redukowalność wiele-do-jednego i stopnie wiele-do-jednego. Zawarte jest również krótkie wprowadzenie do obliczeń z użyciem wyroczni. Wprowadzono operatory obliczalne i nieobliczalne, a także operatory monotoniczne i skończone. Omówiono związek między nimi, w szczególności poprzez twierdzenie Myhill-Shepherdsona. Przedstawione jest również Twierdzenie Kleene'a o najmniejszym punkcie stałym. Część I kończy się krótkim omówieniem modelu obliczeniowego Turinga, redukowalności Turinga i stopni Turinga.

Część II książki koncentruje się na zastosowaniach obliczalności w kilku dziedzinach, a mianowicie w logice (nierozstrzygalność arytmetyki, spełnialność w logice zdań, rozstrzygalność w logice modalnej), geometrii euklidesowej, grafach i złożoności Kołmogorowa. Niemniej jednak wcześniejsza znajomość tych zagadnień nie jest wymagana. Podane są szczegóły niezbędne do zrozumienia zastosowań.