(I don't think that this is a good fit on cstheory, since I figure that this question already has a known answer. However, if you think that this would be a better fit there, please feel free to migrate it)
It can easily be shown that REGULAR (the class of regular languages) is contained in DTIME(O(n)), because for any regular language L we can decide membership in that language in O(n) time by converting a DFA that decides L into a TM that decides L in a single pass over the input. However, is it also true that DTIME(O(n)) is contained in REGULAR; that is, that any language that can be decided in O(n) time by a single-tape TM is necessarily regular?
I have no idea how to approach this problem, and every language I can think of in DTIME(O(n)) seems to be regular. Intuitively, this would make sense, since if you're only allowed to make finitely many passes over the input, you could only remember finitely many things about it, which it seems like you could simulate with a sufficiently large DFA. However, the fact that you can write to the input tape seems like it might complicate things.
And no, this isn't a homework problem. I'm actually teaching a course that covers computability and complexity theory and thought it would be interesting to present the answer to this question in lecture. :-)
Thanks!