Talk:Time hierarchy theorem
|
|
Template:Oldpeerreview Proof looks basically OK. It needs a justification of how a Turing machine can simulate M in O(f(n)³); "it is safe to say" is a bit weak. The fact that f is time-constructible need to be used explicitly in the proof. Also, we need an article on time-constructible function explaining why the concept is important and the exciting things you can do with functions that are not time-constructible. Gdr 23:41, 2004 Jul 4 (UTC)
Stronger bound, link to proof
The time heirarchy theorem has actually been proved for a much stricter bound. Specifically, TIME(o( f(n)/log(f(n)) )) is a strict subset of TIME(O(f(n)) -- sorry for the lack of pretty LaTeX. Lecture notes with proof here (http://www.cs.berkeley.edu/~luca/cs172/noteh.pdf). I'm sorry I don't have time to update the article myself, but I thought I'd at least drop a comment with the information and a link.