enter image description here

I've seen the proof on a pdf online, and I'm having trouble seeing the contradiction.
If $(\langle T\rangle,z)=w \in D$, so when we emulate $T(w)$ with $U$ (universal machine), it accepts within the time bound, so $M_D(w)=1$ and also $T(w)=1$.
Aren't you supposed to define $D$ as above, but accept only $x=(\langle M\rangle,z)$ where $M$ rejects $x$ within the time bound?

  • 6
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$
    – adrianN
    Jun 7, 2016 at 9:01

1 Answer 1


There is no contradiction, and the proof does not hold water. You are right: 'accepts' should be changed to 'rejects', and $D$ should be defined as

$$D=\{\langle M, x\rangle \quad | \quad M \underline{\underline{\text{ rejects }}}\langle M, x \rangle \text{ within }n\log(n) \text{ steps} \} $$

with $n=|\langle M, x\rangle|$, the length of the input. This way, the proof goes according to plan:

Proof. Suppose a $an+b$-time machine $T$ solves $D$. Take a sufficiently long $x$. Does $T$ accept input $\langle T, x\rangle$?

Suppose yes. Then $T$ accepts its input $\langle T,x\rangle$ within $an+b$, so $T$ accepts within $n\log(n)$. That's a contradiction, because by definition of $D$, $\langle T,x\rangle \in D \implies T \text{ rejects } x$.

Suppose no. Then $T$ rejects its input $\langle T, x\rangle$ within $n\log(n)$ steps, so $\langle T, x\rangle$ should be an element of $D$, so $T$ should have accepted. Contradiction $\square$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.