“The Halting Problem Is Decidable on a Set of Asymptotic Probability One”, 2005-04-18 (; similar):
The halting problem for Turing machines is decidable on a set of asymptotic probability one. Specifically, there is a set B of Turing machine programs such that (1) B has asymptotic probability one, so that as the number of states n increases, the proportion of all n-state programs that are in B goes to one; (2) B is polynomial time decidable; and (3) the halting problem H ∩ B is polynomial time decidable.
The proof is sensitive to the particular computational model.