Reflexive structures: an introduction to computability theory
Reflexive Structures: An Introduction to Computability Theory is concerned with the foundations of the theory of recursive functions. The approach taken presents the fundamental structures in a fairly general setting, but avoiding the introduction of abstract axiomatic domains. Natural numbers and numerical functions are considered exclusively, which results in a concrete theory conceptually organized around Church's thesis. The book develops the important structures in recursive function theory: closure properties, reflexivity, enumeration, and hyperenumeration. Of particular interest is the treatment of recursion, which is considered from two different points of view: via the minimal fixed point theory of continuous transformations, and via the well known stack algorithm. Reflexive Structures is intended as an introduction to the general theory of computability. It can be used as a text or reference in senior undergraduate and first year graduate level classes in computer science or mathematics.
What people are saying - Write a review
We haven't found any reviews in the usual places.
2 Numerical Functions
4 Closure Properties
11 other sections not shown
Other editions - View all
Reflexive Structures: An Introduction to Computability Theory
Luis E. Sanchis
No preview available - 2011
A-term algorithm apply assume barred quantification binary c-ary predicate characteristic function Church's thesis class closed class of functions class of predicates closed under basic closed under elementary closed under enumeration closed under existential closed under primitive closed under recursive closed under substitution computability theory Corollary course-of-values recursion defined denoted e-total elementary functions elementary operations encoding enumeration operations equations evaluation example existential quantification fe-ary finitary follows from Theorem FRS with internal function h functions closed Furthermore hence hyperarithmetic hyperenumerable if-computable if-decidable induction hypothesis inductive specification internal interpreter introduce k-ary notation Note partial definition partially decidable partially recursive predicate Q primitive recursive operations Proof Prove the following RC(c recursive function recursive specification recursively enumerable rules S)-index symbol tion total computable function total function total unary function type 2 barred unary computable function unbounded minimalization undefined universal bounded quantification universal quantification vector y e 0g