Search results for 'Recursion theory' (try it on Scholar)

1000+ found
Order:
  1.  1
    Piergiorgio Odifreddi (1989). Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers. Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
    Volume II of Classical Recursion Theory describes the universe from a local (bottom-up or synthetical) point of view, and covers the whole spectrum, from the recursive to the arithmetical sets. The first half of the book provides a detailed picture of the computable sets from the perspective of Theoretical Computer Science. Besides giving a detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity classes, (...)
    Direct download  
     
    Export citation  
     
    My bibliography   14 citations  
  2.  2
    Jordan Zashev (2005). Diagonal Fixed Points in Algebraic Recursion Theory. Archive for Mathematical Logic 44 (8):973-994.
    The relation between least and diagonal fixed points is a well known and completely studied question for a large class of partially ordered models of the lambda calculus and combinatory logic. Here we consider this question in the context of algebraic recursion theory, whose close connection with combinatory logic recently become apparent. We find a comparatively simple and rather weak general condition which suffices to prove the equality of least fixed points with canonical (corresponding to those produced by (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  3.  25
    Raymond M. Smullyan (1993). Recursion Theory for Metamathematics. Oxford University Press.
    This work is a sequel to the author's Godel's Incompleteness Theorems, though it can be read independently by anyone familiar with Godel's incompleteness theorem for Peano arithmetic. The book deals mainly with those aspects of recursion theory that have applications to the metamathematics of incompleteness, undecidability, and related topics. It is both an introduction to the theory and a presentation of new results in the field.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography  
  4.  19
    S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.) (1996). Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press.
    The fundamental ideas concerning computation and recursion naturally find their place at the interface between logic and theoretical computer science. The contributions in this book, by leaders in the field, provide a picture of current ideas and methods in the ongoing investigations into the pure mathematical foundations of computability theory. The topics range over computable functions, enumerable sets, degree structures, complexity, subrecursiveness, domains and inductive inference. A number of the articles contain introductory and background material which it is (...)
    Direct download  
     
    Export citation  
     
    My bibliography  
  5.  1
    Jens Erik Fenstad, R. O. Gandy & Gerald E. Sacks (eds.) (1978). Generalized Recursion Theory Ii: Proceedings of the 1977 Oslo Symposium. Sole Distributors for the U.S.A. And Canada, Elsevier North-Holland.
    GENERALIZED RECUBION THEORY II © North-Holland Publishing Company (1978) MONOTONE QUANTIFIERS AND ADMISSIBLE SETS Ion Barwise University of Wisconsin ...
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography  
  6.  2
    Iraj Kalantari & Larry Welch (2004). A Blend of Methods of Recursion Theory and Topology: A Π1 0 Tree of Shadow Points. [REVIEW] Archive for Mathematical Logic 43 (8):991-1008.
    This paper is a sequel to our [7]. In that paper we constructed a Π1 0 tree of avoidable points. Here we construct a Π1 0 tree of shadow points. This tree is a tree of sharp filters, where a sharp filter is a nested sequence of basic open sets converging to a point. In the construction we assign to each basic open set on the tree an address in 2<ω. One interesting fact is that while our Π1 0 tree (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  7.  19
    Herbert B. Enderton (2011). Computability Theory: An Introduction to Recursion Theory. Academic Press.
    Machine generated contents note: 1. The Computability Concept;2. General Recursive Functions;3. Programs and Machines;4. Recursive Enumerability;5. Connections to Logic;6. Degrees of Unsolvability;7. Polynomial-Time Computability;Appendix: Mathspeak;Appendix: Countability;Appendix: Decadic Notation;.
    Direct download  
     
    Export citation  
     
    My bibliography  
  8.  7
    Anil Nerode & Richard A. Shore (eds.) (1985). Recursion Theory. American Mathematical Society.
    iterations of REA operators, as well as extensions, generalizations and other applications are given in [6] while those for the ...
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography   3 citations  
  9.  1
    Jens Erik Fenstad (1980). General Recursion Theory: An Axiomatic Approach. Springer-Verlag.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography   3 citations  
  10.  0
    L. L. Ivanov (1986). Algebraic Recursion Theory. Halsted Press.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography   1 citation  
  11. M. M. Arslanov & Steffen Lempp (eds.) (1999). Recursion Theory and Complexity: Proceedings of the Kazan '97 Workshop, Kazan, Russia, July 14-19, 1997. W. De Gruyter.
    No categories
     
    Export citation  
     
    My bibliography  
  12.  0
    C.-T. Chong (1984). Techniques of Admissible Recursion Theory. Springer-Verlag.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography  
  13.  2
    Jens Erik Fenstad & Peter G. Hinman (eds.) (1974). Generalized Recursion Theory. New York,American Elsevier Pub. Co..
    Provability, Computability and Reflection.
    Direct download  
     
    Export citation  
     
    My bibliography  
  14. Wolfgang Maass (1978). Contributions to [Alpha]- and [Beta]-Recursion Theory. Minerva-Publikation.
    No categories
     
    Export citation  
     
    My bibliography  
  15.  2
    Arnold Beckmann & Wolfram Pohlers (1998). Applications of Cut-Free Infinitary Derivations to Generalized Recursion Theory. Annals of Pure and Applied Logic 94 (1-3):7-19.
    We prove that the boundedness theorem of generalized recursion theory can be derived from the ω-completeness theorem for number theory. This yields a proof of the boundedness theorem which does not refer to the analytical hierarchy theorem.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  16.  0
    Iraj Kalantari & Larry Welch (2003). A Blend of Methods of Recursion Theory and Topology. Annals of Pure and Applied Logic 124 (1-3):141-178.
    This paper is a culmination of our new foundations for recursive analysis through recursive topology as reported in Kalantari and Welch 125; 98 87). While in those papers we developed groundwork for an approach to point free analysis and applied recursion theory, in this paper we blend techniques of recursion theory with those of topology to establish new findings. We present several new techniques different from existing ones which yield interesting results. Incidental to our work is (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  17.  0
    Rod Downey & Michael Stob (1993). Splitting Theorems in Recursion Theory. Annals of Pure and Applied Logic 65 (1):1-106.
    A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to obtain (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  18.  1
    C. T. Chong, Wei Li & Yue Yang (forthcoming). Nonstandard Models in Recursion Theory and Reverse Mathematics. Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    We give a survey of the study of nonstandard models in recursion theory and reverse mathematics. We discuss the key notions and techniques in effective computability in nonstandard models. and their applications to problems concerning combinatorial principles in subsystems of second order arithmetic. Particular attention is given to principles related to Ramsey's Theorem for Pairs.
    Direct download  
     
    Export citation  
     
    My bibliography  
  19.  3
    Sy D. Friedman (1983). Some Recent Developments in Higher Recursion Theory. Journal of Symbolic Logic 48 (3):629-642.
    In recent years higher recursion theory has experienced a deep interaction with other areas of logic, particularly set theory (fine structure, forcing, and combinatorics) and infinitary model theory. In this paper we wish to illustrate this interaction by surveying the progress that has been made in two areas: the global theory of the κ-degrees and the study of closure ordinals.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  20.  1
    Peter Koepke & Benjamin Seyfferth (2009). Ordinal Machines and Admissible Recursion Theory. Annals of Pure and Applied Logic 160 (3):310-318.
    We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, respectively. We (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  21.  0
    Colin Bailey & Rod Downey (1992). Tabular Degrees in \Ga-Recursion Theory. Annals of Pure and Applied Logic 55 (3):205-236.
    Bailey, C. and R. Downey, Tabular degrees in \Ga-recursion theory, Annals of Pure and Applied Logic 55 205–236. We introduce several generalizations of the truth-table and weak-truth-table reducibilities to \Ga-recursion theory. A number of examples are given of theorems that lift from \Gw-recursion theory, and of theorems that do not. In particular it is shown that the regular sets theorem fails and that not all natural generalizations of wtt are the same.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  22.  0
    J. C. E. Dekker & E. Ellentuck (1992). Myhill's Work in Recursion Theory. Annals of Pure and Applied Logic 56 (1-3):43-71.
    In this paper we discuss the following contributions to recursion theory made by John Myhill: two sets are recursively isomorphic iff they are one-one equivalent; two sets are recursively isomorphic iff they are recursively equivalent and their complements are also recursively equivalent; every two creative sets are recursively isomorphic; the recursive analogue of the Cantor–Bernstein theorem; the notion of a combinatorial function and its use in the theory of recursive equivalence types.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  23.  0
    Phokion G. Kolaitis (1985). Canonical Forms and Hierarchies in Generalized Recursion Theory. In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society 42--139.
    Direct download  
     
    Export citation  
     
    My bibliography  
  24.  6
    Simon Thompson (1985). Axiomatic Recursion Theory and the Continuous Functionals. Journal of Symbolic Logic 50 (2):442-450.
    We define, in the spirit of Fenstad [2], a higher type computation theory, and show that countable recursion over the continuous functionals forms such a theory. We also discuss Hyland's proposal from [4] for a scheme with which to supplement S1-S9, and show that this augmented set of schemes fails to generate countable recursion. We make another proposal to which the methods of this section do not apply.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  25. John N. Crossley (ed.) (1967). Sets, Models and Recursion Theory. Amsterdam, North-Holland Pub. Co..
    No categories
     
    Export citation  
     
    My bibliography  
  26. John N. Crossley & Logic Colloquium (1967). Sets, Models and Recursion Theory Proceedings of the Summer School in Mathematical Logic and Tenth Logic Colloquium, Leicester, August-September 1965. North-Holland.
     
    Export citation  
     
    My bibliography  
  27.  9
    Robert E. Byerly (1982). Recursion Theory and the Lambda-Calculus. Journal of Symbolic Logic 47 (1):67-83.
    A semantics for the lambda-calculus due to Friedman is used to describe a large and natural class of categorical recursion-theoretic notions. It is shown that if e 1 and e 2 are godel numbers for partial recursive functions in two standard ω-URS's 1 which both act like the same closed lambda-term, then there is an isomorphism of the two ω-URS's which carries e 1 to e 2.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  28.  4
    Petr Hájek & Antonín Kučera (1989). On Recursion Theory in I∑. Journal of Symbolic Logic 54 (2):576 - 589.
    It is shown that the low basis theorem is meaningful and provable in I∑ 1 and that the priority-free solution to Post's problem formalizes in this theory.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  29.  0
    Petr Hajek & Antonin Kucera (1989). On Recursion Theory in $Isum_1$. Journal of Symbolic Logic 54 (2):576-589.
    It is shown that the low basis theorem is meaningful and provable in $I\sum_1$ and that the priority-free solution to Post's problem formalizes in this theory.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  30.  0
    James H. Schmerl (1998). Difference Sets and Recursion Theory. Mathematical Logic Quarterly 44 (4):515-521.
    There is a recursive set of natural numbers which is the difference set of some recursively enumerable set but which is not the difference set of any recursive set.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  31.  1
    Theodore A. Slaman (1985). Reflection and Forcing in< I> E_-Recursion Theory. Annals of Pure and Applied Logic 29 (1):79-106.
    E -recursive enumerability is compared via forcing to Σ 1 definability. It is shown that for every countable E -closed ordinal κ there is a set of reals, X , so that L κ [ X ] is the least E -closed structure over X.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  32.  9
    G. Longo & E. Moggi (1984). The Hereditary Partial Effective Functionals and Recursion Theory in Higher Types. Journal of Symbolic Logic 49 (4):1319-1332.
    A type-structure of partial effective functionals over the natural numbers, based on a canonical enumeration of the partial recursive functions, is developed. These partial functionals, defined by a direct elementary technique, turn out to be the computable elements of the hereditary continuous partial objects; moreover, there is a commutative system of enumerations of any given type by any type below (relative numberings). By this and by results in [1] and [2], the Kleene-Kreisel countable functionals and the hereditary effective operations (HEO) (...)
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  33.  3
    Robert E. Byerly (1982). An Invariance Notion in Recursion Theory. Journal of Symbolic Logic 47 (1):48-66.
    A set of godel numbers is invariant if it is closed under automorphisms of (ω, ·), where ω is the set of all godel numbers of partial recursive functions and · is application (i.e., n · m ≃ φ n (m)). The invariant arithmetic sets are investigated, and the invariant recursively enumerable sets and partial recursive functions are partially characterized.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  34.  41
    Nigel Cutland (1980). Computability, an Introduction to Recursive Function Theory. Cambridge University Press.
    What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to (...)
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   7 citations  
  35.  6
    Giuseppe Longo (1988). On Church's Formal Theory of Functions and Functionals: The Λ-Calculus: Connections to Higher Type Recursion Theory, Proof Theory, Category Theory. Annals of Pure and Applied Logic 40 (2):93-133.
    Direct download  
     
    Export citation  
     
    My bibliography  
  36.  45
    Wolfgang Maass (1978). The Uniform Regular Set Theorem in Α-Recursion Theory. Journal of Symbolic Logic 43 (2):270-279.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  37.  2
    L. A. Harrington & D. B. MacQueen (1976). Selection in Abstract Recursion Theory. Journal of Symbolic Logic 41 (1):153-158.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  38.  3
    R. G. Downey & Stuart A. Kurtz (1986). Recursion Theory and Ordered Groups. Annals of Pure and Applied Logic 32 (2):137-151.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  39.  1
    R. Downey (1984). Some Remarks on a Theorem of Iraj Kalantari Concerning Convexity and Recursion Theory. Mathematical Logic Quarterly 30 (19‐24):295-302.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  40.  1
    J. B. Remmel (1980). Recursion Theory on Algebraic Structures with Independent Sets. Annals of Mathematical Logic 18 (2):153-191.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  41.  11
    Thomas J. Grilliot (1972). Omitting Types: Application to Recursion Theory. Journal of Symbolic Logic 37 (1):81-89.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  42.  48
    J. B. Remmel (1980). Recursion Theory on Orderings. II. Journal of Symbolic Logic 45 (2):317-333.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  43.  6
    Klaus Ambos-Spies (1984). An Extension of the Nondiamond Theorem in Classical and Α-Recursion Theory. Journal of Symbolic Logic 49 (2):586-607.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  44.  16
    Carl G. Jockusch Jr (1972). Ramsey's Theorem and Recursion Theory. Journal of Symbolic Logic 37 (2):268-280.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  45.  10
    Robert A. Di Paola & Alex Heller (1987). Dominical Categories: Recursion Theory Without Elements. Journal of Symbolic Logic 52 (3):594-635.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  46.  9
    Robert A. Paola & Alex Heller (1987). Dominical Categories: Recursion Theory Without Elements. Journal of Symbolic Logic 52 (3):594 - 635.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  47.  0
    G. Kreisel, R. O. Gandy & C. E. M. Yates (1975). Some Reasons for Generalizing Recursion Theory. Journal of Symbolic Logic 40 (2):230-232.
    Direct download  
     
    Export citation  
     
    My bibliography   2 citations  
  48.  2
    Steven Homer (1980). Two Splitting Theorems for Beta-Recursion Theory. Annals of Mathematical Logic 18 (2):137-151.
  49.  1
    C. T. Chong (1986). 1-Generic Degrees and Minimal Degrees in Higher Recursion Theory, II. Annals of Pure and Applied Logic 31 (2):165-175.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  50.  2
    Roman Murawski (1998). The Contribution of Polish Logicians to Recursion Theory. In Katarzyna Kijania-Placek & Jan Woleński (eds.), The Lvov-Warsaw School and Contemporary Philosophy. Kluwer Academic Publishers 265--282.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography  
1 — 50 / 1000