Turing the Page

“The ‘computable’ numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.”

“Trees will play an important role throughout this work, so we shall commence with some pertinent definitions:”

These excerpts are from the beginning of Turing’s “On Computable Numbers with an Application to the Entscheidungsproblem”, and Smullyan’s”First Order Logic”, respectively. Both of these texts are used as our main sources of information in in my current class here at Quest, Logic and Metalogic. Though they may seem a little esoteric and scary (maybe not the tree one, but if you saw the amount of logic symbols that came after, you might get scared), once you dig in behind these starting points and get to the real essence of the subject matter, you will find far more esoteric and scary stuff, so hold on as we start Turing the page (my faithful readers will recognize another pun).

Or will you?

Books1

I guess this is one way to approach the evaluation of a class. Presumably, if a class is actually any good, and the student is actually any good, the student’s perception of the material will transform. Instead of esoteric and scary, the student might, after having taken the class, view the subject matter as interesting and complex, applicable and comprehensible. I have not seen Logic and Metalogic that way.

Instead, I see it as this: profound and beautiful.

Profound:

Logic and Metalogic? What even is that? I can understand what calculus is for, biology helps us make medicines and things, creative writing is just plain cool, but Logic and Metalogic? A proof that the Entscheidungsproblem (what?) can’t be solved? Who cares?

When I tell some of my friends that I am taking this class, the preceding is akin to their reply. The answer to that last question is, however, YOU should!

In Logic and Metalogic, what we are looking at are fundamental properties of the universe: different types of infinities, statements that are always true or always false no matter what, and the very nature of computation itself.

So, why are these things interesting? Many problems in our highly technical world today come down to how computers manipulate information in the form of numbers. In fact, that is one of the chapters in one of our books for our class: “Everything is a Number”. So, when it comes down to it, understanding the limits of computation has serious real world applications.

 

Darcy1

One such real world application is that there cannot be a general algorithm that solves all math problems. It is not simply that we haven’t found it yet, or come up with a clever way to do it. Alan Turing proves that, quite literally, there will never be and can never be a general algorithm/computer program that solves every problem. If there was, then Mathematicians would spend all their time finding it. Once they had, they would simply run it to solve all problems, and there you go. The world would be a quite different place, as we would have far more powerful tools to solve things. But, alas, this is simply not the case.

Also, one has to appreciate the brilliance of Alan Turing. In order to solve this Entscheidungsproblem (what I have basically described in the previous paragraph), he first invents the notion of a digital computer, and then proves what they could never do. How crazy is that? Before computers ever existed, someone proved what they could never do, no matter how advanced technologically computers get. It is simply impossible.

What is even more interesting and profound in some people’s minds, including my own, is that this creates a clear and decisive barrier between computers and the human brain/mind, which is disturbing for someone such as myself, who finds the idea that our mind is simply a computational entity quite compelling. However, if our minds truly are simply computers, then they could not have even proved what computers could never do.

From uncovering the limits of computation by creating a machine and then proving what it cannot do, Turing has in fact said something profound about the human mind. We are not computers. Our minds are not mechanical.

class

As I said, this can be unsettling for some. I am still wrestling with this notion myself. If not mechanical, then what else? I am having the very foundations of my belief system about out world challenged, and its happening right in this class.

And that is fantastic! I cannot properly convey my sense of jubilation in this post. The very world as I know it is being reshaped before my eyes. That’s what all my favourite classes have done here at Quest. This is why I chose Quest, and why I choose to continue to attend. When you really get down to it, everything, every single discipline/idea/concept/study is truly interesting, and its all interrelated. A good classes shows you that, but more than that, it makes you feel it.

The subject matter of this class is deeply profound and has far reaching consequences. Who knew? (The tutor, that’s why he offered it).

Beautiful:

Now, I could simply read a summary of Turing’s paper and get a general sense of the ideas, much like how I tried to convey the general sense of the ideas of my course to you. But having a general sense of something and actually knowing it, feeling it, understanding it, those are different things.

