Antti Ylikoski
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.
- {Davis-Sigal-Weyuker1994} Martin D. Davis, Ron Sigal and Elaine J. Weyuker: Computability, Complexity, and Languages, Morgan Kaufmann 1994. ISBN 0-12-206382-1.Google Scholar
- {Lewis-Papadimitriou1981} Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation, Prentice Hall 1981. ISBN 0-13-273417-6.Google Scholar
- {Papadimitriou1995}. Christos H. Papadimitriou: Computational Complexity. Addison-Wesley 1995. ISBN 0-201-53082-1.Google Scholar
Index Terms
- The halting problem on finite and infinite computers
Recommendations
Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
Eilenberg, Elgot and Shepherdson showed in 1969, [S. Eilenberg, C.C. Elgot, J.C. Shepherdson, Sets recognized by n-tape automata, Journal of Algebra 13 (1969) 447-464], that a relation on finite words over a finite, non-unary alphabet with p letters is ...
Universality and the halting problem for cellular automata in hyperbolic spaces: the side of the halting problem
UCNC'12: Proceedings of the 11th international conference on Unconventional Computation and Natural ComputationIn this paper, we remind results on universality for cellular automata in hyperbolic spaces, mainly results about weak universality, and we deal with the halting problem in the same settings. This latter problem is very close to that of strong ...
Comments