Production rules correspond to Turing machines:

[U]nrestricted grammar[s]...can generate arbitrary recursively enumerable languages.

There is a Turing machine that can recognize tautologies in propositional logic (truth table/brute force).

Therefore there should be some production rules that precisely yield tautologies. What are those production rules?

  • 1
    $\begingroup$ The proof of equivalence between unrestricted grammars and r.e. languages, together with a Turing machine listing all tautologies, allows you in principle to construct such a grammar. $\endgroup$ – Yuval Filmus Jul 2 '18 at 20:06

Your Answer

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

Browse other questions tagged or ask your own question.