Elements of the Theory of ComputationA general, yet comprehensive, introduction to the classical and contemporary theory of computation. |
Other editions - View all
Common terms and phrases
1-place A V B a₁ a₂ accepts algorithm alphabet atomic formulas automata b₁ B₂ binary blank C₁ C₂ clause set computation configuration conjunctive normal form construction contains context-free grammar context-free languages decides defined definition derivation deterministic finite automaton disjunctive normal form encoding equivalent example Formally formula F function signs Gödel number grammar G Hamilton cycle head infinite input string integers k-tape Turing machine L₂ leftmost Lemma Let F Let G M₁ M₂ n₂ natural numbers nondeterministic Turing machine nonterminal NP-complete number of steps occurrence P₁ pair parse tree polynomial polynomial-time predicate calculus predicate sign primitive recursive functions problem proof of Theorem propositional calculus pushdown automaton q₁ quantifiers rule S₁ satisfiable scanned second tape Show simulation stack subformulas subset Suppose symbol t₁ tape square tiling tion transformation transitions truth-assignment truth-value Turing-acceptable Turing-computable Turing-decidable u₁ unsatisfiable unsolvable variables verifies w₁