Computers in the past could only do one kind of thing at a time. One computer could add some numbers together, but nothing else. Another could find the smallest of some numbers, but nothing else. You could give them different numbers to work with, but the computer would always do the same kind of thing with them.
To make the computer do something else, you had to open it up and put all its pieces back in a different way. This was very hard and slow!
So a man named Mr. Babbage thought: what if some of the numbers you gave the computer were what told it what to do? That way you could have just one computer, and you could quickly make it be a number-adding computer, or a smallest-number-finding computer, or any kind of computer you wanted, just by giving it different numbers. But although Mr. Babbage and his friend Ms. Lovelace tried very hard to make a computer like that, they could not do it.
But later a man named Mr. Turing thought up a way to make that computer. He imagined a long piece of paper with numbers written on it, and imagined a computer moving left and right that paper and reading the numbers on it, and sometimes changing the numbers. This computer could only see one number on the paper at a time, and also only remember one thing at a time, but that was enough for the computer to know what to do next. Everyone was amazed that such a simple computer could do anything that any other computer then could do; all you had to do was put the right numbers on the paper first, and then the computer could do something different! Mr. Turing’s idea was enough to let people build computers that finally acted like Mr. Babbage’s and Ms. Lovelace’s dream computer.
Even though Mr. Turing’s computer sounds way too simple when you think about our computers today, our computers can’t do anything that Mr. Turing’s imagined computer can’t. Our computers can look at many many numbers and remember many many things at the same time, but this only makes them faster than Mr. Turing’s computer, not actually different in any important way. (Though of course being fast is very important if you want to have any fun or do any real work on a computer!)
A plan is a list of things to do. When a computer runs, it is doing the things that are written in a plan. When you solve a problem like 23 × 3, you are also following a plan.
Plans are made of steps. To follow a plan, you do what each plan step says to do, in the order they are written. But sometimes a step can tell you to move to a different step in the plan, instead of the next one. And sometimes it can tell you to do different things if you see something different. It can say “Go back to step 4” … or “If the water is not hot yet, wait two minutes, then go back to step 3.”
Here is a plan:
Walk to the store.
Buy a food.
Come back home.
You’re done!
Here is another plan:
Walk to the store.
Buy a food.
Come back home.
Go back to step 1.
There is something funny about the second plan! If we started following that plan, we would never stop. We would just keep walking to the store, buying a food, and walking back home. Forever. (Or until we decide it is a dumb plan and we should stop following it. But a computer couldn’t do that.)
You may have heard songs like “The Song That Never Ends” or “Ninety-Nine Bottles of Drinks on the Wall”. Both of these songs are like plans. When you are done singing a part of the song, you follow a plan step to get to the next part. In “The Song That Never Ends”, you just go back to the beginning. But in “Ninety-Nine Bottles of Drinks on the Wall”, you take one away from the number of bottles of drinks. And if there are no more bottles, you stop! But if there are more bottles, you sing the next part. Even though it is a very long song, it does have an end.
(There is a bad joke about people who write plans for computers. It is also a joke about hair soap. There is a plan written on the hair soap bottle:
Put hair soap in your hair.
Use water to get the hair soap out of your hair.
Repeat.
The person who writes plans for computers starts washing their hair and does not know when to stop!
Normal people know that “repeat” just means “do it a second time, then stop” and not “keep doing it forever”. But in a computer plan, it would mean “do it forever”.)
It is nice to know out how long a plan will take for us to do. It is really nice to know if it is one of those plans that never ends. If it is, then we could just say, “I won’t follow this plan! It never ends! It is like that dumb song or the bad joke!”
Can we have plans for thinking about other plans? Yes, we can!
Suppose that we found a plan, and we did not know what kind of plan it is. Maybe it is a plan for how to make a food. Or maybe it is a plan for how to go by car to another city. Or maybe it is a plan for how to build a house.
We don’t know. Can we have a plan for finding out?
Yes! Here is a plan for telling what kind of plan it is:
Get paper and a writing stick.
Start at the first step of the plan we are reading.
Read that step. (Do not do the things that step says to do! You are only reading that plan, not following it. You are following this plan.)
Write down all of the names of real things (like food, roads, or wood) that the step uses. Do not write down anything that is not a name of a real thing. Do not write down numbers, action words, colors, or other words like those.
Are there more steps in the plan we are reading? If so, go to the next step of the plan we are reading, and go back to go back to step 3 of this plan. If not, go on to step 6 of this plan.
Look at the paper that we wrote things down on.
If most of the things on the paper are food and kitchen things, say that the plan is a plan for making food.
If most of the things on the paper are car things, roads, and places, say that the plan is a plan for going to a city.
If most of the things on the paper are wood and building things, say that the plan is a plan for building a house.
If most of the things on the paper are paper, writing sticks, and steps of plans, say that the plan is a plan for reading plans!
So we can have a plan for reading and thinking about other plans. This plan is not perfect, but it is pretty good. It can even tell if a plan is a plan for reading plans. This is like looking in the mirror and knowing that you are seeing yourself. It is a very interesting thing!
But …. can we make a plan for telling if a plan will end or not? That is a hard problem.
Let’s imagine that we have a plan for reading other plans and saying if they will end. Our imaginary plan is called E, for Ending. We want to know if a plan like E is possible. We do not know what the steps of plan E are. All we know is that we are imagining that we can follow plan E to read another plan and say whether it will end or not. (We need a name for this other plan. We’ll call it X.)
But wait! We know there are plans that sometimes end, and sometimes go on forever. Here is one —
Plan Z:
Start with a number.
If our number is zero, stop.
Make our number smaller by 1.
Go to step 2.
Plan Z will always stop if the number we start with is bigger than zero and is a whole number. But if our number is one-half (or something else not whole) then Z will never end. That is because our number will go right past zero without ever being zero.
Plan Z is not really whole by itself. It needs something else that we give it: the number in step 1. We can think of this number as “food” for the plan. The “food” is something Z needs in order to go, or even to make sense. Some food is good for you, and some is bad for you … … and whether Z ends or not depends on what number we feed it.
Plan Z ends if we feed it the number 1 or 42, but not if we feed it the number one-half.
And so when we ask “Will plan X end?” we really should ask “Will plan X end, if we feed F to plan X?”
So in order to follow plan E, we need to know two things: a plan X, and a something called F. (What kind of something? Whatever kind X wants. If X wants a number, then F is a number.
If X wants a cookie, then F is a cookie. If X wants a plan to read, then F is a plan.) Following E will then tell us if X-fed-with-F will end or run forever.
Now here is another plan —
Plan G:
Start with a plan. Call it plan X.
Follow plan E to read plan X, with plan X as food. This will tell us if plan X will end or not.
Now, if E told us that X never ends, then stop!
But if E told us that X stops, then sing “The Song That Never Ends”.
So when we follow plan G, we don’t do the same thing that X does. We do the other thing! If X never ends, then G ends. And if X ends, then G never ends.
But what happens if X is G? G is a plan, and G wants a plan for its food. So we can feed G to G itself! If we feed G to G, then G will end if G doesn’t end. And G will go on forever if G ends.
That does not make any sense at all. Everything about that makes no sense! It is like saying “If the cat is white, then the cat is not white.” It is really wrong!
What part is wrong, though? G is very simple. There is nothing wrong with G. The wrongness is in the thing that we imagined:
Plan E, the plan that can tell us if any plan will end or not.
This means that E is not really possible. That is the part that looked like it might make sense, but really it did not. Oh well. It sure would be nice if E was possible. But it is not.
So what is Mr. Turing’s computer like? It has these parts:
The long piece of paper. The paper has lines on it like the kind of paper you use in numbers class at school; the lines mark the paper up into small parts, and each part has only enough room for one number. Usually the paper starts out with some numbers already on it for the computer to work with.
The head, which reads from and writes numbers onto the paper. It can only use the space on the paper that is exactly under it; if it wants to read from or write on a different place on the paper, the whole head has to move up or down to that new place first. Also, it can only move one space at a time.
The memory. Our computers today have lots of memory, but Mr. Turing’s computer has only enough memory for one thing at a time. The thing being remembered is the “state” of the computer, like a “state of mind”.
The table, which is a plan that tells the computer what to do when it is each state. There are only so many different states that the computer might be in, and we have to put them all in the table before we run the computer, along with the next steps the computer should take when it reads different numbers in each state.
Looking closer, each line in the table has five parts, which are:
If Our State Is this
And The Number Under Head Is this
Then Our Next State Will Be this (or maybe the computer just stops here)
And The Head Should write this
And Then The Head Should move this way
Here’s a simple table:
Happy 1 Happy 1 Right
Happy 2 Happy 1 Right
Happy 3 Sad 3 Right
Sad 1 Sad 2 Right
Sad 2 Sad 2 Right
Sad 3 Stop
Okay, so let’s say that we have one of Mr. Turing’s computers built with that table. It starts out in the Happy state, and its head is on the first number of a paper like this:
1 2 1 1 2 1 3 1 2 1 2 2 1 1 2 3
What will the paper look like after the computer is done? Try pretending you are the computer and see what you do! The answer is at the end.
So you can see now that the table is the plan for what the computer should do. But we still have not fixed Mr. Babbage’s problem! To make the computer do different things, we have to open it up and change the table. Since the “table” in any real computer will be made of very many parts put together very carefully, this is not a good way to do it!
So here is the amazing part that surprised everyone: you can make a great table that can act like any other table if you give it the right numbers on the paper. Some of the numbers on the paper tell the computer about a table for adding, and the rest of the numbers are to be added. The person who made the great table did not even have to know anything about adding, as long as the person who wrote the first half of the paper does.
Our computers today have tables like this great table, and so almost everything fun or important that they do is given to them long after they are built, and it is easy to change what they do.
By the way, here is how the paper from before will look after a computer with our simple table is done with it:
What about Babbage’s Analytical Engine, which would have been turing-complete had it been constructed? Although it took a Countess to figure out that programming could be a thing…
I see your point (I sometimes get the same feeling), but if you think about it, it’d be much more astonishing if someone built a universal computer before having the idea of a universal computer. It’s not really common to build something much more complex than a hand ax by accident. Natural phenomena are often discovered like that, but machines are usually imagined a long time before we can actually build them.
Yeah, that’s a good point. Turing must have been one of the first people to realize that there’s a “maximum amount of flexibility” a computer can have, so to speak, where it’s so flexible it can do anything that any computer can.
Mr. Turing’s Computer
Computers in the past could only do one kind of thing at a time. One computer could add some numbers together, but nothing else. Another could find the smallest of some numbers, but nothing else. You could give them different numbers to work with, but the computer would always do the same kind of thing with them.
To make the computer do something else, you had to open it up and put all its pieces back in a different way. This was very hard and slow!
So a man named Mr. Babbage thought: what if some of the numbers you gave the computer were what told it what to do? That way you could have just one computer, and you could quickly make it be a number-adding computer, or a smallest-number-finding computer, or any kind of computer you wanted, just by giving it different numbers. But although Mr. Babbage and his friend Ms. Lovelace tried very hard to make a computer like that, they could not do it.
But later a man named Mr. Turing thought up a way to make that computer. He imagined a long piece of paper with numbers written on it, and imagined a computer moving left and right that paper and reading the numbers on it, and sometimes changing the numbers. This computer could only see one number on the paper at a time, and also only remember one thing at a time, but that was enough for the computer to know what to do next. Everyone was amazed that such a simple computer could do anything that any other computer then could do; all you had to do was put the right numbers on the paper first, and then the computer could do something different! Mr. Turing’s idea was enough to let people build computers that finally acted like Mr. Babbage’s and Ms. Lovelace’s dream computer.
Even though Mr. Turing’s computer sounds way too simple when you think about our computers today, our computers can’t do anything that Mr. Turing’s imagined computer can’t. Our computers can look at many many numbers and remember many many things at the same time, but this only makes them faster than Mr. Turing’s computer, not actually different in any important way. (Though of course being fast is very important if you want to have any fun or do any real work on a computer!)
The Halting Problem (Part One)
A plan is a list of things to do.
When a computer runs, it is doing the things that are written in a plan.
When you solve a problem like 23 × 3, you are also following a plan.
Plans are made of steps.
To follow a plan, you do what each plan step says to do, in the order they are written.
But sometimes a step can tell you to move to a different step in the plan, instead of the next one.
And sometimes it can tell you to do different things if you see something different.
It can say “Go back to step 4” … or “If the water is not hot yet, wait two minutes, then go back to step 3.”
Here is a plan:
Walk to the store.
Buy a food.
Come back home.
You’re done!
Here is another plan:
Walk to the store.
Buy a food.
Come back home.
Go back to step 1.
There is something funny about the second plan!
If we started following that plan, we would never stop.
We would just keep walking to the store, buying a food, and walking back home.
Forever.
(Or until we decide it is a dumb plan and we should stop following it.
But a computer couldn’t do that.)
You may have heard songs like “The Song That Never Ends” or “Ninety-Nine Bottles of Drinks on the Wall”.
Both of these songs are like plans.
When you are done singing a part of the song, you follow a plan step to get to the next part.
In “The Song That Never Ends”, you just go back to the beginning.
But in “Ninety-Nine Bottles of Drinks on the Wall”, you take one away from the number of bottles of drinks.
And if there are no more bottles, you stop!
But if there are more bottles, you sing the next part.
Even though it is a very long song, it does have an end.
(There is a bad joke about people who write plans for computers.
It is also a joke about hair soap.
There is a plan written on the hair soap bottle:
Put hair soap in your hair.
Use water to get the hair soap out of your hair.
Repeat.
The person who writes plans for computers starts washing their hair and does not know when to stop!
Normal people know that “repeat” just means “do it a second time, then stop” and not “keep doing it forever”. But in a computer plan, it would mean “do it forever”.)
It is nice to know out how long a plan will take for us to do.
It is really nice to know if it is one of those plans that never ends.
If it is, then we could just say, “I won’t follow this plan! It never ends! It is like that dumb song or the bad joke!”
The Halting Problem (Part Two)
Can we have plans for thinking about other plans? Yes, we can!
Suppose that we found a plan, and we did not know what kind of plan it is.
Maybe it is a plan for how to make a food.
Or maybe it is a plan for how to go by car to another city.
Or maybe it is a plan for how to build a house. We don’t know.
Can we have a plan for finding out?
Yes! Here is a plan for telling what kind of plan it is:
Get paper and a writing stick.
Start at the first step of the plan we are reading.
Read that step.
(Do not do the things that step says to do!
You are only reading that plan, not following it.
You are following this plan.)
Write down all of the names of real things (like food, roads, or wood) that the step uses.
Do not write down anything that is not a name of a real thing.
Do not write down numbers, action words, colors, or other words like those.
Are there more steps in the plan we are reading?
If so, go to the next step of the plan we are reading, and go back to go back to step 3 of this plan.
If not, go on to step 6 of this plan.
Look at the paper that we wrote things down on.
If most of the things on the paper are food and kitchen things, say that the plan is a plan for making food.
If most of the things on the paper are car things, roads, and places, say that the plan is a plan for going to a city.
If most of the things on the paper are wood and building things, say that the plan is a plan for building a house.
If most of the things on the paper are paper, writing sticks, and steps of plans, say that the plan is a plan for reading plans!
So we can have a plan for reading and thinking about other plans.
This plan is not perfect, but it is pretty good.
It can even tell if a plan is a plan for reading plans.
This is like looking in the mirror and knowing that you are seeing yourself.
It is a very interesting thing!
But …. can we make a plan for telling if a plan will end or not?
That is a hard problem.
Edited to add the italicized comment on step 3.
The Halting Problem (Part Three)
Let’s imagine that we have a plan for reading other plans and saying if they will end.
Our imaginary plan is called E, for Ending. We want to know if a plan like E is possible.
We do not know what the steps of plan E are.
All we know is that we are imagining that we can follow plan E to read another plan and say whether it will end or not.
(We need a name for this other plan. We’ll call it X.)
But wait! We know there are plans that sometimes end, and sometimes go on forever. Here is one —
Plan Z:
Start with a number.
If our number is zero, stop.
Make our number smaller by 1.
Go to step 2.
Plan Z will always stop if the number we start with is bigger than zero and is a whole number.
But if our number is one-half (or something else not whole) then Z will never end.
That is because our number will go right past zero without ever being zero.
Plan Z is not really whole by itself.
It needs something else that we give it: the number in step 1.
We can think of this number as “food” for the plan.
The “food” is something Z needs in order to go, or even to make sense.
Some food is good for you, and some is bad for you …
… and whether Z ends or not depends on what number we feed it.
Plan Z ends if we feed it the number 1 or 42, but not if we feed it the number one-half.
And so when we ask “Will plan X end?” we really should ask “Will plan X end, if we feed F to plan X?”
So in order to follow plan E, we need to know two things: a plan X, and a something called F.
(What kind of something? Whatever kind X wants.
If X wants a number, then F is a number. If X wants a cookie, then F is a cookie.
If X wants a plan to read, then F is a plan.)
Following E will then tell us if X-fed-with-F will end or run forever.
Now here is another plan —
Plan G:
Start with a plan. Call it plan X.
Follow plan E to read plan X, with plan X as food.
This will tell us if plan X will end or not.
Now, if E told us that X never ends, then stop!
But if E told us that X stops, then sing “The Song That Never Ends”.
So when we follow plan G, we don’t do the same thing that X does.
We do the other thing!
If X never ends, then G ends.
And if X ends, then G never ends.
But what happens if X is G?
G is a plan, and G wants a plan for its food. So we can feed G to G itself!
If we feed G to G, then G will end if G doesn’t end.
And G will go on forever if G ends.
That does not make any sense at all.
Everything about that makes no sense!
It is like saying “If the cat is white, then the cat is not white.”
It is really wrong!
What part is wrong, though?
G is very simple. There is nothing wrong with G.
The wrongness is in the thing that we imagined: Plan E, the plan that can tell us if any plan will end or not.
This means that E is not really possible.
That is the part that looked like it might make sense, but really it did not.
Oh well.
It sure would be nice if E was possible.
But it is not.
So what is Mr. Turing’s computer like? It has these parts:
The long piece of paper. The paper has lines on it like the kind of paper you use in numbers class at school; the lines mark the paper up into small parts, and each part has only enough room for one number. Usually the paper starts out with some numbers already on it for the computer to work with.
The head, which reads from and writes numbers onto the paper. It can only use the space on the paper that is exactly under it; if it wants to read from or write on a different place on the paper, the whole head has to move up or down to that new place first. Also, it can only move one space at a time.
The memory. Our computers today have lots of memory, but Mr. Turing’s computer has only enough memory for one thing at a time. The thing being remembered is the “state” of the computer, like a “state of mind”.
The table, which is a plan that tells the computer what to do when it is each state. There are only so many different states that the computer might be in, and we have to put them all in the table before we run the computer, along with the next steps the computer should take when it reads different numbers in each state.
Looking closer, each line in the table has five parts, which are:
If Our State Is this
And The Number Under Head Is this
Then Our Next State Will Be this (or maybe the computer just stops here)
And The Head Should write this
And Then The Head Should move this way
Here’s a simple table:
Okay, so let’s say that we have one of Mr. Turing’s computers built with that table. It starts out in the Happy state, and its head is on the first number of a paper like this:
What will the paper look like after the computer is done? Try pretending you are the computer and see what you do! The answer is at the end.
So you can see now that the table is the plan for what the computer should do. But we still have not fixed Mr. Babbage’s problem! To make the computer do different things, we have to open it up and change the table. Since the “table” in any real computer will be made of very many parts put together very carefully, this is not a good way to do it!
So here is the amazing part that surprised everyone: you can make a great table that can act like any other table if you give it the right numbers on the paper. Some of the numbers on the paper tell the computer about a table for adding, and the rest of the numbers are to be added. The person who made the great table did not even have to know anything about adding, as long as the person who wrote the first half of the paper does.
Our computers today have tables like this great table, and so almost everything fun or important that they do is given to them long after they are built, and it is easy to change what they do.
By the way, here is how the paper from before will look after a computer with our simple table is done with it:
I’m actually surprised that Turing machines were invented before anyone ever built an actual computer.
What about Babbage’s Analytical Engine, which would have been turing-complete had it been constructed? Although it took a Countess to figure out that programming could be a thing…
I see your point (I sometimes get the same feeling), but if you think about it, it’d be much more astonishing if someone built a universal computer before having the idea of a universal computer. It’s not really common to build something much more complex than a hand ax by accident. Natural phenomena are often discovered like that, but machines are usually imagined a long time before we can actually build them.
Yeah, that’s a good point. Turing must have been one of the first people to realize that there’s a “maximum amount of flexibility” a computer can have, so to speak, where it’s so flexible it can do anything that any computer can.