On the Generic Undecidability of the Halting Problem for Normalized Turing Machines

摘要

Hamkins and Miasnikov presented in (Notre Dame J. Formal Logic 47(4), 515-524, 2006) a generic algorithm deciding the classical Halting Problem for Turing machines with one-way tape on a set of asymptotic probability one (on a so-called generic set). Rybalov (Theor. Comput. Sci. 377, 268-270, 2007) showed that there is no generic algorithm deciding this problem on strongly generic sets of inputs (some subclass of generic sets). In this paper we prove that there is no generic algorithm deciding the Halting Problem for normalized Turing machines on generic sets of inputs. Normalized Turing machines have programs with the following natural restriction: internal states with large indices are not allowed at the beginning of the program. This condition does not reduce the class of computable functions because for every Turing machine there exists a normalized Turing machine which computes the same function. Our proof holds for machines with one-way and two-way tape. It also implies that the Hamkins-Miasnikov algorithm is not generic for normalized Turing machines.