| Latest revision |
Your text |
| Line 16: |
Line 16: |
| | 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) | | 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) | | :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) |
| − | :Alternatively, "big picture" people aren't really concerned with details. "You want to know if it halts? I'm telling ya baby, it halts!" The value of such an assertion is dubious, but it does save a lot of worrying. You know what else is funny? The mind-numbing amount of detail in these responses to a comic about the the "big picture". Reflect, people, reflect! [[Special:Contributions/108.162.219.58|108.162.219.58]] 23:04, 4 February 2014 (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) | | 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) |
| Line 25: |
Line 24: |
| | 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) | | 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?
| + | == 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) | | 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)
| |
| − |
| |
| − | ::::Irrelevant load. Randall is not concerned with multiple nodes or hypervisors, he is simply demonstrating the "big picture" solution to an undecidable problem in computing. It is *not possible* in general to determine if 'program' will halt or not, so don't even look at it. Sidestep the work and just return your best guess. That's how people frequently operate, right? [[Special:Contributions/108.162.219.58|108.162.219.58]] 23:04, 4 February 2014 (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)
| |
| − |
| |
| − | :There is a problem with this argument. What you have shown is that if there exists an algorithm A that solves the halting problem, then there is an algorithm B that solves the "all-input-halting-problem". However, the all-input-halting-problem is harder in the following sense: Given an oracle (i.e., some "magic" machine that gives the correct answer even though there exists no algorithm for doing so) for the halting-problem, you cannot solve the all-input-halting-problem. But given an oracle for the all-input-halting-problem, it is easy to solve the halting problem. (Your proof does not contradict this, because if A is an oracle, then Y is not a Turing machine and cannot be fed to A.) Basically, the all-input-halting-problem is one step higher on the arithmetical hierarchy (https://en.wikipedia.org/wiki/Arithmetical_hierarchy). [[Special:Contributions/172.69.138.46|172.69.138.46]] 22:24, 10 March 2019 (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)
| |
| − | :Popper claimed that such things are outside the realms of science, correct? The undecidability of this question has been used to falsify other intended scientific proofs. Therefore, it is surely within the realms of science. [[Special:Contributions/108.162.219.58|108.162.219.58]] 23:04, 4 February 2014 (UTC)
| |
| − |
| |
| − | ;Bad example for showing the difference between theoretical computation and "actual" computation
| |
| − |
| |
| − | The explanation's "1/3 + 1/3 + 1/3 = 1" example ticks me off: symbolic math programs can already give the correct answer to this easily. See http://www.sympygamma.com/input/?i=1%2F3+%2B+1%2F3+%2B+1%2F3 . {{unsigned ip|108.162.229.53}}
| |
| − |
| |
| − | :You're misunderstanding it. "1/3 + 1/3 + 1/3 = 1". You won't -always- get 1 using every implementation. But the answer is always 1. What a computer outputs and what the truth is are not -always- the same thing. It wasn't implied that they are -never- the same thing. It's only a bad example if you always get "1/3 + 1/3 + 1/3 = 1". {{unsigned ip|162.158.145.84}}
| |
