Editing Talk:1266: Halting Problem

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. [[User:Shachar|Shachar]] ([[User talk: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. -- [[User:Hkmaly|Hkmaly]] ([[User talk:Hkmaly|talk]]) 08:57, 18 September 2013 (UTC)
:Remembered this is wiki and added it to the actual explanation :-) -- [[User:Hkmaly|Hkmaly]] ([[User talk: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. [[Special:Contributions/85.19.71.131|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 ... -- [[User:Hkmaly|Hkmaly]] ([[User talk: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. [[User:Osias|Osias]] ([[User talk: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. [[User:Osias|Osias]] ([[User talk:Osias|talk]]) 14:16, 18 September 2013 (UTC)
::It would, in fact, kill/reject none since it would find no nonhalters.[[Special:Contributions/178.0.89.106|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. ''&mdash; [[User:Tbc|tbc]] ([[User talk:Tbc|talk]]) 12:30, 18 September 2013 (UTC)''

What is the joke here? What does "big picture" mean? [[Special:Contributions/62.209.198.2|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. [[User:Osias|Osias]] ([[User talk:Osias|talk]]) 18:46, 18 September 2013 (UTC)

Same kind of humor as in http://www.explainxkcd.com/wiki/index.php?title=221 [[Special:Contributions/176.67.13.14|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. {{unsigned ip|66.69.243.27}}
: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. {{unsigned ip|85.218.82.16}}

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.') [[Special:Contributions/174.239.229.68|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". --[[User:Bpothier|B. P.]] ([[User talk:Bpothier|talk]]) 23:52, 20 September 2013 (UTC)

What you thought you saw was the most obvious "implementation" of a solution to the halting problem.
 define DoesItHalt (program):
 {
     program();
     return true;
 }
This solution returns <code>true</code> if <code>program</code> stops, and loops forever is <code>program</code> loops forever. [[User:Xhfz|Xhfz]] ([[User talk:Xhfz|talk]]) 20:44, 23 September 2013 (UTC)

: It won't work if your program is exit() or shutdownYourComputer(). :) --[[Special:Contributions/61.223.87.164|61.223.87.164]] 00:49, 28 September 2013 (UTC)

::It will. We are talking about Turing machines. A Turing machine can stop itself, but it cannot stop the calling Turing machine.  [[User:Xhfz|Xhfz]] ([[User talk:Xhfz|talk]]) 12:43, 7 October 2013 (UTC)

:::Turing machines are known to be really poor at I/O. If you trace the shutdownYourComputer function, it actually instructs your {{w|Power_supply_unit_(computer)|power supply unit}} (ATX required, AT lacked such capability) to turn power down. Similarly, rebootYourComputer function instruct outside hardware - usually {{w|Northbridge_(computing)|north bridge}} - to send a reset signal on the {{w|Peripheral_Component_Interconnect|PCI bus}} (and presumably other busses), which will reset all devices and start {{w|Power-on_self-test|POST}}. Unlike Turing machines, virtualized OSs may be able to reboot host computer if the hypervisor is not coded correctly and allows I/O for hardware acceleration. -- [[User:Hkmaly|Hkmaly]] ([[User talk:Hkmaly|talk]]) 09:22, 16 October 2013 (UTC)
; The halting problem for every input
The sentence in bold is false
:It should be noted that Randall's solution, barring its unsoundness, solves more than the halting problem in the form it is usually stated. The halting problem requires two parameters (a program and its parameters), while Randall's function only accepts one (the program). The question of whether a program halts for every input '''can be shown to be even harder to solve''' than the halting problem, meaning that even if a Turing machine had an additional instruction allowing it to check whether a program halts with given parameters, it still could not always confirm that a given program that halts for all parameters does so.
In fact, let A be a Turing machine that solves the halting problem for one input, and B a Turing machine that solves the halting problem for every input. B can be built using A as a subroutine. First B builds machine Y that takes its input, X, and halts if X loops with at least one input; Y loops if X stops for every input.
:Turing machine B (Turing machine X) {
:// manipulate X in order to build Y that calls X for every input and stops when the first input does not halt
: Y = <code>"s = <nowiki>''</nowiki>; repeat { if (A(" + X + "," s + ") == 'false' then halt; s = next(s);}"</code>
: return A(Y, "") // second parameter is ignored
:}
The function next returns the next valid string. For example, if our alphabet is A..Z0..9, then next("AJ38YT") = "AJ38YU"

Machine B determines if Y halts. And Y halts if machine X does not halt. If we had Turing machine A then we could build B. 
[[User:Xhfz|Xhfz]] ([[User talk:Xhfz|talk]]) 17:53, 18 October 2013 (UTC)

; Karl Popper
I think that the title text is a direct reference to Karl Popper's falsifiability argument, since this is one of the most common example of a non-falsifiable statement. [[User:Bonob|Bonob]] ([[User talk:Bonob|talk]]) 19:01, 18 October 2013 (UTC)