Czy możesz podać mi sugestie dotyczące dobrej wstępnej (ale wyczerpującej) książki
o logice i obliczeniach?
Niektóre rozmyte tematy, które mam na myśli to:
Odpowiedzi:
Moja odpowiedź może być spóźniona na to pytanie, ale mam nadzieję, że przyda się innym osobom szukającym podobnych informacji.
Wziąłem kurs o logice matematycznej na National University of Singapore, w którym wykładowca wykorzystał ten podręcznik:
Zwięzłe wprowadzenie do logiki matematycznej, 3. wydanie, Wolfgang Rautenberg
Osobiście bardzo podoba mi się zarówno podręcznik, jak i kurs.
Podręcznik początkowo wydaje się dość trudny do odczytania. Jednak po zapoznaniu się z nim znacznie łatwiej jest podążać, ponieważ system notacji jest bardzo jasny, treść jest zamknięta, a podejście zaczyna się od założenia, nie ma niejasnych założeń. Na przykład książka ta rozwija rachunek dedukcji naturalnej i rachunek Hilberta lub dowodzi dwóch twierdzeń Kurta Gödela od podstaw.
Proponuję jedną z książek, które niedawno kupiłem:
Nie miałem („nadal nie mam” :-) silnego tła z logiką i ta książka pomaga mi lepiej zrozumieć niektóre „podstawowe” aspekty logiki i jej związek z obliczeniami i złożonością. Niewątpliwie dobra książka wprowadzająca.
Spis treści i wstęp książki można pobrać ze strony głównej Pudlaka, a także niektóre fragmenty książki na stronie http://books.google.com .
Ze wstępu :
... Pierwsze dwa rozdziały są wstępem do podstaw matematyki i logiki matematycznej. Materiał został wyjaśniony bardzo nieformalnie, a bardziej szczegółowe przedstawienie zostało odłożone do późniejszych rozdziałów ...
Rozdział 3 poświęcony jest teorii mnogości, która jest najważniejszą częścią podstaw matematyki. Dwa główne tematy w tym rozdziale to: (1) wyższe nieskończoności jako źródło potężnych aksjomatów oraz (2) alternatywne aksjomaty, takie jak aksjomat determinacji ...
Dowody niemożliwości, temat rozdziału 4, dowodzą, że niektóre zadania są niemożliwe, wbrew pierwotnej intuicji. Obecnie mamy tendencję do utożsamiania niemożliwości z niedopuszczalnością i niemożnością obliczenia, co jest raczej wąskim poglądem. Dlatego warto przypomnieć, że pierwsze ważne wyniki niemożliwości uzyskano w różnych kontekstach: geometrii i algebry. Najważniejszym rezultatem przedstawionym w tym rozdziale jest twierdzenie Kurta Godela o niekompletności ...
Dowody niemożliwości są, oczywiście, ważne w fundamentach. Jednym z obszarów, w którym najbardziej podstawowe problemy dotyczące udowodnienia niemożności są teorie złożoności obliczeniowej, temat rozdziału 5. Ale istnieje więcej powiązań między złożonością obliczeniową a podstawami ...
W rzeczywistości istnieje dziedzina badań, która bada związki między złożonością obliczeniową a logiką. Nazywa się to „dowodem złożoności” i jest przedstawione w rozdziale 6. Chociaż mamy wskazówki, że złożoność powinna odgrywać istotną rolę w fundamentach, nie mamy żadnych wyników potwierdzających ten związek. ...
Każda książka o podstawach matematyki powinna wymieniać podstawowe filozoficzne podejścia do podstaw matematyki. Robię to również w rozdziale 7, ale ponieważ nie jestem filozofem, główna część rozdziału koncentruje się raczej na wynikach matematyki i problemach leżących na granicy matematyki i filozofii ...
Nie obejmuje FMT i złożoności opisowej, ale istnieje kilka dobrych książek, które koncentrują się na tych tematach (np. Leonid Libkin: Elementy teorii modeli skończonych; Teksty w teoretycznej informatyce. Seria EATCS; 2004 )
Przyjmuję odpowiedź, ponieważ nie miałem jeszcze okazji przeczytać książki zaproponowanej przez Trung Ta.
Podoba mi się książka Toma Stuarta „Zrozumienie obliczeń” w odniesieniu do obliczeń modelowania. Oferuje ładny progresywny przegląd modeli do obliczeń. Jeśli dobrze pamiętam: - deterministyczne maszyny skończone - niedeterministyczny FSM - FSM ze stosem (deterministyczny i niedeterministyczny) - maszyny Turinga (z taśmą)
Jest dość interaktywny i praktyczny, ponieważ jednocześnie buduje prostą implementację każdego modelu w Ruby.