1
$\begingroup$

Coming from a digital functional hardware verification background, I don’t really understand the Halting Problem. I can represent the program as a state machine and show whether all inputs in all states generate a valid output or lead to an infinite loop.

The only requirement is that the inputs and states are finite. E.g. an infinite counter would lead to an infinite number of states.

Since infinite counters or infinite inputs are impossible in reality, does the Halting Problem really have a practical relevance?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ The undecidability of the halting problem doesn't depend on having "infinite counters" or "infinite inputs". In the standard models of computation, inputs are finite and, at any stage of the computation, only a finite amount of data has been stored. $\endgroup$
    – David Richerby
    Jun 3 '16 at 11:11
0
$\begingroup$

Indeed, if states and inputs are finite (and the tape is finite, which is quite reasonable), then you can easily reduce the Turing machine to a Finite State Machine. However, this is completely impractical, since it doesn't yield any reasonably effective algorithms. I.e. your solution for the halting problem will be to explode the states of the TM with all possible input combinations of size N, and then find a path that reaches a stop state, right? Probably don't want to implement such a check in your compiler.

Improve this answer
$\endgroup$
-1
$\begingroup$

No, your reasoning is wrong. Building a state machine and checking for cycles works only if the memory of the Turing machine is finite and bounded in length. However, the working state of the Turing machine (the tape) is unbounded in length, so there is no upper limit on the set of possible states. In other words, while the size of the state is finite at any specific time, the total number of possible states that might ultimately be reachable is infinite.

Yes, the Halting problem is important and has practical relevance: see Why, really, is the Halting Problem so important?

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.