The halting problem for Turing machines is perhaps the canonical undecidable set. Nevertheless, we prove that there is an algorithm deciding almost all instances of it. The halting problem is therefore among the growing collection of those exhibiting the “black hole” phenomenon of complexity theory, by which the difficulty of an unfeasible or undecidable problem is confined to a very small region, a black hole, outside of which the problem is easy.
[Joel David Hamkins and Alexei Miasnikov, "The halting problem is decidable on a set of asymptotic probability one", 2005]
Can anyone provide references to other “black holes” in complexity theory, or another place where this or related concepts are discussed?