0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Even if all computations of M on w are accept still $\Phi_{M,w}$ is falsifiable? $\endgroup$
    – user82913
    Commented Jan 18, 2018 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
    Commented Jan 18, 2018 at 18:04
  • $\begingroup$ I understood you. $\endgroup$
    – user82913
    Commented Jan 18, 2018 at 18:18

Your Answer

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