Computability and logic
by George Boolos, Richard C. Jeffrey, George S. Boolos, John P. Burgess · first published 1974
10mentions
7recommended by
9HN commenters
2010–2022first – last mentioned
78% recommend22% neutral
Why HN recommends it
Approachable, well-regarded textbook on computability, Turing machines, recursive functions and Gödel's theorems; recommended for students and self-learners, including those moving beyond popular introductions.
Summarised by Claude from recommending comments
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
I have been through a slew of logic texts. By far, my favorite for both theory and practice is Computability and Logic by Boolos, Burgess and Jeffrey. http://www.amazon.com/Computability-Logic-George-S-Boolos/dp... Another very good book on nuts and bolts proofs in both propositional and predicate logic is Beginning…
on “Teach Yourself Logic 2016: A Study Guide [pdf]” ↗…a very entry level introduction. After that you might still need some textbook for more depth. >Mathematical Logic and Godel Incompleteness Theorems Start with ForallX by Magnus. Then continue with Computability and Logic by Boolos (don't read all chapters, check out preface to see what you need for Godel Incompleteness Theorems). >Set Theory Hrbacek - Introduction to Set Theory --- I am currently developing an online…
on “Ask HN: Mathematicians, what textbooks are best for learning these math topics?” ↗I went through it the first time by reading over Computability & Logic (5th edition) [1]. I'd love to go over it again, and would recommend it to anyone interested who has a few weekends to invest. [1] https://www.goodreads.com/book/show/1556746.Computability_an...
on “A Computability Proof of Gödel’s First Incompleteness Theorem” ↗Totally agree! When I was in school, I took a logic class that used Boolos & Jeffrey's "Computability and Logic", which is a really great book. Chapter 2 is a very clear presentation of Cantor's diagonalization proof that there exist uncountable sets. It blew my mind.
on “Music and Measure Theory (2015) [video]” ↗This is very cool! Thanks for posting this link. A very nice description of Turing machines, Abacus machines and in introduction to recursive functions can be found in the book "Computability and Logic" by Boolos, Burgess and Jeffrey.
on “A Turing Machine in the Classic Style” ↗I can't speak for Godel's original proof since I haven't seen it before, but I certainly found Computability and Logic [1] to be pretty approachable. It's the textbook used for UC Berkeley's "Intermediate Logic" philosophy course (in other words, it's so easy even philosophy majors can understand it! :P). From my understanding,…
on “Gödel and the limits of logic (2006)” ↗…author, I recommend: https://www.logicmatters.net/igt/godel-without-tears/ I found this super helpful when I was studying Gödel's theorems in grad school. (Fwiw, the 3rd edition of Boolos & Jeffrey's Computability and Logic is also great and takes a somewhat atypical approach to the proofs.)
on “An Introduction to Godel's Theorems (Second Edition) [pdf]” ↗…Turing by Charles Petzold really is great. It comes up a lot on this website but it was a great follow up, a good bridge from the fun almost hack-y math to a more "serious" approach. This led me to: Computability and Logic by George S Boolos. A standard textbook in universities across North America (and maybe further?). In the end I didn't become a mathematician. I hardly use advanced math compared to many other engineers…
on “Ask HN: Which book made you study mathematics” ↗…didn't read the thesis itself yet but I feel like some key point must be missing from the article. The "loop programs" described are nearly identical to the "abacus machine" presented in the textbook Computability and Logic (pp. 55-56 3rd ed.) which cites Joachim Lambek who published "How to Program an Infinite Abacus" in 1961 which seems to also be trivially close in structure (not merely equivalent). Lambek in turn cites…
on “Discovering Dennis Ritchie’s Lost Dissertation” ↗I used interpretation as it occurs for example in Computability and Logic by Boolos, Burgess and Jeffrey. It is also explained here: https://en.wikipedia.org/wiki/Interpretation_(logic)#Interpr... Please note that from a logical perspective, a (pure) Prolog program is always…
on “The Mercury logic programming system” ↗