2
$\begingroup$

It has been my understanding that, technically, our computers are Finite State Machines. And, since FSMs halt when they run out of input, the halting problem is technically solvable. At some point, we must reach an identical state without consuming input if there is an infinite loop.

I also understand that doing this in practice would take far, far, far too long to be useful. Thus, I have read over and over that, yes, technically the halting problem is solvable for real computers, but it doesn't matter, because we can't do it in practice.

However, in a real computer, while we have a finite (vast) set of states, isn't it the case that we don't have finite input? Input can easily be generated from non-cyclical random events, such as random radioactive decay, or the motion of water in a stream. Doesn't this mean that, in fact, our computers are not truly Finite State Machines, and that the Halting Problem is not merely practically unsolvable, but genuinely unsolvable?

$\endgroup$
1
$\begingroup$

The halting problem can be stated as follows:

Given a program P and an input x, does P halt when run on x?

Here both P and x are finite. In some cases (for example, in program verification) we might also be interested in infinite input which is eventually periodic, or at the very least, has an effective finite description (i.e., it is given by some algorithm). Assuming that this algorithm is also executed on a real machine (otherwise it is "cheating"), the entire setup can be folded to a program running on a real machine, and so the property of having a finite number of states is recovered.

$\endgroup$
  • $\begingroup$ So what you're basically saying is that, yes, a program on a real computer can use infinite input, but that the halting problem isn't really a question about this scenario? $\endgroup$ – Ben I. Apr 20 '17 at 15:47
  • $\begingroup$ Right. Moreover, you can formulate variants of the halting problem which do have infinite input in some sense, but this won't make any difference. $\endgroup$ – Yuval Filmus Apr 20 '17 at 15:54
  • $\begingroup$ Why wouldn't they make any difference? Why would a variant of the halting problem with infinite input on a finite state machine be solvable? $\endgroup$ – Ben I. Apr 20 '17 at 16:50
  • $\begingroup$ It depends on the variant... if the infinite input is also generated by a finite state machine, then you can combine both FSMs together to get another FSM. $\endgroup$ – Yuval Filmus Apr 20 '17 at 16:51
  • $\begingroup$ But the example in my question is clearly not generated by a FSM. It's generated by radioactive decay a flowing stream. $\endgroup$ – Ben I. Apr 20 '17 at 16:53
-3
$\begingroup$

A Turing Machine is, strictly speaking, ALSO a Finite-State Machine; what gives it universal power is in how this FSM is allowed to interact in a largely unrestricted (but still finite) manner with one or more read/write tapes. Note that since the machine cannot visit more than N tape cells in N steps, these tapes do not need to be actually infinite; they merely need to be enlargeable, with no inherent bound on the eventual amount of enlargement. It is clearly possible to operate a physically real machine in this manner [though at the moment humans would be required to supply and manage the ever-growing tapes], therefore the theoretical analysis also applies to the physical machine.

$\endgroup$
  • $\begingroup$ A TM is not a FSM, this is incorrect. $\endgroup$ – Ben I. Apr 20 '17 at 20:47
  • $\begingroup$ Your first sentence is just wrong. While one component of a Turing machine is a finite state machine, the machine as a whole has an infinite number of possible states (which are referred to as "configurations"). In hindsight, it would have been better to call the states something like "control states" and the configurations "states", but that horse bolted long ago. $\endgroup$ – David Richerby Apr 20 '17 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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