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 axioms 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 elements 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 mapping 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 sequence Show smn-theorem stack computable stack machine standard numbering standard representation subset Suppose surjective t-admissible tape machine tion total function total numbering total recursive function translation lemma Turing Type 2 theory unary upper bound