# Decidability of the halting problem on finite computers [closed]

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?

• 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 Jan 26 '12 at 9:16
• I appreciate the feedback. – Syzygy Jan 26 '12 at 9:24
• 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 Jan 26 '12 at 11:17

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.
• Actually one million bits is $2^{10^{6}}$ – SOFe Feb 13 at 17:22