5 ms·

> There are even models of computation where the halting problem is solvable (typically called hyper-computation). BTW, it's not only hyper-computation that ca

> There are even models of computation where the halting problem is solvable (typically called hyper-computation). BTW, it's not only hyper-computation that can solve the halting problem. The halting problem is decidable in models of computation that have finite state (although the decider machine does need more state than the machine being analyzed).

tsimionescu 3y ago
The term "the halting problem" typically refers to the problem "given a Turing machine and a starting state of the tape, determine if the Turing machine will halt". There are other versions of the halting problem for systems that are more limitted than a Turing machine, such as finite automata ("given a finite automaton and an initial state, determine if the automaton will halt"). Some of these other versions are indeed solvable, such as the one you mention. But these are different problems, not the same problem as THE halting problem. As far as it is known today, all such systems are strictly less powerful than Turing machines (that is, for any system where it is provable if a computation in that system halts, there are problems that it can't solve that a Turing machine can) - this is known as the Church-Turing thesis. Hyper-computation refers to models of computation where THE halting problem (does an arbitrary Turing machine halt) is solvable.
- someplaceguy 3y ago
  I meant "the halting problem" as in the informal description of the problem, e.g. as in how it is described in Wikipedia: "the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever". If you take that description at face value and consider a model of computation with finite state (like real-world computers have), then it is decidable. If you take the usual formal description of the halting problem, which like you said, is specifically defined over Turing machines (i.e. a theoretical model which assumes you can have a machine with literally infinite state, which is impossible to construct in our universe), then yes, you'd need hyper-computation to solve that.
  - tsimionescu 3y ago
    I thought initially you are referring to things like deterministic finite automata (DFAs) or total languages (Idris) when you are talking about finite state. If instead you are simply referring to the observation that physical computers have a finite amount of memory and thus we can solve the halting problem in finite time by simply iterating over all possible configurations, that is a somewhat uninteresting observation - since if we are already talking about real physical constraints, that algorithm is entirely useless for even the simplest computers from the 50s and 60s. It's basically equivalent to saying "any program will halt, because the sun will destroy all computers on Earth when it goes supernova". More interestingly, it turns out that there are some finitist versions of the halting problem for finite-tape Turing machines, and they act as a similar kind of limit. That is, it turns out that the only way to verify whether an arbitrary finite-state Turing machine will halt on a specific input is to check all possible states (and this also requires a finite-state Turing machine with a larger tape than the one under analysis). This result can actually be used in a very similar way to the infinite-tape halting problem: it 100% guarantees that, if your system is equivalent to a Turing machine with tape length N and M possible symbols, it will take more than N^M computational steps to check whether an arbitrary program holds. This can be used to prove that it is effectively impossible to check if a program halts, much the same as the "true" halting problem is used to prove that it is actually impossible to check. For an example, an arbitrary program for a computer with as much memory as the infamous "640KB is enough for anyone" quote would require at least 640,000^255 (~10^1480) computational steps to check if it halts. So, we can just as easily say it is impossible to check and we wouldn't be far off. This is very different from something like a total language (e.g. Idris) or a DFA, where it is actually possible to relatively quickly verify whether a program halts.
    - someplaceguy 3y ago
      > thus we can solve the halting problem in finite time by simply iterating over all possible configurations, that is a somewhat uninteresting observation It is, but that's not the observation I was making. You only mentioned one way of solving the problem, but that's not the only way. > That is, it turns out that the only way to verify whether an arbitrary finite-state Turing machine will halt on a specific input is to check all possible states What do you mean by all possible states? If you mean literally all possible states, that's not true. I mean, yes, you could iterate over all possible states to solve that problem, but that's probably the least efficient way to solve it. There are already-known algorithms which always solve the Halting problem for machines with finite state, and they don't need to iterate over all possible states. They do, however, need to iterate over all state transitions that the machine actually goes through (multiple times, even). However, these algorithms that I'm mentioning (i.e. cycle detection algorithms) are also quite dumb. They don't exploit any knowledge about the state transitions in order to analyze whether the machines halt or not, they just simulate the machine step by step (this is due to the definition of the cycle detection problem itself, which does not allow inspecting the program). In principle, and even in practice, it's possible to make those algorithms significantly more efficient, at least for many of the machines (i.e. programs) that we care about. I suspect it is not possible to make such a (fully automatic) algorithm significantly more efficient for all possible programs (even the nonsensical ones), although I don't think such a proof exists (if it does, I would like to see it). The closest I've been pointed to is a paper possibly implying that such an algorithm would have to be EXPTIME-complete, although even the person that pointed me to that paper had some difficulty interpreting it -- and even if that were true, that says nothing about its real-world efficiency. > That is, it turns out that the only way to verify whether an arbitrary finite-state Turing machine will halt on a specific input is to check all possible states Can you point me to a source that proves this claim? Not only I'm doubting it, but even if you are right, I'd be really interested in reading such a proof. > For an example, an arbitrary program for a computer with as much memory as the infamous "640KB is enough for anyone" quote would require at least 640,000^255 (~10^1480) computational steps to check if it halts. Again, I'm wondering why you are claiming that the only possible algorithms which can check whether arbitrary finite-state programs halt have to iterate over all possible states (or even all the actual state transitions).

tsimionescu 3y ago

The term "the halting problem" typically refers to the problem "given a Turing machine and a starting state of the tape, determine if the Turing machine will halt". There are other versions of the halting problem for systems that are more limitted than a Turing machine, such as finite automata ("given a finite automaton and an initial state, determine if the automaton will halt"). Some of these other versions are indeed solvable, such as the one you mention. But these are different problems, not the same problem as THE halting problem. As far as it is known today, all such systems are strictly less powerful than Turing machines (that is, for any system where it is provable if a computation in that system halts, there are problems that it can't solve that a Turing machine can) - this is known as the Church-Turing thesis. Hyper-computation refers to models of computation where THE halting problem (does an arbitrary Turing machine halt) is solvable.

someplaceguy 3y ago
I meant "the halting problem" as in the informal description of the problem, e.g. as in how it is described in Wikipedia: "the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever". If you take that description at face value and consider a model of computation with finite state (like real-world computers have), then it is decidable. If you take the usual formal description of the halting problem, which like you said, is specifically defined over Turing machines (i.e. a theoretical model which assumes you can have a machine with literally infinite state, which is impossible to construct in our universe), then yes, you'd need hyper-computation to solve that.
- tsimionescu 3y ago
  I thought initially you are referring to things like deterministic finite automata (DFAs) or total languages (Idris) when you are talking about finite state. If instead you are simply referring to the observation that physical computers have a finite amount of memory and thus we can solve the halting problem in finite time by simply iterating over all possible configurations, that is a somewhat uninteresting observation - since if we are already talking about real physical constraints, that algorithm is entirely useless for even the simplest computers from the 50s and 60s. It's basically equivalent to saying "any program will halt, because the sun will destroy all computers on Earth when it goes supernova". More interestingly, it turns out that there are some finitist versions of the halting problem for finite-tape Turing machines, and they act as a similar kind of limit. That is, it turns out that the only way to verify whether an arbitrary finite-state Turing machine will halt on a specific input is to check all possible states (and this also requires a finite-state Turing machine with a larger tape than the one under analysis). This result can actually be used in a very similar way to the infinite-tape halting problem: it 100% guarantees that, if your system is equivalent to a Turing machine with tape length N and M possible symbols, it will take more than N^M computational steps to check whether an arbitrary program holds. This can be used to prove that it is effectively impossible to check if a program halts, much the same as the "true" halting problem is used to prove that it is actually impossible to check. For an example, an arbitrary program for a computer with as much memory as the infamous "640KB is enough for anyone" quote would require at least 640,000^255 (~10^1480) computational steps to check if it halts. So, we can just as easily say it is impossible to check and we wouldn't be far off. This is very different from something like a total language (e.g. Idris) or a DFA, where it is actually possible to relatively quickly verify whether a program halts.
  - someplaceguy 3y ago
    > thus we can solve the halting problem in finite time by simply iterating over all possible configurations, that is a somewhat uninteresting observation It is, but that's not the observation I was making. You only mentioned one way of solving the problem, but that's not the only way. > That is, it turns out that the only way to verify whether an arbitrary finite-state Turing machine will halt on a specific input is to check all possible states What do you mean by all possible states? If you mean literally all possible states, that's not true. I mean, yes, you could iterate over all possible states to solve that problem, but that's probably the least efficient way to solve it. There are already-known algorithms which always solve the Halting problem for machines with finite state, and they don't need to iterate over all possible states. They do, however, need to iterate over all state transitions that the machine actually goes through (multiple times, even). However, these algorithms that I'm mentioning (i.e. cycle detection algorithms) are also quite dumb. They don't exploit any knowledge about the state transitions in order to analyze whether the machines halt or not, they just simulate the machine step by step (this is due to the definition of the cycle detection problem itself, which does not allow inspecting the program). In principle, and even in practice, it's possible to make those algorithms significantly more efficient, at least for many of the machines (i.e. programs) that we care about. I suspect it is not possible to make such a (fully automatic) algorithm significantly more efficient for all possible programs (even the nonsensical ones), although I don't think such a proof exists (if it does, I would like to see it). The closest I've been pointed to is a paper possibly implying that such an algorithm would have to be EXPTIME-complete, although even the person that pointed me to that paper had some difficulty interpreting it -- and even if that were true, that says nothing about its real-world efficiency. > That is, it turns out that the only way to verify whether an arbitrary finite-state Turing machine will halt on a specific input is to check all possible states Can you point me to a source that proves this claim? Not only I'm doubting it, but even if you are right, I'd be really interested in reading such a proof. > For an example, an arbitrary program for a computer with as much memory as the infamous "640KB is enough for anyone" quote would require at least 640,000^255 (~10^1480) computational steps to check if it halts. Again, I'm wondering why you are claiming that the only possible algorithms which can check whether arbitrary finite-state programs halt have to iterate over all possible states (or even all the actual state transitions).