Recursive Function Theory and Logic

By Ann Yasuhara

No Synopsis Available.

• Format: Hardcover
• Language: English
• ISBN: 0127689508
• ISBN13: 9780127689500
• Release Date: January 1971
• Publisher: Academic Pr
• Length: 338 Pages
• Weight: 1.66 lbs.

Customer Reviews

more information

Here's the contents of the book: (haven't read it yet)introduction 1part 1 recursive function theorych 1 turing machines 151.1 the definition of a turing machine1.2 some simple problems tm's can do1.3 some terminology and notation1.4 the universal turing machine1.5 the halting problem1.6 a few remarks about decision problems1.7 well-known decision problems1.8 additional exercisesch 2 semi-thue and thue systems2.1 instantaneous descriptions of a turing machine2.2 semi-thue systems2.3 thue systems2.4 the post correspondence problem2.5 some formal grammar ramifications of the thue systemch 3 enumerations and godel numbering3.1 enumerations and countable sets3.2 godel numberingsch 4 recursive functions4.1 preliminaries4.2 definition of primitive recursive functions4.3 some simple primitive recursive functions4.4 some useful primitive recursive functions4.5 total, regular, and partial functions, and unbounded minimization4.6 recursive and partial recursive functions4.7 remarks and exercises on 4.7 and 4.43ch 5 equivalence of recursive and turing-computable functions5.1 turing computability5.2 recursive implies turing computable5.3 turing computable implies recursive5.4 some results of the equivalence5.5 the smn theorem, the recursion theorem, and self-reproducing machinesch 6 inside recursive functions 1036.1 remarks6.2 ackermann's function6.3 an alternative formulation of the recursive functions6.4 kalmar-elementary functions and the grzegorzyk hierarchy6.5 the predictably computable functions, or the ritchie hierarchy6.6 complexity of partial recursive functionsch 7 recursively enumerable sets 1497.1 definitions and basic theorems7.2 the complete set K7.3 one-one (many-one) reducibiltiesch 8 recursive and recursively enumerable relations 1638.1 defintions8.2 the T predicate8.3 quantifying on recursive and r.e. relations8.4 turing reducibility, or oracles8.5 friedbergs theorempart 2 mathematical logicch 9 the propositional calculus as an example of a recursivelyaxiomatizable theory 1859.1 defn of a recursively axiomatizable theory9.2 a formulation of the propositioinal calculus9.3 some theorems in P_0 and the deduction theorem9.4 more about propositional languages; truth values9.5 tautologies and the consistency of P_09.6 truth value functions9.7 completeness and solvability of P_0ch 10 introduction to first order languages and relational systems 19910.1 first order languages10.2 relational systems10.3 a relational system for a language10.4 a formula is true in a relational system10.5 further discussion of a language and its relational system10.6 universally valid formulas10.7 definition of and introduction to first order theoriesch 11 first order theories with equality 22311.1 the axioms for V11.2 adding extra names of constants11.3 V=_ the completeness theorem11.4 some immediate consequences of the completeness theoremch 12 first order theories with equality 236ch 13 herbrands theorem 24213.1 prenex normal form13.2 conjunctive and disjunctive norma