I've seen two competing and contrary arguments for this problem. One states that real computers are linear-bounded automata, and therefore the halting problem is decidable. The other states that real programs on finite machines are modelled as taking an infinite vector of inputs (say, network or keyboard inputs), and that the input vector is modelled as part of the state, therefore the state is infinite, and therefore the problem is undecidable. Would anybody care to weigh in on this one?

  • 5
    $\begingroup$ This is not a question about computability because everything is crystal clear once we decide how to model real-world computers (you yourself listed the choices, and the answers are known for all of them). At best, you are asking us how to model real-world computers. And the answer to that depends on what aspect you want to model and think about. So I consider this not to be a good question, at least not the way it is posed. $\endgroup$ – Andrej Bauer Jan 26 '12 at 9:16
  • $\begingroup$ I appreciate the feedback. $\endgroup$ – Syzygy Jan 26 '12 at 9:24
  • 2
    $\begingroup$ What you are actually seeing here is the dichotomy between transformational and reactive systems - the former being those that take some (finite) input and try to compute some result based on it, while the latter have an ongoing interaction with the environment. For reactive systems, you are usually concerned with other (temporal logic) properties than halting. $\endgroup$ – Klaus Draeger Jan 26 '12 at 11:17

Minsky explains this problem very well (see the wikipedia article on the Halting Problem under 'common pitfalls': http://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls ).

Strictly speaking, an actual computer has a finite number of possible states, which means that any non-halting behavior must be periodic, so you just solve the halting problem by running the computer until you observe the same state twice and then you know it's a non-halting machine.

However, with only a million bits of memory you have at least $2^{\left (10^6 \right )}$ possible states, so that's the possible length of sequence of states until it returns to an already visited state. That means that if you compute one state transition in the smallest theoretically measurable timelapse, you'd need 300000 times the age of the universe to complete such a cycle.

At that point it's more useful to model computers as infinite state machines (like Turing Machines).

Physicists have a similar problem where modeling a glass of water as a large but finite number of water molecules is much more difficult than modeling it as a an infinite number of molecules. It's a kind of 'approximation from above'.

| cite | improve this answer | |
  • 1
    $\begingroup$ Actually one million bits is $2^{10^{6}}$ $\endgroup$ – SOFe Feb 13 '19 at 17:22

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