In Love With Computer Science

There's a nice article written by a senior lecturer of UCSC, Dr. Chamath Keppitiyagama about the Turing Machine. I really like that article since I'm a big fan of theoretical computer science. It is a good attempt to show up an important concept to the ordinary people. I thought to repost it's content here to make it secure so that if the original article goes off, I won't miss it. :)

Link to original article: http://www.nation.lk/edition/component/k2/item/3666-a-computer-for-hundred-rupees?.html

A computer for hundred rupees?

No, I did not miss by several zeros – I meant it. We can build such a cheap computer and I guarantee that it can solve any problem that can be solved by those fancy and expensive computers. Now do not rush to buy processors, power supplies and other equipments, because we do not need them!

You can get the following ‘parts’ under hundred rupees. You need a long paper tape (a very long one), a pencil, an eraser, and a note pad. Take the long paper tape and using the pencil draw equal-sized squares along the tape.

That is it. Now there are some rules to follow. You can move the tape one square to the left or one to the right. You can write ‘1’ or ‘0’ on the square directly under your hand. If you wish you can erase anything on the square directly under your hand. After taking any action you can write a number in the note pad to indicate your ‘state’. The note pad has a table that you can consult before taking any action. This table tells you what to do – write, erase, move left or right – when you are in a given state and after reading a particular value from the tape. All that you can do is limited to those few actions.

That is your 100 rupee computer. I am not joking, but this machine is so powerful that it can solve any problem that can be solved on fancy computer. In fact, if a problem can be solved using a computing device, this computer can solve it. If this computer cannot solve a problem then it can never be solved using even a super computer. Unbelievable, isn’t it? Yet, it is true.

This machine is called a Turing machine. It was designed by Alan Turing in 1936, quite a long time before anybody made a computing device that resembles modern day computers. He did not propose it as a machine to be built and used for actual computation, even though you can easily build one if you really want to and use it for computation. Alan Turing proposed the Turing machine as a model of computation. He proposed that if any problem can be solved using computers this extremely simple machine can solve it and only the problems that can be computed on this machine can be solved on computers. It makes our 100 rupee computer a very powerful one indeed!

I have simplified the description of the machine quite a bit. A Turing machine needs an infinitely long tape, but let us ignore those details. Initially, the problem to be solved is written on the tape using ones and zeros on the squares (strictly speaking they do not even have to be ones and zeros, they can be any symbols). When the machine stops – that is when you stop moving the tape back and forth – the answer will be on the tape encoded in ones and zeros.

Computer scientists and mathematicians use this simple machine to study whether problems can be solved on computers and if so what are the most efficient ways to solve them. They do not actually build the machine, but use it to think of computing as a sequence of those actions allowed in the Turing machine. Even though they look very complicated, modern day computers try to mimic this machine. The role that you played in our 100 rupee computer is played by the processor and the memory chips take the place of the paper tape. The electronic processor is just faster than you and the problems can be solved faster, but apart from the speed, modern computers are not more powerful than a Turing machine. In fact, they are less powerful since none of them have an infinite memory whereas the Turing machine has an infinitely long tape (memory).

The power of this simple machine does not stop there. I am sure you have heard of those wonderful programming languages such as Java, C# and Python. Those programming languages are no more powerful than the simple set of instructions on our rudimentary computer. If you can write a nice program using those languages, you can write the same one using our simple set of instructions, but that would be tedious. Most of us have the notion that computers are all powerful devices. Well they are in some ways, but so is our Turing machine! I am sure now you have lost your faith in computers.

(The writer is a Senior Lecturer, University of Colombo School of  Computing)