Let $A=\{$ M is a TM, $s\in \mathbb{N}$ and $\exists x\in\Sigma^*$ s.t M rejects $x$ in at most $s$ steps $\}$.

I want to define its complement, so how do I negate "$\exists x\in\Sigma^*$ s.t M rejects $x$ in at most $s$ steps"?

Is it:

$\forall x \in \Sigma^*$ M accepts $x$ in at most $s$ steps?

Thanks a lot!

  • $\begingroup$ No. It's possible that $M$ neither accepts nor rejects $x$. The complement is "$M$ does not reject $x$ within $s$ steps." $\endgroup$
    – rici
    Nov 16, 2022 at 15:37
  • $\begingroup$ Oh right! Thank you! Why did you write "within $s$ steps" instead of "at most"? $\endgroup$
    – Geo
    Nov 16, 2022 at 20:23
  • $\begingroup$ It sounded better to my Canadian ear. $\endgroup$
    – rici
    Nov 16, 2022 at 20:46
  • $\begingroup$ @rici Got it! ;) Thanks! :) $\endgroup$
    – Geo
    Nov 17, 2022 at 10:18
  • $\begingroup$ @rici And should I replaced $\exists$ with $\forall$ ? $\endgroup$
    – Geo
    Nov 17, 2022 at 10:19


Your Answer

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