Intends to lay a common basis for the different branches of recursion theory. Leads from the very basic theory to modern concepts of computability. Consists of three consecutive parts: 1. Basic Concepts of Computability. 2. Traditional Recursion Theory. 3. Unified Type 2 theory of constructivity and computability on Baire's space including a general the- ory of representations.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Prerequisites and Notation
Type 1 Recursion Theory
3 other sections not shown
Other editions - View all
1-complete A-list algebraic cpo alphabet arithmetical Assume bijective Chapter characterization complete complexity measure computable function computable iff Consider constructive continuous function Corollary correspondence cpo's cylinder Define a numbering Definition div otherwise dom(f dom(v domain encodings equivalent Example exercise exists f is computable final topology finite flowchart F following properties formally function f halting problem hence induction infinite injective input isomorphic isotone Lemma Let f machine flowchart metric space natural numbers notation number functions obtain oracle computable partial order pre-order primitive recursive functions productive proof of Theorem Prove r.e. set range(v real numbers recursion theory recursive set recursively enumerable sets register machine Scott topology sequence Show smn-theorem stack computable stack machine standard numbering standard representation subset Suppose surjective t-admissible tape machine total function total numbering total recursive function translation lemma Turing Type 2 theory universal function upper bound WHILE-program