Elements of the Theory of Computation

2-place A V B a₁ a₂ accepts algorithm alphabet atomic formulas automata b₁ B₂ binary C₁ C₂ clause set computation configuration conjunctive normal form construction contains context-free grammar context-free languages countable decides defined definition derivation deterministic finite automaton disjunctive normal form encoding equivalent example F₁ Formally formula F function signs functional form G₂ grammar G halts Hamilton cycle Herbrand expansion infinite input string integers k-tape Turing machine L₂ Lemma Let F Let G literals M₁ M₂ natural numbers negation nondeterministic Turing machine nonterminal NP-complete number of steps occurrence pair parse tree polynomial polynomial-time predicate calculus predicate sign primitive recursive functions problem proof of Theorem propositional calculus pushdown automaton q₁ quantifiers R₁ regular expression relation rule S₁ satisfiable Show simulation stack subformulas subset Suppose symbol t₁ tape square tiling tion transformation transitions truth-assignment truth-value Turing-acceptable Turing-decidable unsatisfiable unsolvable variables verifies w₁ write