Skip to main content
added 214 characters in body
Source Link
user326210
  • 778
  • 3
  • 12

It's the prover's fault: there is no way to decide whether an arbitrary TM will halt or run forever, and so there is no certificate to prove that an arbitrary TM will run forever.

If $L$ is not recursively enumerable, then no machine can simultaneously:

  1. Halt on every input $\langle w, c\rangle$ (a word and a proof that the word is in the language).
  2. Always answer correctly whether $w\in L$.

If a convincing certificate $c(w)$ really did exist for every word $w$ in the language, and a verifier with these two properties existed, then the language would be recursively enumerable and here is the Turing machine to prove it:

M(x): on input x, iterate over every possible word $c$ in increasing order of length and run the verifier on $\langle x,c\rangle$. Halt and respond YES if the verifier ever accepts, otherwise keep iterating forever.

It's not the verifier's fault. If a language is not recursively enumerable, then (equivalently) it is algorithmically impossible to confirm membership in the language. In particular, no certificate can help.

It's the prover's fault: there is no way to decide whether an arbitrary TM will halt or run forever, and so there is no certificate to prove that an arbitrary TM will run forever.

If $L$ is not recursively enumerable, then no machine can simultaneously:

  1. Halt on every input $\langle w, c\rangle$ (a word and a proof that the word is in the language).
  2. Always answer correctly whether $w\in L$.

If a convincing certificate $c(w)$ really did exist for every word $w$ in the language, and a verifier with these two properties existed, then the language would be recursively enumerable and here is the Turing machine to prove it:

M(x): on input x, iterate over every possible word $c$ in increasing order of length and run the verifier on $\langle x,c\rangle$. Halt and respond YES if the verifier ever accepts, otherwise keep iterating forever.

It's the prover's fault: there is no way to decide whether an arbitrary TM will halt or run forever, and so there is no certificate to prove that an arbitrary TM will run forever.

If $L$ is not recursively enumerable, then no machine can simultaneously:

  1. Halt on every input $\langle w, c\rangle$ (a word and a proof that the word is in the language).
  2. Always answer correctly whether $w\in L$.

If a convincing certificate $c(w)$ really did exist for every word $w$ in the language, and a verifier with these two properties existed, then the language would be recursively enumerable and here is the Turing machine to prove it:

M(x): on input x, iterate over every possible word $c$ in increasing order of length and run the verifier on $\langle x,c\rangle$. Halt and respond YES if the verifier ever accepts, otherwise keep iterating forever.

It's not the verifier's fault. If a language is not recursively enumerable, then (equivalently) it is algorithmically impossible to confirm membership in the language. In particular, no certificate can help.

added 284 characters in body
Source Link
user326210
  • 778
  • 3
  • 12

It's the prover's fault: there is no way to decide whether an arbitrary TM will halt or run forever, and so there is no certificate that can correctly establishto prove that an arbitrary TM will haltrun forever.

If $L$ is not recursively enumerable, then no machine can simultaneously:

  1. Halt on every input $\langle w, c\rangle$ (a word and a proof that the word is in the language).
  2. Always answer correctly whether $w\in L$.

If a convincing certificate $c(w)$ really did exist for every word $w$ in the language, and a verifier with these two properties existed, then the language would be recursively enumerable and here is the Turing machine to prove it:

M(x): on input x, iterate over every possible word $c$ in increasing order of length and run the verifier on $\langle x,c\rangle$. Halt and respond YES if the verifier ever accepts, otherwise keep iterating forever.

It's the prover's fault: there is no way to decide whether an arbitrary TM will halt or run forever, and so there is no certificate that can correctly establish that an arbitrary TM will halt.

If $L$ is not recursively enumerable, then no machine can simultaneously:

  1. Halt on every input $\langle w, c\rangle$ (a word and a proof that the word is in the language).
  2. Always answer correctly whether $w\in L$.

If a convincing certificate $c(w)$ really did exist for every word $w$ in the language, and a verifier with these two properties existed, then the language would be recursively enumerable and here is the Turing machine to prove it:

M(x): on input x, iterate over every possible word $c$ in increasing order of length and run the verifier on $\langle x,c\rangle$. Halt and respond YES if the verifier ever accepts, otherwise keep iterating forever.

It's the prover's fault: there is no way to decide whether an arbitrary TM will halt or run forever, and so there is no certificate to prove that an arbitrary TM will run forever.

If $L$ is not recursively enumerable, then no machine can simultaneously:

  1. Halt on every input $\langle w, c\rangle$ (a word and a proof that the word is in the language).
  2. Always answer correctly whether $w\in L$.

If a convincing certificate $c(w)$ really did exist for every word $w$ in the language, and a verifier with these two properties existed, then the language would be recursively enumerable and here is the Turing machine to prove it:

M(x): on input x, iterate over every possible word $c$ in increasing order of length and run the verifier on $\langle x,c\rangle$. Halt and respond YES if the verifier ever accepts, otherwise keep iterating forever.

Source Link
user326210
  • 778
  • 3
  • 12

It's the prover's fault: there is no way to decide whether an arbitrary TM will halt or run forever, and so there is no certificate that can correctly establish that an arbitrary TM will halt.

If $L$ is not recursively enumerable, then no machine can simultaneously:

  1. Halt on every input $\langle w, c\rangle$ (a word and a proof that the word is in the language).
  2. Always answer correctly whether $w\in L$.

If a convincing certificate $c(w)$ really did exist for every word $w$ in the language, and a verifier with these two properties existed, then the language would be recursively enumerable and here is the Turing machine to prove it:

M(x): on input x, iterate over every possible word $c$ in increasing order of length and run the verifier on $\langle x,c\rangle$. Halt and respond YES if the verifier ever accepts, otherwise keep iterating forever.