Customer Reviews

Recursive Function Theory and Logic (Computer Science and Applied Mathematics)

5 star:		(1)
4 star:		(0)
3 star:		(0)
2 star:		(0)
1 star:		(1)

 

 

I've read a number of books on computability theory, and this isnt one of the good ones. It makes fluctuating demands on the level of mathematical sophistication required by the reader. Often trivial ideas are belabored, while more subtle and important concepts are glossed over. Even worse, many important theorems are left as poorly expressed exercises, or the reader is invited to hunt down a four-decade-old research paper if he actually wants to learn anything. Exposition is confused, terminology and notation bad, and the proofs arent so hot either. Pretends to be mathematically rigorous but is not, and fails to foster intuitive understanding either. Too rapid and disorganized for the beginner, especially as topics too advanced for the scope of the book are carelessly thrown in. But its also too clumsy and inarticulate to benefit the advanced reader.

I suppose you can probably find in it a handful of special-topics you havent seen in other books. And there are certainly (much) worse computation theory books out there. Instead I would recomend (1)Lewis & Papadimitriou's _Elements of the Theory of Computation_ 1st edition (but be warned many people seem to hate this book, though i'm sure they wouldnt like yasuharas either) and (2) Hartley Rogers' _Theory of Recursive Functions and Effective Computability_ (great great great book)

Here's the contents of the book: (haven't read it yet)
introduction 1
part 1 recursive function theory
ch 1 turing machines 15
1.1 the definition of a turing machine
1.2 some simple problems tm's can do
1.3 some terminology and notation
1.4 the universal turing machine
1.5 the halting problem
1.6 a few remarks about decision problems
1.7 well-known decision problems
1.8 additional exercises
ch 2 semi-thue and thue systems
2.1 instantaneous descriptions of a turing machine
2.2 semi-thue systems
2.3 thue systems
2.4 the post correspondence problem
2.5 some formal grammar ramifications of the thue system
ch 3 enumerations and godel numbering
3.1 enumerations and countable sets
3.2 godel numberings
ch 4 recursive functions
4.1 preliminaries
4.2 definition of primitive recursive functions
4.3 some simple primitive recursive functions
4.4 some useful primitive recursive functions
4.5 total, regular, and partial functions, and unbounded minimization
4.6 recursive and partial recursive functions
4.7 remarks and exercises on 4.7 and 4.43
ch 5 equivalence of recursive and turing-computable functions
5.1 turing computability
5.2 recursive implies turing computable
5.3 turing computable implies recursive
5.4 some results of the equivalence
5.5 the smn theorem, the recursion theorem, and self-reproducing machines
ch 6 inside recursive functions 103
6.1 remarks
6.2 ackermann's function
6.3 an alternative formulation of the recursive functions
6.4 kalmar-elementary functions and the grzegorzyk hierarchy
6.5 the predictably computable functions, or the ritchie hierarchy
6.6 complexity of partial recursive functions
ch 7 recursively enumerable sets 149
7.1 definitions and basic theorems
7.2 the complete set K
7.3 one-one (many-one) reducibilties
ch 8 recursive and recursively enumerable relations 163
8.1 defintions
8.2 the T predicate
8.3 quantifying on recursive and r.e. relations
8.4 turing reducibility, or oracles
8.5 friedbergs theorem

part 2 mathematical logic
ch 9 the propositional calculus as an example of a recursively
axiomatizable theory 185
9.1 defn of a recursively axiomatizable theory
9.2 a formulation of the propositioinal calculus
9.3 some theorems in P_0 and the deduction theorem
9.4 more about propositional languages; truth values
9.5 tautologies and the consistency of P_0
9.6 truth value functions
9.7 completeness and solvability of P_0
ch 10 introduction to first order languages and relational systems 199
10.1 first order languages
10.2 relational systems
10.3 a relational system for a language
10.4 a formula is true in a relational system
10.5 further discussion of a language and its relational system
10.6 universally valid formulas
10.7 definition of and introduction to first order theories
ch 11 first order theories with equality 223
11.1 the axioms for V
11.2 adding extra names of constants
11.3 V=_ the completeness theorem
11.4 some immediate consequences of the completeness theorem
ch 12 first order theories with equality 236
ch 13 herbrands theorem 242
13.1 prenex normal form
13.2 conjunctive and disjunctive normal forms
13.3 skolem functions
13.4 trees and konigs lemma
13.5 herbrands theorem
13.6 mechanical theorem proving
ch 14 decidable and undecidable theoreis 267
14.1 number theory and peanos axioms
14.2 the incompleteness theorem
14.3 the undecidability of P and N
14.4 two subtheories of N: R and Q

14.5 presburgers theory of addition of natural numbers; elimination of quantifiers
14.6 finite automata and the weak monadic second order theory of successor
14.7 concluding remarks

references 321
index 327