Autosolvability of halting problem instances for instruction sequences
Jan Aldert Bergstra, Cornelis A. Middelburg · arXiv (Cornell University) · 2009
We position Turing's result regarding the undecidability of the halting problem as a result about programs rather than machines. The mere requirement that a program of a certain kind must solve the halting problem for all programs of that kind leads to a contradiction in the case of a recent unsolvability result regarding the halting problem for programs. In this paper, we investigate this autosolvability requirement in a setting in which programs take the form of instruction sequences.