Skip to main content
Loading Explore guides…
Turing Machines Explained · Acedra
Home
Explore
Computer Science
Turing Machines Explained
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
9 segments
Copy
Hide video
0:00
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
0:36
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.
1:10
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
1:50
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!
2:26
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
3:07
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
3:47
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.
4:25
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
5:08
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.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat