If M is non deterministic Turing machine and w is any string then $\Phi_{M,w}$ is satisfiable if and only if M accepts w according to Cook and Levin (1971).

By the definition of non deterministic Turing machine, M accepts w if and only if M has an accept computation on w.

But if all computations of M on w are accept then is $\Phi_{M,w}$ necessarily a tautology more than just satisfiable?

We know for sure that if M rejects w then all computations of M on w are reject and $\Phi_{M,w}$ is unsatisfiable.


The formula $\Phi_{M,w}$, which says "Turing machine $M$ accepts input $w$" is never a tautology.

If you look at how the formula is defined, the variables denote things like "At time $t$, the machine is in state $q$" and "At time $t$, the $i$th cell of the tape contains symbol $\sigma$" and the clauses say things like, "$M$ is only in one state at a time", "every tape cell contains only one character at a time" and "the tape cells don't change except where the head is." Thus, any assignment to the variables that violates these conditions (e.g., in two states at once, two characters in the same tape cell, characters on the tape changing without being written by the head), then $\Phi_{M,w}$ is falsified.

  • $\begingroup$ Even if all computations of M on w are accept still $\Phi_{M,w}$ is falsifiable? $\endgroup$ – user82913 Jan 18 '18 at 17:59
  • $\begingroup$ Never means never, yes. I explained why the formula is falsifiable and that explanation had nothing to do with $M$'s behaviour on input $w$. $\endgroup$ – David Richerby Jan 18 '18 at 18:04
  • $\begingroup$ I understood you. $\endgroup$ – user82913 Jan 18 '18 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy