Name: Computability and logic
ISBN: 9780521701464

Computability and logic

Computability and Logic has become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as Godel's incompleteness theorems, but also a large number of optional topics, from Turing's theory of computability to Ramsey's theorem. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive functions, a traditional stumbling block for students on the way to the Godel incompleteness theorems.

What Hacker News says

PhithagorasFeb 2022

Things to Make and Do in the Fourth Dimension by Matt Parker is a fun, accessible, and fascinating explanation of how math can be a big game.

The Annotated 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 and scientists but the ideas have stuck with me for years, and I think my life is richer for knowing them

thread

ntabrisAug 2020

For a shorter (but still fairly thorough) introduction by the same 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.)

thread

daviddaviddavidJul 2020

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.

thread

adz_6891Dec 2019

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...

thread

philip-bApr 2019

Textbooks which people on the internet consider very good:

>Group Theory

Carter - Visual Group Theory

>Complex Analysis

Needham - Visual Complex Analysis

Less confident recommendations:

>Probability

https://ocw.mit.edu/courses/mathematics/18-05-introduction-t... as 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 course which teaches logic, set theory, and computability theory (this includes Godel Incompleteness Theorem). It uses the textbooks I've mentioned above. You can check it out at https://app.grasple.com/#/course/141?access_token=3HCK4oRipe.... Use "Fundamentals of formalization" and ignore other tracks.

thread

ucarionMar 2017

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, C&L diverges from Godel's original proof technique in order to make it easier to follow, but it's much more rigorous and explicit than what you'd find in Godel, Escher, Bach or something. It's still a textbook.

[1]: https://www.amazon.com/Computability-Logic-George-S-Boolos/d...

thread