The halting problem on finite and infinite computers

ABSTRACT

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.

REFERENCES

• 1: {Davis-Sigal-Weyuker1994} Martin D. Davis, Ron Sigal and Elaine J. Weyuker: Computability, Complexity, and Languages, Morgan Kaufmann 1994. ISBN 0-12-206382-1.
• 2: {Lewis-Papadimitriou1981} Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation, Prentice Hall 1981. ISBN 0-13-273417-6.
• 3: {Papadimitriou1995}. Christos H. Papadimitriou: Computational Complexity. Addison-Wesley 1995. ISBN 0-201-53082-1.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Computability theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines); Bounded-action devices (e.g., Turing machines, random access machines)

General Terms:
Algorithms, Theory