Timeline for Is there a subset of programs that avoid the halting problem
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 21, 2011 at 6:40 | comment | added | user281377 | David: True, but the "practical halting problem" is a completely different kind of beast than the theoretical problem anyway. For example, as you have pointed out, a program counting to 2^128 won't complete its job in this solar system. On the other hand, from the theoretical point of view, there is no doubt that this is a program that eventually halts! A program that just writes 1s to the tape inevitably crashes in the real world with an out of memory exception, but never halts in the theoretical model. | |
| Dec 21, 2011 at 0:46 | history | edited | Alex ten Brink | CC BY-SA 3.0 | added 86 characters in body |
| Dec 21, 2011 at 0:09 | comment | added | SK-logic | @Alex ten Brink, you said that "the subset (of the always terminating programs) is amazingly useless", it was not clear that it is about some specific algorithm. | |
| Dec 20, 2011 at 23:15 | comment | added | Alex ten Brink | @SK-logic: I'm not sure what you mean. Presuming your comment was aimed at me: I don't call any programming language 'amazingly useless'. I merely think that the algorithm presented in the paper is amazingly useless, since the set of programs it works on correctly is highly uninteresting. That has nothing to do with programming languages. | |
| Dec 20, 2011 at 15:15 | comment | added | David Thornley | @ammoQ: That's similarly infeasible. Counting to something as low as 2^128 with anything resembling conventional computing would take more energy than the Sun will put out in the future. Theoretically, we're dealing with computers of essentially infinite power, and cannot in general solve the Halting Problem. Practically, we're dealing with computer of limited size, which means the HP is solvable on a theoretical computer of infinite power, but can't be solved with only the resources in the known Universe. | |
| Dec 20, 2011 at 11:52 | comment | added | SK-logic | It is somewhat insulting to call languages like Agda2 and Coq "amazingly useless". For example, there is a complete C compiler written in Coq. Is it a "useless" application for a language? | |
| Dec 20, 2011 at 8:05 | comment | added | user281377 | Alex: Ok, now it's more clear what you mean. It should be more clearly said that the method described in the paper depends on the turing machine. I thought it was a general statement about the halting problem. The second issue is more clear now, too. So I'll take back the -1. | |
| Dec 20, 2011 at 7:42 | comment | added | user281377 | David: On a computer with n bits of storage, a program can run at most through 2^n different states before either looping or halting. While it is infeasible to build a computer with a 2^n bits (so you can mark each state that has been reached), all it really takes is a n bit counter; on every clock tick of the target system, just increase the counter by one. If it overruns, we have detected a loop. So we need a little bit of overhead for the program that handles the counter, but that is not the problem. We need some time, though, so the heat death of the universe might become an issue. | |
| Dec 19, 2011 at 22:52 | comment | added | David Thornley | @ammoQ: No, the halting problem is not solvable if you are talking about real-world systems with limited storage, as that would mean building a real-world system that can handle combinations of states. As the number of possible register states in most CPUs exceeds the number of atoms in the Universe, you aren't going to be able to do that. | |
| Dec 19, 2011 at 21:54 | history | edited | Alex ten Brink | CC BY-SA 3.0 | added 227 characters in body |
| Dec 19, 2011 at 21:51 | comment | added | Alex ten Brink | As for your second issue: the states I'm talking about is not the same as the 'state of a machine' one usually talks about (which involves the state of everything that can have state), but rather the state the finite state automaton used to control the Turing machine is in, which roughly corresponds to the line of code a program is working on at any point during execution. On repeating a line of code the contents of your memory may be different, so this does not immediately imply halting at all. I'll update my answer to make this more clear. | |
| Dec 19, 2011 at 21:50 | comment | added | Alex ten Brink | As for your first issue: as remarked in the paper, showing that some model of computation is Turing complete does not preserve how many programs exactly halt, so the result they prove does not immediately mean anything for other models of computation. I'm well aware of Turing completeness, and I'm not completely sure why it makes my answer 'wrong'. | |
| Dec 19, 2011 at 20:26 | comment | added | user281377 | First, real-worlds computers cannot compute anything that a Turing machine can't. Till now, nobody has shown a real-world computer more capable (in terms of computablity) than a Turing machine. Second, if a program repeats it's state, it won't halt, so the halting problem is solved for that program and input. Remember: The halting problem is about deciding whether or not a program will halt on given input. An infinite loop is ok once you positively detect it. Finally: There is a large set of useful programs for which the halting problem is solvable: Those operating on limited storage. | |
| Dec 19, 2011 at 20:19 | comment | added | user281377 | -1, This is wrong on so many levels... | |
| Dec 19, 2011 at 12:20 | history | answered | Alex ten Brink | CC BY-SA 3.0 |