The undecidability of the halting problem implies that no Turing machine can determine whether an arbitrary Turing machine passed to it will halt or not on a given input. However, we can devise algorithms that are right some of the time. In the simplest case, an algorithm that always returns "halt" will be correct for any Turing machine that halts. This is, however, not very useful. Can we do better?
What I am curious about is whether there are any results that pin down how good a partial solution to the halting problem can be before we run into trouble. Is there a Turing machine that solves the halting problem for almost all inputs? If not, is there a weaker condition we can ask for that can in fact be met?
More generally, let a "weak halting problem" be a problem obtained by replacing the universal quantification in the halting problem (the requirement that a Turing machine determine whether its input halts for all possible inputs) with some weaker notion of quantification. Which such weak halting problems are solvable?