Autosolvability of halting problem instances for instruction sequences
arXiv:0911.5018
Abstract
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.
18 pages; notational mistakes in tables 5 and 6 corrected; erroneous definition in last paragraph of page 11 corrected