World's most popular travel blog for travel bloggers.

Question as regards a proof of the Time Hierarchy Theorem

, , No Comments
Problem Detail: 

I'm referring to the proof outlined here (and

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?

Asked By : John Smith
Answered By : Yuval Filmus

Your arguments is as follows:

  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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback