h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

Entry: The Halting Problem - A1080596
Author: Atlantic_Cable - U196159

I've had this in writing workshop and now submit it for peer review. I hope it's clear enough.

Nope

While I have some basic knowledge of Turing Machines and Godel's Undecidability theorem as concepts, I found this explanation of the problem quickly left me out of my depth. I was much more comfortable when the entry got back to the description of the consequences of the the halting problem.

As an idea (that you may hate) you could lose the nitty gritty of the mathematical explanation, and gloss over how it works, leading more quickly to the practical results.

It might also be useful to consider in the introductory paragraph that the entry will discuss 'why computers can't easily avoid crashing' - this would also be a good title, more likely to grab the attention if one hasn't heard of the problem before.

Pimms

There are one or two typos too - do you want to know about them?

I tend to agree with PImms, AC. You lost me in the first section. I didn't understand what a halting problem was (and if and why it's important). Maybe if it's explained a little more?

I like the article, but it needs to be clearer. It starts off saying: 'In 1936 Alan Turing invented the Turing Machine..' but then never really says what the Turing machine is. Maybe hold off on talking about turing machines straight off and pose the question 'Could a modern computer programmer write a program which works out if another program will ever stop, or will go on running forever?' This means people will see something that they understand as a problem straight off and then you could go back and explain about Alan Turing..

Thanks for the comments!

I've made a few alterations to the introduction. Please tell me what you think.

I think this is good, but does need some work. Some comments:

First of all, I think you could mention at least some of the points I made when we discussed this at F48874?thread=208128&latest=1 (that although this explains why software can't predict its future behaviour, this isn't too relevant to actual application design). In particular, you could mention in the "A Solution?" section, that another solution is to just recognise when a program has crashed (it stops responding to input) and stop running it.

I think you could change the introductory section a bit. It's not important that Turing originally specified that it should have an infinite tape, etc. I think you should either say more about this (in a section of its own) - why he came up with that specification - or you should say less, i.e. all he needed was a mathematical idealisation of a computer with infinite storage space. I think it would be better to always talk about "computer program" rather than "Turing machine program", and so forth, except maybe in a section on Turing machines where you could talk about Turing's original ideas.

Don't use the phrase "natural number", say "whole number" instead (more people will understand then). You might also mention how the "description number" is associated with the program (e.g. you could say that the program's file on the disk is in binary and so you can think of it as just a large number, I think there is an EG entry on binary you could link to).

You might like to say what "reductio ad absurdum" means.

I think you've made a mathematical mistake in the section on partial solutions. You give the fact that we don't know whether the program "for(i=j=k=1;--j||k;k=j?i%j?k:k-j: (j=i+=2));" halts as a reason for not knowing the solution to the PHS, but you can't argue that it can't be solved because we don't know how to solve this particular example. Also, that program is in C and not everyone will be able to understand what it does, and not only that it's in obfuscated C which is the worst sort. You don't explain why nobody knows if it halts.

You could mention that you can safely skip the maths bits, and mark those sections with mathsy bits in it.

Thanks very much for your comments.

I have made a few alterations, but would like to ask you the following:

I think that marking the mathsy bits is a good idea, but I am uncertain the best way to do it. Any suggestions?

The Turing machine is necessary because the Halting prob was first proposed on TMs and all the maths is based on them, mainly because it simplifies it enourmously.

I'm afraid the part of your posting about the maths error lost me completely. I admit it is late at night and I will try reading it again in the morning.

Thanks.

I'd just put something like: "You can skip this section if maths is not your thing." Well, perhaps something more formal. You might find it interesting to take a look at my article with a mathsy bit in it marked off: A568613.

I know that the halting problem was first done with TMs, but they're not the most logical or intuitive way of doing it, and your proof of the undecidability of the halting problem doesn't actually use the definition of TMs as tape reading and modifying devices, it uses the idea of TMs as abstract computers. It might even make sense, if you must introduce a particular implementation of "abstract computer" to introduce the notion of "register machines" which are a modern version of TMs and are more like the way computers actually work. But really, I think it makes more sense to say "just think of what a computer with an infinite amount of memory could do" than to talk about infinitely long tape and obscure stuff like that. You can even justify it then by saying "If a computer with infinite memory can't do it - certainly a computer with finite memory can't do it".

Hi AC
Re-read entry. One thing that struck me was footnote 2: 'The program's file on the disk is in binary and so you can think of it as just a large number.'

Since you haven't introduced disks already it might be better to say:
'Every computer program file can be read as a (very) long string of 1's and 0's that can be thought of as a single (large) number, expressed in binary.'

I think that is clearer.

Pimms

Thanks, I've changed it.

Hi Atlantic Cable!

I didn't follow the proof in detail but I will take your word for it that it is correct.


I think there are some problems in the entry which need to be addressed.

You talk about the halting problem, but you never say what halting is in the introduction. You should explain that Turing programs either halt when they have arrived at the results or else they continue for ever. No Turing program can be said to have produced any results until it has halted.

You say that a Turing program never halting is the equivalent of crashing. This is not really true. A crashed computer can halt producing an error message. But they are certainly similar.

You say that as more of the code can be checked by program verifiers, the chances of the program not halting are reduced. This gives the impression that the halting problem is about mistakes in the code. This is not so. There are plenty of mathematical problems where the program is doing exactly what it is supposed to do, but the program will never halt. For example, asking the program to keep going until it finds an odd number which is equal to the sum of its divisors. The program may halt when it finds one, or it may never halt, even though it is working perfectly. We have no way of knowing, because it is not known whether such a number exists.

There are some typos and grammar mistakes:

crach --> crash
analysise --> analyse
relevent --> relevant
asking computers can't --> asking why computers can't
most common used --> most commonly used
program, however --> program. However
the maths in this entry aren't --> the maths in this entry isn't
the accuracy of these guesses are --> the accuracy of these guesses is

Thanks! I've made a few alterations.

Seems good to me, I was wondering if it would gain a wider readership if you changed the title to "Why computers still crash"?

Did you sort the typos because there were two jumped out and hit me on the nose? Do you want to know what they are?



NB: is this a general 'all computers' thing. My Apple Mac seems to be remarkably stable.

Why computers still crash would be a much more general entry. I might do one sometime.

This is an "all computers" thing. Turing machines were invented before computers. A TM can simulate any computer and a computer can simulate any TM. Any TM can also simulate any other TM. This is where the idea of emulation comes in. I myself have a semi-descent Mac emulator for my PC.

Thanks for the comments.

Oh, BTW I don't know where the typos are. Any help would be appreciated.

Are you still working on this, Atlantic Cable?

No, I'm pretty much done with it.

Your Guide Entry has just been picked from Peer Review by one of our Scouts, and is now heading off into the Editorial Process, which ends with publication in the Edited Guide. We've therefore moved this Review Conversation out of Peer Review and to the entry itself.

If you'd like to know what happens now, check out the page on 'What Happens after your Entry has been Recommended?' at EditedGuide-Process. We hope this explains everything.

Thanks for contributing to the Edited Guide!

Congratulations!