Talk:Halting problem

This article is an atrocious misrepresentation of the halting problem -- would it be permissible for me to rewrite it? NekoMimi 20:35, 7 February 2011 (EST)

Please do. Karajou 20:46, 7 February 2011 (EST)

The current version is a vast improvement. I'd like to suggest that particular and extreme care be taken in defining what "halt" means. (Not criticizing the existing change; just suggesting further improvement.) To people not well versed in theoretical computer science, "halt" might be taken to mean "hang" and "crash" or even "blue screen of death". You need to be very clear that "halt" is taken to mean "run to completion, obtaining the answer, and announcing that the program is finished." Of course "hang", in the sense of "run forever" is the opposite of that. The example given certainly shows that, but I wonder if a slightly nontrivial version could be given, like, "if x is even, divide by 2, if x is odd, multiply by 3 and add the integer part of the square root, and continue until you get 1". For what values of x will this get to 1 and halt? Not so easy. (I'm just making that up off the top of my head; there very well may be truly undecidable functions that are that simple.) Another thing to consider, much more ambitious, is to show the undecidability of the halting problem -- "Suppose we had a program (that is, a Turing machine; not sure how far we want to go there) that could look at a program and argument and say, yes or no, whether that program, with that argument, would halt. Then concoct a tricky program built on the given program, feed it to itself, and get a contradiction." The concocting of the tricky program based on the original program is fairly simple, but the explanation of what it means for a program to look at another program is what is hard. Just a thought. SamHB 16:22, 12 February 2011 (EST)