The halting problem on finite and infinite computers
Antti Ylikoski · ACM SIGACT News · 2005
This paper discusses some points originally raised by Robert L. Massey of Colorado, USA, and some consequences of that discussion. Firstly, earthly (ie. realistic) computers are finite because the number of atoms on Earth is finite. Secondly, and the main result of the paper is that, the famous Halting Problem is unsolvable only for infinite machines. In the end of the paper there are some thoughts about the consequences of these results, such as a suggestion to improve the classical Linear Bounded Automaton model.