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 '16 at 9:01

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, privacy policy and cookie policy

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