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)

## No comments:

## Post a Comment