Talk:Time hierarchy theorem

From Wikipedia, the free encyclopedia

Time hierarchy theorem has had a peer review by Wikipedia editors which is now archived. It may contain ideas you can use to improve this article.

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)

I kind of agree with you that "it is a bit weak" to just say "it is safe to say", but I also believe this article should stick to the thing it is about. To prove that it is possible to simulate a Turing machine in ever-lower time bounds is another proof in itself and, quite frankly, doesn't belong here. Of course, one could remove the "it is safe to say" bit and just claim it's possible in f(m)logf(m) and give the external link; but this runs the risk of the link breaking in future. One could always write a new article with this proof, but the title of that article would be huge... Proof that a Turing machine can simulate the first n steps of another Turing machine in at most n log m time, where m is the length of the description of the second Turing machine and its input perhaps? :) – Timwi 15:51, 3 October 2005 (UTC)

How about Universal Turing Machine? - User:Ben Standeven as 70.249.214.16 22:39, 9 October 2005 (UTC)

[edit] 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. 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.

[edit] Where's the linear lower bound come from?

I often see this result stated with a linear (n) lower bound on t(n). I can only think it must be because no smaller functions are time-constructible (a Turing machine can't even read an input of size n in sublinear time, although it can read it in sublinear work tape space), so it's actually redundant, in the same way that requiring NP proof signatures to have polynomial size is redundant. It might still be useful to mention somewhere though, since it does effectively limit the power of the theorem. Deco 28 June 2005 16:59 (UTC)

I've never thought of this, but it sounds really interesting. Thanks for this, I'll add something to this effect to the article. – Timwi 15:51, 3 October 2005 (UTC)