Talk:Time hierarchy theorem

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)\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)

How about Universal Turing Machine? - User:Ben Standeven as 70.249.214.16 22:39, 9 October 2005 (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. 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.

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)

Contradiction Cases and Time vs Steps

The cases here:

• If N accepts [N] (which we know it does in at most f(n) operations), this means that K rejects ([N], [N]), so ([N], [N]) is not in H_f, and thus N does not accept [N] in f(n) steps. Contradiction!
• If N rejects [N] (which we know it does in at most f(n) operations), this means that K accepts ([N], [N]), so ([N], [N]) is in H_f, and thus N does accept [N] in f(n) steps. Contradiction!

are not written very clearly. The justification for each step is 'implicit' and hides a mistake in the proof. It would be clearer to write something closer to

 0) If N accepts [N]
 1) K rejects (N,N)                                           // by definition of N
 2) not (N  runs on [N] in <= f(n) steps and N accepts [N])  // by definition of K
 3) N  runs on [N] in > f(n) steps                          // by 0) and 2) 
 4) N is in Time(f(n))                                     // by runtime evaluation of N
 3 and 4 are a contradiction.

 0) If N rejects [N]
 1) K accepts (N,N)                                         // by definition of N
 2) (N  runs on [N] in <= f(n) steps) and (N accepts [N])  // by definition of K
 3) N accepts [N]                                         // simplification of 2)
 0 and 3 are a contradiction.

Unfortunately, writing it this way shows a clear mistake. In the accepting case, (N halts on N in > f(n) steps) and (Time(N)=f(n)) does not simplify to false. Since K_f cannot be altered to determine if it's input (M,x) runs in O(f(m)), it is necessary to show that N_f can be defined to run in <= f(n) steps for the contradiction to hold. Antares5245 (talk) 20:33, 20 February 2009 (UTC)

This error is predicated on the assumption that the notation TIME(f(n)) includes implied big-O notation (TIME(O(f(n))) which I've seen in some definitions but I think in this case it's meant to imply an exact number of steps.

If the number of steps is exact though, that raises new issues; we can see that K runs in time f(n), but how does N run in time f(n)? If it simulates K, there would be a slowdown. And it has the overhead of copying the input to produce the input for K, and inverting the result, which presumably can't be done in zero time. It seems a constant factor needs to be accounted for somehow, but I'm pretty fuzzy on this. Can someone lay out the details of this part more pedantically? Dcoetzee 21:00, 20 February 2009 (UTC)

That's phrased a lot better than what I said. Actually more than a constant factor is required if you have to copy the input. That's why the proof seems to imply big O notation, because the added 'constant factors' are ignored. It might actually be necessary for the proof for N to be an alterned 'copy' of K, not just a machine that simulates it.

Textbook-like proof

This article is a great example of why proofs are problematic on Wikipedia. First, it's not clear whether or not this proof is original research. Second, it appears to be a simplified proof, in an attempt to teach the subject matter, rather than present facts. --Taeshadow (talk) 16:52, 11 March 2009 (UTC)

DTime(f(n)) strictly contained in DSpace(f(n))?

Please give a citation. Where the strict part is proved? 89.177.144.33 (talk) 08:44, 8 January 2018 (UTC)