To really understand something, especially something as complex and elegant as the proof we study in this class, is a lot of hard, determined work. In this class we have a lot of reading, and real, hands on programming of Turing machines (the computer he invents) to make sure that we have an intuitive and deep feel for what is going on in the proof. As an example, here are a few lines of code from a recent assignment to write a Univeral Turing Machine that can simulate code of any other Turing Machine:

f(e1(e(anf,x),anf,x),anf,x) @ L f1(e1(e(anf,x),anf,x),anf,x)
f(e1(e(anf,x),anf,x),anf,x) Else L f(e1(e(anf,x),anf,x),anf,x)
f1(e1(e(anf,x),anf,x),anf,x) x - e1(e(anf,x),anf,x)
f1(e1(e(anf,x),anf,x),anf,x) None R f2(e1(e(anf,x),anf,x),anf,x)
f1(e1(e(anf,x),anf,x),anf,x) Else R f1(e1(e(anf,x),anf,x),anf,x)
f2(e1(e(anf,x),anf,x),anf,x) x - e1(e(anf,x),anf,x)
f2(e1(e(anf,x),anf,x),anf,x) None R anf
f2(e1(e(anf,x),anf,x),anf,x) Else R f1(e1(e(anf,x),anf,x),anf,x)

Wow. What even is that? Just like when you are learning a new concept in math or new jargon in the social sciences, even if you know what is going on it can be difficult to parse apart. However, the more practice you put into actually practicing the skills necessary to understand all the nuts and bolts of a concept, the more rewarding it is. You simply get more out of it, and get a deeper sense of beauty than skimming the surface simply gives you. An poet John Keats points out in his poem Endymion

A thing of beauty is a joy for ever:
Its loveliness increases; it will never
Pass into nothingness

Well put. However, Keats does not (at this point in this poem, anyway) describe the arduous endeavor that often accompanies a solid grasp and true appreciation of such beauty (for Keats’ description of this, see the begininng of Keats’ The Fall of Hyperion: A Dream).

This is something that both this class, as well as others at Quest, has taught me about beauty. Understanding beauty is tough work, but rewarding. Sometimes simplicity is beauty. For example,

1+1=2

is a proof, from first principles (that’s what the Qs mean on the side) of 1+1=2. Before we proved it, most of only thought this because of intuition, and because it had been drilled into our heads all our lives. Now, everyone can the class can say that we definitively know that 1+1=2.

Other times, beauty is complicated and difficult to parse.

lookslikemath

Now this may look scary (and I’ll admit it, it is). If you had approached me at the beginning of the block and asked me what this meant, I would have laughed and thought it a joke. No way I could ever figure that out. Now, however, after a few weeks of digging into various types of logic, arguments, and proofs, I can tell you what this means. It is simply a way to phrase an instruction for a Turing Machine (computer) to print a certain symbol if it is scanning another symbol, and move left. Being able to look at something like this, a statement in first order logic, and understand what it means and its implications is an empowering feeling.

There is also lots of work that goes on outside of class to understand these things. And believe me, you can understand them with a little work. For example, the bellow is a whiteboard some students were using to make sure they understood some of the different terms we used in this class.

quantifier

When you dig deep enough into the kinds of questions we asked in this class, we actually stumble upon question about the fundamental nature of reality. For example, if we are defining what it means for a system to be “sound”, some say that this means that any True statement a system produces is indeed true. However, others disagree, saying that there is no actual external truth, but that the system itself generates the truth.

You can already see how quickly, when you dig deep enough into logic and metalogic, you come to beautiful and profound conclusions and ideas. Although a challenging class, we dive right into the interesting proofs of arguably one of the most important papers ever written. It can be (and is) tough to delve right in when you have no previous experience with logic, but this is what makes it such a valuable learning experience. When you are thrown straight off into the deep end, you will learn to swim. And then you will learn to dive deep into the rich waters you originally found terrifying and incomprehensible.

And the treasures you find there, they are beautiful beyond belief. This is what a good class, such as Logic and Meta logic does.

Can you tell that I am enjoying this class?

Leave a Reply