fubarobfusco comments on The Up-Goer Five Game: Explaining hard ideas with simple words - Less Wrong

29 Post author: RobbBB 05 September 2013 05:54AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (82)
Tags: xkcd english simple words taboo games

Comments (82)

You are viewing a single comment's thread. Show more comments above.

Comment author: fubarobfusco 07 September 2013 01:20:47AM *  5 points [-]

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:

  1. Get paper and a writing stick.
  2. Start at the first step of the plan we are reading.
  3. 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.)
  4. 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.
  5. 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.
  6. Look at the paper that we wrote things down on.
  7. If most of the things on the paper are food and kitchen things, say that the plan is a plan for making food.
  8. 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.
  9. If most of the things on the paper are wood and building things, say that the plan is a plan for building a house.
  10. 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.

Comment author: fubarobfusco 10 September 2013 06:23:18AM *  2 points [-]

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:

  1. Start with a number.
  2. If our number is zero, stop.
  3. Make our number smaller by 1.
  4. 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:

  1. Start with a plan. Call it plan X.
  2. Follow plan E to read plan X, with plan X as food.
    This will tell us if plan X will end or not.
  3. Now, if E told us that X never ends, then stop!
  4. 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.

Powered by Reddit Powered by Reddit