<p>Minsky explains this problem very well (see the wikipedia article on the Halting Problem under 'common pitfalls': <a href="http://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls</a> ).</p>

<p>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.</p>

<p>However, with only a million bits of memory you have at least <span class="math-container">$2^{\left (10^6 \right )}$</span> 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. </p>

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

<p>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'. </p>

CC BY-SA 4.0
2019-02-13T17:22:13.217Z
Actually one million bits is $2^{10^{6}}$
SOFe
CC BY-SA 4.0
2012-01-26T13:01:05.390Z
2019-02-14T05:13:52.393Z
2019-02-14T05:13:52.393Z
Peter
<p>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?</p>

CC BY-SA 3.0
2012-01-26T09:16:52.110Z
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.
Andrej Bauer
CC BY-SA 3.0
2012-01-26T09:24:12.693Z
I appreciate the feedback.
Syzygy
CC BY-SA 3.0
2012-01-26T11:17:10.573Z
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.
Klaus Draeger
<computability>
Decidability of the halting problem on finite computers
Syzygy
# Decidability of the halting problem on finite computers

(Asked by: username_0 on 2012-01-26)

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?

**Tags:** computability
> **Comments:**
> **username_1**: 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.  
> **username_0**: I appreciate the feedback.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2012-01-26. Score: 6

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'.

> **Comments:**
> **username_4**: Actually one million bits is $2^{10^{6}}$  

---

