Turing

Wanna earn a million dollars? It's possible, and all you might need is a really good idea. The Clay Mathematics Institute has chosen 7 of the hardest and most interesting math problems and offers a million dollars for a solution of any of them.

Out of the seven problems, one has been solved and five are hard to understand. This leaves the one this is about.

The mechanism of computation

It's quite possible you're reading this on a computer. But computers aren't primarily to be used as e-readers, they're computing machines. If you have a problem of a mathematical nature, you can use a computer to figure out the solution. Since we want to get to the absolute basics, we use zeroes and ones. A simple problem is determining whether two strings of ones are the same length (which might mean determining whether two numbers are equal). Now, there are easy problems and there are hard problems.

Computers are complicated. How could we ever find out which problems are easy and which are hard? So to simplify, there are models of computation. They are simple computing machines that can do anything a computer can do, but with everything superficial removed. Since we're trying to do math here, we don't need things like displays or user input. Introducing...

The Turing machine

The Turing machine model was invented by Alan Turingin 1936 - that is long before computers became practical. It's a "computer" stripped down to the very bare essentials. It consists of these parts:

1) An infinite tape of ones and zeroes. This tape serves as the memory.

2) A reading head that can move around the tape, read from it and write in it.

3) The program. It specifies how the head moves and how it reacts to the tape.

You may be unconvinced this is enough, or maybe you don't really get it. How does this work? Well, to show you just how powerful Turing machines are, let's build a program.

Base converter

Our example program will take a number in binary and convert it into unary. "Unary" is just a fancy tern for "a string of ones as long as the number is big". If you don't know what binary is, you might have slight problems. Read about it here. For example, the number 9 is 1001 in binary and 111111111 in unary.

The first thing to consider is - how do we even want our input to look? We have an infinite tape. Let's say we start at the first digit of the number. So the tape would look like this:

...00000010010000000...

(For our purposes, I'll bold whichever place the head is at)

But there's a problem. What if we wanted to ask the program to convert 10010?

...00000010010000000...

It's the same. So how can the program possibly know the difference? It can't. So what if we put a 1 at the end?

...00000010011000000...

...00000010010100000...

Now they're different, but imagine this: What if you wanted to convert 10010100000000000000000000000000000000000000? The one would be very far to the right. The program would have to go all the way there to check if that doesn't happen to be the number you wanted. There could be however many zeroes you want at the end, so just looking a fixed distance to the right wouldn't be enough, you'd still convert some numbers wrong.

What if we used a 2 to mark the end? That way we can just search for it first - and we'll know it's the end. But, obviously, no "2" symbol exists. So let's do this:

We'll divide the tape into two digit "numbers". As long as we know where they begin, we can add characters. It works like this:

00 will be used later

01 is the beginning or the end of the tape

10 is a zero in the number

11 is a one in the number.

Now, these two numbers would look like this (I divides the couples for easier recognition):

...00000I01I11I01I01I10I10I01I00000...

...00000I01I11I10I10I10I11I10I01I000...

The vertical bars aren't there for the program (just for us to better understand it), so we're not doing anything illegal and the program can identify both the end and the beginning of the number. It might be a little weird that we're using 01 for both the beginning and the end, but we can design the program so that it's not a problem.

Now, where do we put the result? Best to put it either before or after the number. Apart from the solution, we also need a place to store one more variable - the place value of whatever digit we're at. That will be on one end and the result will be on the other end.