Results for 'Recursion theory'

1000+ found
Order:
  1.  5
    Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers.Piergiorgio Odifreddi - 1989 - 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   29 citations  
  2.  2
    Diagonal Fixed Points in Algebraic Recursion Theory.Jordan Zashev - 2005 - 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.  31
    Recursion Theory for Metamathematics.Raymond M. Smullyan - 1993 - 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.
    Direct download  
     
    Export citation  
     
    My bibliography  
  4.  19
    Computability, Enumerability, Unsolvability: Directions in Recursion Theory.S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.) - 1996 - 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.  3
    Generalized Recursion Theory Ii: Proceedings of the 1977 Oslo Symposium.Jens Erik Fenstad, R. O. Gandy & Gerald E. Sacks (eds.) - 1978 - 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 ...
    Direct download  
     
    Export citation  
     
    My bibliography  
  6.  4
    General Recursion Theory: An Axiomatic Approach.Jens Erik Fenstad - 1980 - Springer Verlag.
  7.  8
    Recursion Theory.Anil Nerode & Richard A. Shore (eds.) - 1985 - American Mathematical Society.
    iterations of REA operators, as well as extensions, generalizations and other applications are given in [6] while those for the ...
    Direct download  
     
    Export citation  
     
    My bibliography   5 citations  
  8.  2
    Algebraic Recursion Theory.L. L. Ivanov - 1986 - Halsted Press.
  9.  1
    Techniques of Admissible Recursion Theory.C.-T. Chong - 1984 - Springer Verlag.
  10.  2
    A Blend of Methods of Recursion Theory and Topology: A Π1 0 Tree of Shadow Points. [REVIEW]Iraj Kalantari & Larry Welch - 2004 - 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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  11. Recursion Theory and Complexity: Proceedings of the Kazan '97 Workshop, Kazan, Russia, July 14-19, 1997.M. M. Arslanov & Steffen Lempp (eds.) - 1999 - W. De Gruyter.
  12.  24
    Computability Theory: An Introduction to Recursion Theory.Herbert B. Enderton - 2011 - 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  
  13.  4
    Generalized Recursion Theory.Jens Erik Fenstad & Peter G. Hinman (eds.) - 1974 - New York: American Elsevier Pub. Co..
    Provability, Computability and Reflection.
    Direct download  
     
    Export citation  
     
    My bibliography  
  14. Contributions to [Alpha]- and [Beta]-Recursion Theory.Wolfgang Maass - 1978 - Minerva-Publikation.
     
    Export citation  
     
    My bibliography  
  15. Splitting Theorems in Recursion Theory.Rod Downey & Michael Stob - 1993 - 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   8 citations  
  16.  2
    A Blend of Methods of Recursion Theory and Topology.Iraj Kalantari & Larry Welch - 2003 - 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   4 citations  
  17.  3
    Ordinal Machines and Admissible Recursion Theory.Peter Koepke & Benjamin Seyfferth - 2009 - 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   2 citations  
  18.  8
    Applications of Cut-Free Infinitary Derivations to Generalized Recursion Theory.Arnold Beckmann & Wolfram Pohlers - 1998 - 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  
  19.  11
    Some Recent Developments in Higher Recursion Theory.Sy D. Friedman - 1983 - 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 (7 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  20.  4
    Tabular Degrees in \Ga-Recursion Theory.Colin Bailey & Rod Downey - 1992 - 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  
  21.  2
    Myhill's Work in Recursion Theory.J. C. E. Dekker & E. Ellentuck - 1992 - 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  
  22.  2
    Nonstandard Models in Recursion Theory and Reverse Mathematics.C. T. Chong, Wei Li & Yue Yang - forthcoming - 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  
  23. Canonical Forms and Hierarchies in Generalized Recursion Theory.Phokion G. Kolaitis - 1985 - In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society. pp. 42--139.
    Direct download  
     
    Export citation  
     
    My bibliography  
  24.  9
    Axiomatic Recursion Theory and the Continuous Functionals.Simon Thompson - 1985 - 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 (7 more)  
     
    Export citation  
     
    My bibliography  
  25. Sets, Models and Recursion Theory.John N. Crossley (ed.) - 1967 - Amsterdam: North-Holland Pub. Co..
     
    Export citation  
     
    My bibliography  
  26. Sets, Models and Recursion Theory Proceedings of the Summer School in Mathematical Logic and Tenth Logic Colloquium, Leicester, August-September 1965.John N. Crossley & Logic Colloquium - 1967 - North-Holland.
     
    Export citation  
     
    My bibliography  
  27.  12
    Recursion Theory and the Lambda-Calculus.Robert E. Byerly - 1982 - 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 (7 more)  
     
    Export citation  
     
    My bibliography  
  28.  9
    On Recursion Theory in I∑.Petr Hájek & Antonín Kučera - 1989 - 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. On Recursion Theory in $Isum_1$.Petr Hajek & Antonin Kucera - 1989 - 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 (5 more)  
     
    Export citation  
     
    My bibliography  
  30. Recursion Theory and Algebra.G. Metakides, A. Nerode, J. N. Crossley, Iraj Kalantari & Allen Retzlaff - 1986 - Journal of Symbolic Logic 51 (1):229-232.
    Direct download  
     
    Export citation  
     
    My bibliography   17 citations  
  31. The Uniform Regular Set Theorem in Α-Recursion Theory.Wolfgang Maass - 1978 - Journal of Symbolic Logic 43 (2):270-279.
  32.  1
    Nonstandard Models in Recursion Theory and Reverse Mathematics.C. T. Chong, Wei Li & Yue Yang - 2014 - Bulletin of Symbolic Logic 20 (2):170-200.
  33. Recursion Theory on Orderings. II.J. B. Remmel - 1980 - Journal of Symbolic Logic 45 (2):317-333.
  34.  23
    Ramsey's Theorem and Recursion Theory.Carl G. Jockusch Jr - 1972 - Journal of Symbolic Logic 37 (2):268-280.
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography   10 citations  
  35.  1
    Recursion Theory on Algebraic Structures with Independent Sets.J. B. Remmel - 1980 - Annals of Mathematical Logic 18 (2):153-191.
  36.  8
    Recursion Theory and Ordered Groups.R. G. Downey & Stuart A. Kurtz - 1986 - Annals of Pure and Applied Logic 32 (2):137-151.
  37.  3
    Some Reasons for Generalizing Recursion Theory.G. Kreisel, R. O. Gandy & C. E. M. Yates - 1975 - Journal of Symbolic Logic 40 (2):230-232.
    Direct download  
     
    Export citation  
     
    My bibliography   8 citations  
  38. Fundamentals of Generalized Recursion Theory.Melvin Fitting - 1986 - Journal of Symbolic Logic 51 (4):1078-1079.
    Direct download  
     
    Export citation  
     
    My bibliography   6 citations  
  39.  11
    An Extension of the Nondiamond Theorem in Classical and Α-Recursion Theory.Klaus Ambos-Spies - 1984 - Journal of Symbolic Logic 49 (2):586-607.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  40.  16
    Some Remarks on a Theorem of Iraj Kalantari Concerning Convexity and Recursion Theory.R. Downey - 1984 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 30 (19-24):295-302.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  41.  14
    A Limit for Higher Recursion Theory.H. Luckhardt - 1979 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 25 (30):475-479.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  42.  3
    Some Remarks on a Theorem of Iraj Kalantari Concerning Convexity and Recursion Theory.R. Downey - 1984 - Mathematical Logic Quarterly 30 (19‐24):295-302.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  43.  16
    Minimal Degrees in Generalized Recursion Theory.Michael Machtey - 1974 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 20 (8-12):133-148.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  44.  7
    Reflection and Forcing in< I> E_-Recursion Theory.Theodore A. Slaman - 1985 - 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  
  45.  14
    Some Reflections on the Foundations of Ordinary Recursion Theory and a New Proposal.George Tourlakis - 1986 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 32 (31-34):503-515.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  46.  16
    On Church's Formal Theory of Functions and Functionals: The Λ-Calculus: Connections to Higher Type Recursion Theory, Proof Theory, Category Theory.Giuseppe Longo - 1988 - Annals of Pure and Applied Logic 40 (2):93-133.
  47.  11
    The Hereditary Partial Effective Functionals and Recursion Theory in Higher Types.G. Longo & E. Moggi - 1984 - 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 (7 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  48.  14
    Omitting Types: Application to Recursion Theory.Thomas J. Grilliot - 1972 - Journal of Symbolic Logic 37 (1):81-89.
  49.  17
    Dominical Categories: Recursion Theory Without Elements.Robert A. Di Paola & Alex Heller - 1987 - Journal of Symbolic Logic 52 (3):594-635.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  50.  8
    Recursion Theory on Orderings. I. A Model Theoretic Setting.G. Metakides & J. B. Remmel - 1979 - Journal of Symbolic Logic 44 (3):383-402.
1 — 50 / 1000