Talk:Time hierarchy theorem

This  level-5 vital article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics C‑class Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles C This article has been given a rating which conflicts with the project-independent quality rating in the banner shell. Please resolve this conflict if possible. Mid This article has been rated as Mid-priority on the project's priority scale.

Time hierarchy theorem received 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 ${\displaystyle f(m)\log f(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)[reply]

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