Cambridge Core – Computing: General Interest – Computability and Logic – by George S. Boolos. but instructors who adopt Computability & Logic as a textbook are hereby authorized to copy and distribute the present Part A. This permission does not extend. Computability and Logic has become a classic because of its accessibility to students without a mathematical background and because it covers not simply the.

Author: Zulura Akilmaran
Country: Anguilla
Language: English (Spanish)
Genre: Literature
Published (Last): 5 December 2018
Pages: 482
PDF File Size: 5.1 Mb
ePub File Size: 15.10 Mb
ISBN: 360-5-47583-478-5
Downloads: 79007
Price: Free* [*Free Regsitration Required]
Uploader: Goltikazahn

I’m reviewing the books on the MIRI course list. After putting down Model Theory partway through I picked up a book on logic.

Book Review: Computability and Logic

Computability and Logicspecifically. This book is not on the MIRI course list. It was recommended to me by Luke along with a number of other books as a potential way to learn provability logic.

Computability and Logic is a wonderful book. It’s formal, but pulls off a conversational tone. It demonstrates many difficult concepts with ease. It even feels nice — it’s got thick pages, large text, and a number of useful diagrams. This book is a wonderful introduction to computability, incompleteness, unsatisfiability, and related concepts. It masterfully motivates the connection between computability and logic a subject near and dear to my heart.

It could be an invaluable resource for anyone in computer science llogic to branch out into logic. For me, though, it was on the easy side. I already knew all the computability stuff quite well, and skimmed computabikity much of it. The logic sections were a good refresher, though they were somewhat rudimentary by comparison to Model Theory. Actually, this book would have been a great precursor to Logiv Theory: It spent quite a bit of time motivating and fleshing out concepts that Model Theory computsbility on your head.

Still, while this book was not exactly what I needed, I highly recommend it ad other purposes. Its contents are summarized below. This chapter introduces enumerability, and some of the cooler results.

If any of the below sounds surprising to you, you’d be well served by reading this chapter:. If there’s a one-to-one mapping between two sets, those sets are “the same size”.

By this measure, the following sets are the same size:. This leads to a discussion of the “size” of infinite sets, which can be somewhat surprising the first time through. Knowledge of enumerability is central to many issues in computer science, and is integral in any study of infinities. I highly recommend you familiarize yourself with these concepts at some point in your life, if only for fun. When you realize how much can be enumerated there’s a one-to-one mapping between natural numbers and all finite subsets of the natural numbers!

Diagonalization stops the buck. It’s a tool for finding conputability set that defies a given encoding. Diagonalization is incredibly important if you want to play with infinities or learn about decidability.

If you haven’t yet seen diagonalization, you’re in for a treat. I won’t ruin the fun here: The second chapter of Computability and Logic is a clever and easy introduction to diagonalization, and I highly recommend it to newcomers. Again, if this sounds new, I highly recommend picking up Computability and Logic: This chapter introduces Turing Computability, which is literally the bedrock of computer science.


We focus on the question of what can in principle be computed. For those of you who don’t know, the Turing Machine is an idealized computation engine which can compute answers to a very large class of problems. If you’re not familiar with the concept, this chapter is a great introduction.

Even if you’re vaguely familiar with the concept, but you’re not quite sure how a Turing machine works “wait, it only has a fixed number of states? It walks you through the implementation of a Turing machine, and shows you a number of clever algorithms by which a Turing machine computes simple algorithms. You’ll find yourself actually walking through the actions of the machine in your head, which is a great way to get a feel for the idealized basics of computation.

Again, if any of this sounds new to you, I highly recommend picking up this book and reading the first few chapters.

Computability and Logic by George S. Boolos

After seeing Turing machines, it is again easy to grow overconfident and feel like you can compute anything. As a matter of fact, the proof that you can’t compute everything with a Turing machine is exactly the same as the proof that you can’t enumerate every set. It turns out Turing programs are enumerable as is anything you can write out with symbols from a finite alphabet. So we can use the exact same technique — diagonalization — to construct problems that a Turing machine cannot solve.

Again, if any of this sounds foreign or even if you’re just rustythis chapter is a delightful introduction to uncomputability. For example, it constructs the halting problem from a diagonalization of an encoding of Turing machine instructions. This smoothly unifies diagonalization with the intuitive impossibility of the halting problem.

The chapter even touches on the busy beaver problem. I can’t do it justice in a few mere paragraphs: This chapter introduces another formalism that has more machinery available to it than a Turing machine. If you don’t already know how this story goes, I won’t ruin the surprise. Again, this chapter is clever and fun to read. It has lots of diagrams and gives you a good feel for what sort of power an “abacus machine” something that can do real math has as a computational engine.

If computability is a new field to you, you’ll enjoy this chapter. We now step to the math side of things. This transition is motivated computationally: These four functions are called the “primitive recursive” functions, and some time is spent exploring what they can do. If we allow use of a fifth function:. These are a set of building blocks for some pretty interesting functions, and we are now firmly in math land. The above definitions are extended to define recursive sets and relations.

Generally speaking, we can define sets and relations by indicator functions which distinguish between elements that are in a set from elements that are not. Sets and relations are called “primitive recursive” if their indicator functions can be constructed from primitive recursive building blocks.

They are “recursive” if their indicator functions can be constructed from recursive building blocks. They are called “semirecursive” if there is a recursive function which at least says “yes” to elements that are in the set, even if it cannot say “no” to elements that are not in the set. Note that the indicator function for recursive sets must be total — i.


Also, note that semirecursive sets are more commonly known as “recursively enumerable” sets. This may all seem a bit abstract, especially following all the computationally-motivated content above. However, these distinctions are good to know.

This chapter is perhaps less fun than the others, but no less important. It’s easy to get recursive and semirecursive sets mixed up, when you’re starting out. This is where the magic happens. This chapter shows that a function is recursive iff it is Turing computable. Turing machines and recursive functions are computational engines of precisely the same power.

This is one of my favorite results in mathematics, and it’s a beautiful and the original bridge between the lands of math and computer science. This chapter actually shows you how to build a recursive function that computes the result of a Turing machine, and how to encode recursive functions as Turing-machine instructions.

Even if you know the results, you may find it useful or just fun to toy with an actual bridge between the two formalisms. That’s one thing I really like about this book: It actually shows you an encoding. It lets you see the guts of the thing. If you’re casually interested in math or computer science or if you need a brush up, or you just want a good time then I highly recommend reading this book at least through chapter 8.

It’s good clean fun to see these things play out in front of you, instead of just hearing the results secondhand. We now dive in to the logic side of things. This chapter introduces the syntax of first order logic.

It’s a pretty solid introduction, and a good way to brush up on the precise syntax if you’re feeling rusty. Here we start getting into a little bit of model theory, binding the syntax of first order logic to semantics. This chapter would have been valuable before I started reading Model Theory. It is a solid introduction to the concepts.

This chapter is dedicated to encoding a Turing machine as a logical theory. The fact that this can be done is incredibly cool, to say the least.

As before, the chapter provides actual examples for how to encode Turing machines as logical theories. You get to play with sentences that describe a specific Turing machine and the state of its tape.

You get to see the chain of implications that represent the computation of the Turing machine. As before, this is an awesome way to get a hands-on feel for a theoretical result that is commonly acknowledged but seldom explored. However, this book doesn’t just tell you that result, it shows it to you. Even if you’re already familiar with the result, reading this chapter is quite a bit of fun. There’s something magical about seeing the connections between computation and logic laid bare before you.

This chapter goes into basic model theory, discussing concepts like isomorphism, model size, and compactness.