Handbook of Computability TheoryE.R. Griffor The chapters of this volume all have their own level of presentation. The topics have been chosen based on the active research interest associated with them. Since the interest in some topics is older than that in others, some presentations contain fundamental definitions and basic results while others relate very little of the elementary theory behind them and aim directly toward an exposition of advanced results. Presentations of the latter sort are in some cases restricted to a short survey of recent results (due to the complexity of the methods and proofs themselves). Hence the variation in level of presentation from chapter to chapter only reflects the conceptual situation itself. One example of this is the collective efforts to develop an acceptable theory of computation on the real numbers. The last two decades has seen at least two new definitions of effective operations on the real numbers. |
Contents
Reducibilities and Degrees | 87 |
Generalized Computability Theory | 249 |
Mathematics and Computability Theory | 361 |
Logic and Computability Theory | 505 |
Computer Science and Computability Theory | 587 |
| 707 | |
| 715 | |
Other editions - View all
Common terms and phrases
1-generic algebra Algebra i Logika Ambos-Spies Amer Math arithmetic automorphism Banach space Boolean bounded c.e. sets characterization coding complete COMPUTABILITY THEORY computable field computable functions computable numbering computable ring construction continuous functionals COROLLARY countable models decidable defined definition denote Downey E-recursive effective elements embedding equivalent example exists first-order function f Gödel Harrington hence hierarchy higher type ideal induction infinite initial segment input integers isomorphic Jockusch k-coloring Kleene Lachlan lattice Lemma m-degrees Mathematics model theory natural numbers Noetherian ring North-Holland notation notion numbered set oracle ordinal partial orderings partial recursive function polynomial primitive recursive primitive recursive functions proof properties proved putable Recursion Theory recursive sets recursively enumerable degrees recursively enumerable sets relation Section semicomputable Shore Slaman Soare splitting algorithm Springer structure subset Symbolic Logic Theorem Thesis tion tree tt-degrees Turing degrees Turing machine Turing's undecidable
Popular passages
Page 8 - These two memoirs taken together furnish, to those who are capable of understanding the reasoning, a complete demonstration — That the whole of the developments and operations of analysis are now capable of being executed by machinery.
Page 31 - The woof and warp of all thought and research is symbols, and the life of thought and science is the life inherent in symbols; so that it is wrong to say that a good language is important to good thought, merely, for it is the essence of it.
Page 28 - objective" and "subjective" proved not to be barbarous enough, by half, long to retain their usefulness in philosophy, even if there had been no other objection to them. The first rule of good taste in writing is to use words whose meanings will not be misunderstood; and if a reader does not know the meaning of the words, it is infinitely better that he should know he does not know it.
Page 15 - It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, ie, one not depending on the formalism chosen.
Page 31 - Documentation ...the woof and warp of all thought and all research is symbols, and the life of thought and science is the life inherent in symbols...
Page 9 - If <p denotes an unknown function and ^1, . . . , ^k are known functions, and if the ^'s and the <p are substituted in one another in the most general fashions and certain pairs of the resulting expressions are equated, then, if the resulting set of functional equations has one and only one solution for <p, <p is a recursive function".
Page 14 - Of these, the first has the advantage of making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately — ie, without the necessity of proving preliminary theorems.
Page 15 - ... notion, ie, one not depending on the formalism chosen. In all other cases treated previously, such as demonstrability or definability, one has been able to define them only relative to a given language, and for each individual language it is clear that the one thus obtained is not the one looked for. For the concept of computability, however, although it is merely a special kind of demonstrability or definability, the situation is different. By a kind of miracle, it is not necessary to distinguish...