Computability |
Contents
Prerequisites and Notation | 1 |
Churchs Thesis | 79 |
Type 1 Recursion Theory | 137 |
Copyright | |
4 other sections not shown
Other editions - View all
Common terms and phrases
1-complete A-list algebraic cpo arithmetical Assume bijective Chapter complete computable function computable iff constructive continuous function Corollary correspondence cpo's D₁ D₂ Definition div otherwise dom(f dom(g dom(v domain elements encodings equivalent Example exercise exists f is computable final topology finite flowchart F following properties formally function f HALT halting problem hence induction infinite injective input isomorphic isotone Lemma Let f metric space natural numbers notation numbering of p(1 obtain oracle computable partial order precomplete primitive recursive functions productive proof of Theorem Prove r.e. set R₁ range(v real numbers recursion theory recursive set recursively enumerable sets register machine satisfies Show smn-theorem stack computable stack machine standard numbering standard representation subset Suppose t-admissible T-space tape machine total numbering translation lemma Turing Type 2 theory utm-theorem v₁ v₂