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

1000+ found
Order:
  1. 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  
  2.  2
    Peter G. Hinman (1978). Recursion-Theoretic Hierarchies. Springer-Verlag.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography   61 citations  
  3.  2
    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   29 citations  
  4.  8
    H. E. Rose (1984). Subrecursion: Functions and Hierarchies. Oxford University Press.
  5.  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  
  6.  30
    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  
  7.  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  
  8.  2
    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  
  9.  2
    Jens Erik Fenstad (1980). General Recursion Theory: An Axiomatic Approach. Springer-Verlag.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography   7 citations  
  10.  8
    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   5 citations  
  11.  1
    L. L. Ivanov (1986). Algebraic Recursion Theory. Halsted Press.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography   2 citations  
  12. C.-T. Chong (1984). Techniques of Admissible Recursion Theory. Springer-Verlag.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography   2 citations  
  13.  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  
  14. 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  
  15.  20
    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  
  16.  3
    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  
  17. Wolfgang Maass (1978). Contributions to [Alpha]- and [Beta]-Recursion Theory. Minerva-Publikation.
    No categories
     
    Export citation  
     
    My bibliography  
  18.  3
    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   2 citations  
  19.  1
    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   3 citations  
  20.  8
    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  
  21. 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   4 citations  
  22.  11
    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   1 citation  
  23.  3
    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  
  24.  2
    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  
  25.  2
    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  
  26.  9
    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  
  27. John N. Crossley (ed.) (1967). Sets, Models and Recursion Theory. Amsterdam, North-Holland Pub. Co..
    No categories
     
    Export citation  
     
    My bibliography  
  28. 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  
  29.  12
    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  
  30.  9
    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  
  31. 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  
  32. G. Metakides, A. Nerode, J. N. Crossley, Iraj Kalantari & Allen Retzlaff (1986). Recursion Theory and Algebra. Journal of Symbolic Logic 51 (1):229-232.
    Direct download  
     
    Export citation  
     
    My bibliography   17 citations  
  33. 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  
  34. 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  
  35.  1
    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   8 citations  
  36. Melvin Fitting (1986). Fundamentals of Generalized Recursion Theory. Journal of Symbolic Logic 51 (4):1078-1079.
    Direct download  
     
    Export citation  
     
    My bibliography   6 citations  
  37.  14
    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.
  38.  7
    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   4 citations  
  39.  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   6 citations  
  40.  4
    H. Luckhardt (1979). A Limit for Higher Recursion Theory. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 25 (30):475-479.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  41.  8
    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   4 citations  
  42.  22
    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   4 citations  
  43.  7
    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  
  44.  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   3 citations  
  45.  4
    R. Downey (1984). Some Remarks on a Theorem of Iraj Kalantari Concerning Convexity and Recursion Theory. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 30 (19-24):295-302.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  46.  11
    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   2 citations  
  47.  12
    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  
  48.  6
    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  
  49.  14
    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  
  50.  4
    Michael Machtey (1974). Minimal Degrees in Generalized Recursion Theory. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 20 (8-12):133-148.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
1 — 50 / 1000