I'm familiar with Hamkins' result that the generic-case complexity of the Halting Problem is polynomial in time.
What's the analogous result for the various Linear Bounded Automata?
Edit: For those unfamiliar with generic-case complexity, here is the definition from Wikipedia. The proof of the generically-polynomial complexity of the Halting Problem can be found in this paper.
The "one sentence version" of the paper is that there exists some algorithm such that the proportion of $n$-state Turing Machines for which the Halting Problem is decidable (using that algorithm) becomes 100% as $n\to\infty$.