Theory of Recursive Functions and Effective Computability

analogue arithmetical hierarchy Assume basic called Chapter characteristic function Church's Thesis co-finite computation Consider convergent Corollary defined degrees domain dual ideal elementary arithmetic equivalent example Exercise exists a recursive expression finite sets finite-path tree following theorem function variables give given Godel number halting problem Hence hierarchy theorem Hint hypersimple immediate infinite initial segment input integers isomorphic Kleene lattice logic mapping nonrecursive notation number variables obtained one-one ordering output partial function partial recursive function primitive recursive procedure productive proof of Theorem provable Prove quantifiers question recursion theorem recursive function theory recursive operator recursive relation recursive sets recursively enumerable sets recursively invariant reducibility relativized result second-order arithmetic sentences of elementary set theory sets of integers Show single-valued stage 2n subset symbols T-degree Take Tarski-Kuratowski algorithm Theorem VIII Theorem XI tion topology total function truth-table reducibility tt-condition Turing machine uniformly unsolvability wffs yields