Back at the start of the 20th century
mathematicians were fascinated by the question
'just how much maths can we do, not by using our
gut feelings or intuitions but just by following rules very very carefully
by following an algorithm'? In order to make that notion precise
we would have to set out: "just what do we mean by a program
or algorithm" - and this is where Alan Turing came in,
with his notion of a Turing machine.
Turing was working on a problem in Formal Logic
and as part of his proof he had to come up with the notion
of any possible algorithm
or any possible machine. He had to come up with a very general way of capturing
how algorithms or programs or machines would work
This is where his notion of a Turing machine comes in. The way Turing
described these machines goes like this: you have a way of
writing down information in a coded form.
His way was to think of a tape which is as long as it needs to be.
It's divided up into squares and each of the squares there is either one
or a zero or we can have some spaces. Now what our machine does
is it looks at the tape
one square at a time. So you could imagine it
as a little box running above the tape,
maybe on little wheels, looking
one square at a time and that information
codes up a question or a problem that we want solved.
What a Turing machine does is really simple
at any moment in time it's in a particular state
and it's looking at one square on the tape, and it has
a logbook, a program book. And that tells it,
if for instance you're in state number 23
and you're looking at a zero, then rub out the zero, change it
to one, move one square to the right,
and move into state number 359,
for instance. Or if you're in state number 359 and you're looking at a one
leave that one as it is, move one square to the left
and move into state number twenty. Really simple instructions!
what the machine does, is it starts off with a certain
pattern of ones and zeros. It
follows these rules one square at a time,
transforming that string of ones and zeros
into a different string of ones and zeros.
And eventually - hopefully -
the machine moves into a halting state, it is finished, it is done.
And what's left on the tape is the answer to our problem,
coded up as ones and zeros. That is such a simple
process but it turns out it's the
essence of computation. Whatever
any computer can do, it could in theory
be done by that system looking at ones and zeros
on a tape. So that's why we say
that Turing in coming up with his idea of Turing machines,
in effect, came up with a blueprint for modern digital computers.
Those computers manipulate strings of ones and zeros
to solve problems. This really simple
idea that we find in Turing machines is actually so
powerful that all modern computers
basically do what Turing machines do. And we use this idea
to evaluate the strength of modern computer programs.
When a computer program can do
what a Turing machine can do, we call it Turing complete
and that is the top of the hierarchy of program strength. So the strongest
program that we can get does exactly what
a Turing machine can do. We've never come up with a way of computing things
that could do more than a Turing machine. So
recently, there's been a challenge to the idea
that anything a computer can do, a Turing machine can do.
And the challenge comes from quantum computers which
almost seem like they can do things magically.
My take on this is that a quantum computer
can't do more than a Turing machine but it can do things more
efficiently. For instance, if you asked
a classical computer to find you a phone number
in the phone directory, you have to look for every single
entry and it takes a long time.
But a quantum computer can do that
more efficiently, don't ask me how.
ok
look what
happens, if I've read a zero, which I have, there.
What do I then do? The answer is I
override it with a one. Call that machine H,
for the halting problem, if you give me that machine, I could transform it into a
different machine,
like this.