World's most popular travel blog for travel bloggers.

# Question as regards a proof of the Time Hierarchy Theorem

, ,
Problem Detail:

I'm referring to the proof outlined here (and wikipedia.org): https://proofwiki.org/wiki/Deterministic_Time_Hierarchy_Theorem

In my understanding, if I relaxed the conditions such that $K$ decides the input in time $O(f(m)^3)$, there should not be a contradiction in the final step because an appropriate TM $K$ should really exist.

Under this condition, $N$'s running time should be $O(f(2n+1)^3)$.

Finally, I arrive at the conclusion:

1. If $N$ rejects $[N]$ (which we know it does in at most $f(2n+1)^3$ operations):
2. By the definition of $N$, $K$ accepts $([N],[N])$.
3. Therefore, by the definition of $K$, $([N],[N])\in H_f$.
4. Therefore, by the definition of $H_f$, $N$ does accept $[N]$ in $f(n)$ steps.

To me it seems that 1. and 4. would still contradict. What did I do wrong?

###### Answered By : Yuval Filmus

1. If $N$ rejects $[N]$ then $([N],[N]) \in H_f$.
2. Since $([N],[N]) \in H_f$, $N$ accepts $[N]$ in $f(m_n)$ steps.

This is indeed a contradiction, so we conclude that $N$ accepts $[N]$. Then we argue again:

1. Since $N$ accepts $[N]$ then $([N],[N]) \notin H_f$.
2. Since $([N],[N]) \notin H_f$, it is not true that $N$ accepts $[N]$ in $f(m_n)$ steps.

Since the running time of $N$ is $f(2m_n+1)^3$ in your case, there is no contradiction. After $f(m_n)$ steps the machine $N$ might still be running.