Talk:1266: Halting Problem

Explain xkcd: It's 'cause you're dumb.
Revision as of 23:52, 20 September 2013 by Bpothier (talk | contribs) (Missing the obvious?: new section)
Jump to: navigation, search

I wrote an explanation for the body of the comics, but I believe there are aspects of the title I'm still missing, so I left the incomplete tag in place. Shachar (talk) 07:52, 18 September 2013 (UTC)

Isn't google already running applications designed to continue running even if some of nodes they run on have a fatal hardware failure? Also, even if the claim would be true in "practical" sense, it would not solve the problem, because as you said, the stopping would be because of reasons external to the actual program. In other words, program running on turing machine will never stop by hardware failure, because turing machine BY DEFINITION doesn't have any. -- Hkmaly (talk) 08:57, 18 September 2013 (UTC)

Remembered this is wiki and added it to the actual explanation :-) -- Hkmaly (talk) 09:10, 18 September 2013 (UTC)
Several systems are running with redundant nodes. They will not run forever. They are in for example extremely unlikely to outlive the sun. 85.19.71.131 11:29, 18 September 2013 (UTC)
System with ability to replace nodes can be deployed on nodes physically as distant as needed. Application which is currently starting on a multi-node system on earth can be later expanded to system with nodes in different star system. Although unless the nodes have FTL connection it would have inpractically large lag ... -- Hkmaly (talk) 09:39, 20 September 2013 (UTC)

"For all practical purposes, this is the correct solution"

No, it's not. A very practical purpose would be "have my OS kill processes that won't stop". Other one would be "reject installing apps that contain algorithms that don't halt". If the OS assumes "every app will eventually halt" it would kill every process and reject every app. Osias (talk) 12:15, 18 September 2013 (UTC)
Changing the paragraph to say "a physical perspective" instead of "all practical purposes" was a good solution. Osias (talk) 14:16, 18 September 2013 (UTC)
It would, in fact, kill/reject none since it would find no nonhalters.178.0.89.106 20:51, 18 September 2013 (UTC)


Google "halting problem" and do a little reeding so you are in the same mindset as Randall. This is a famous computer science problem. You aren't talking about the same thing in comments above. tbc (talk) 12:30, 18 September 2013 (UTC)

What is the joke here? What does "big picture" mean? 62.209.198.2 16:33, 18 September 2013 (UTC)

I believe it's related to the quote " In the long run we are all dead." by John Maynard Keynes. Osias (talk) 18:46, 18 September 2013 (UTC)

Same kind of humor as in http://www.explainxkcd.com/wiki/index.php?title=221 176.67.13.14 18:47, 18 September 2013 (UTC)

A program with its given input can be seen, as a whole, as a specific program. Therefore the halting function need not take two inputs and is equivalent to a function that takes the two described inputs. Therefore I feel the comment about the number of inputs in the explanation can be removed. 66.69.243.27 (talk) (please sign your comments with ~~~~)

Yeah, the halting problem on the empty word/input is known to be equivalent to the general halting problem. I think that's the form used in this comic. 85.218.82.16 (talk) (please sign your comments with ~~~~)

Might there be a reference here to Isaac Asimov's famous story "The Last Question"? (The titular question was: 'Can entropy be reversed?' Throughout the lifetime of the universe, the computer only said: 'THERE IS INSUFFICIENT DATA FOR A MEANINGFUL ANSWER.') 174.239.229.68 04:18, 20 September 2013 (UTC)

Missing the obvious?

Maybe it is just me, but I interpreted this to be the "DoesItHalt" function actually *running* "program", then when "program" completes (halts) it returns true. This would be the "big picture" solution and does not actually deal with the "details". --B. P. (talk) 23:52, 20 September 2013 (UTC)