On the strongly generic undecidability of the Halting Problem

AbstractIt has been shown in [J.D. Hamkins, A. Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Formal Logic 47(4) (2006) 515–524] that the classical Halting Problem for Turing machines with one-way tape is decidable on a “large” set of Turing machines (a so-called generic set). However, here we prove that the Halting Problem remains undecidable when restricted to an arbitrary “very large” set of Turing machines (a so-called strongly generic set). Our proof is independent of a Turing machine model