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

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

Just a little entry on a complicated subject.

Beig a computer science graduate this entry makes prefect sense to me, but I have the feeling that it's as clear as a train station announcer eating a sandwich.

Any ideas on how to clear it up would be gratefully appreciated.

Have to admit I don't follow the mathematical part but that's probably my inadequacy at least as much as your explanation.

The HP and GIC are both self reference problems, yes?

The most general statement of the problem of self prediction is that a predicting machine may not predict its own future internal states because in order to do so it would have to contain as PART of itself a COMPLETE model of itself.

Hope that helps.

Noggin

His they are self referencing problems.

That helps enourmously, thanks.

While it is true that the halting problem is currently one of the unsolvable problems in computing, there is also the possibility that in the future it won't matter.

there is a field of computing which deals with proving the correctness of programs. this already allows you (with very small programs) to prove which parts of the program are known to not have common trouble spots in them.

while this doesn't prove that the program has no errors, it does provide extra levels of debugging based solely on the programs structure.

similarly, there are tools out there which can give you a reachability graph for your program, which can also help massively with debugging.

so while the halting problem is currently veiwed as being unsolvable, you are now getting lots of tools appearing which can be used to make it a lot less relevent most of the time.

Thanks for the input, it was just what I was needing to add a conclusion section to the entry.

It also jogged my memory about some of the things in that computability course I took.

What do you think?

I would make a couple of changes, and then stick it in peer review.

first, the title. it's known as "the halting problem", not "the turing halting problem".

second, you say "students call it 'That Awkward Bugger' ", but it would probably be better to say "students call it 'That Awkward Bit' ".

keep up the good work.