The Experts below are selected from a list of 11583 Experts worldwide ranked by ideXlab platform
Sy-david Friedman - One of the best experts on this subject based on the ideXlab platform.
-
fragments of kripke platek set Theory and the metamathematics of alpha ź Recursion Theory
Archive for Mathematical Logic, 2016Co-Authors: Sy-david Friedman, Tin Lok WongAbstract:The foundation scheme in set Theory asserts that every nonempty class has an $$\in $$ź-minimal element. In this paper, we investigate the logical strength of the foundation principle in basic set Theory and $$\alpha $$ź-Recursion Theory. We take KP set Theory without foundation (called KP$$^-$$-) as the base Theory. We show that KP$$^-$$- + $$\Pi _1$$ź1-Foundation + $$V=L$$V=L is enough to carry out finite injury arguments in $$\alpha $$ź-Recursion Theory, proving both the Friedberg-Muchnik theorem and the Sacks splitting theorem in this Theory. In addition, we compare the strengths of some fragments of KP.
-
Fragments of Kripke–Platek set Theory and the metamathematics of $$\alpha $$ α -Recursion Theory
Archive for Mathematical Logic, 2016Co-Authors: Sy-david Friedman, Tin Lok WongAbstract:The foundation scheme in set Theory asserts that every nonempty class has an ∈-minimal element. In this paper, we investigate the logical strength of the foundation principle in basic set Theory and α-Recursion Theory. We take KP set Theory without foundation (called KP−) as the base Theory. We show that KP− + Π1-Foundation + V=L is enough to carry out finite injury arguments in α-Recursion Theory, proving both the Friedberg-Muchnik theorem and the Sacks splitting theorem in this Theory. In addition, we compare the strengths of some fragments of KP
-
Handbook of Computability Theory - Ordinal Recursion Theory
Handbook of Computability Theory, 1999Co-Authors: Chitat Chong, Sy-david FriedmanAbstract:This chapter presents the basic concepts and techniques of ordinal Recursion Theory, with particular emphasis on the new ideas that have been introduced to study Recursion-theoretic problems assuming only Є l -admissibility on a domain greater than ω. As Є 1 -admissibility is easily lost under relativization, the chapter discusses β-Recursion Theory, which attempts to develop Recursion Theory on arbitrary limit ordinals. The chapter concludes with the discussion of admissibility spectra. Some of the techniques and ideas that were invented in ordinal Recursion Theory have recently found applications in “Recursion Theory on fragments of Peano arithmetic.” This is an unexpected turn of events that signal a basic unity among various fields in Recursion Theory and fine structure Theory.
-
ordinal Recursion Theory
Studies in logic and the foundations of mathematics, 1999Co-Authors: C T Chong, Sy-david FriedmanAbstract:This chapter presents the basic concepts and techniques of ordinal Recursion Theory, with particular emphasis on the new ideas that have been introduced to study Recursion-theoretic problems assuming only Є l -admissibility on a domain greater than ω. As Є 1 -admissibility is easily lost under relativization, the chapter discusses β-Recursion Theory, which attempts to develop Recursion Theory on arbitrary limit ordinals. The chapter concludes with the discussion of admissibility spectra. Some of the techniques and ideas that were invented in ordinal Recursion Theory have recently found applications in “Recursion Theory on fragments of Peano arithmetic.” This is an unexpected turn of events that signal a basic unity among various fields in Recursion Theory and fine structure Theory.
-
Ordinal Recursion Theory
arXiv: Logic, 1996Co-Authors: Chitat Chong, Sy-david FriedmanAbstract:In this article, intended for the Handbook of Recursion Theory, we survey Recursion Theory on the ordinal numbers, with sections devoted to $\alpha$-Recursion Theory, $\beta$-Recursion Theory and the study of the admissibility spectrum.
Manuel L. Campagnolo - One of the best experts on this subject based on the ideXlab platform.
-
Continuous-time computation with restricted integration capabilities
Theoretical Computer Science, 2003Co-Authors: Manuel L. CampagnoloAbstract:Recursion Theory on the reals, the analog counterpart of recursive function Theory, is an approach to continuous-time computation inspired by the models of Classical Physics. In Recursion Theory on the reals, the discrete operations of standard Recursion Theory are replaced by operations on continuous functions such as composition and various forms of differential equations like indefinite integrals, linear differential equations and more general Cauchy problems. We define classes of real recursive functions in a manner similar to the standard Recursion Theory and we study their complexity. We prove both upper and lower bounds for several classes of real recursive functions, which lie inside the elementary functions, and can be characterized in terms of space complexity. In particular, we show that hierarchies of real recursive classes closed under restricted integration operations are related to the exponential space hierarchy. The results in this paper, combined with earlier results, suggest that there is a close connection between analog complexity classes and subrecursive classes, at least in the region between FLINSPACE and the primitive recursive functions.
-
UMC - The Complexity of Real Recursive Functions
Unconventional Models of Computation, 2002Co-Authors: Manuel L. CampagnoloAbstract:We explore Recursion Theory on the reals, the analog counterpart of recursive function Theory. In Recursion Theory on the reals, the discrete operations of standard Recursion Theory are replaced by operations on continuous functions, such as composition and various forms of differential equations. We define classes of real recursive functions, in a manner similar to the classical approach in Recursion Theory, and we study their complexity. In particular, we prove both upper and lower bounds for several classes of real recursive functions, which lie inside the primitive recursive functions and, therefore, can be characterized in terms of standard computational complexity.
Chitat Chong - One of the best experts on this subject based on the ideXlab platform.
-
Recursion Theory: Computational Aspects of Definability
2015Co-Authors: Chitat ChongAbstract:This monograph presents Recursion Theory from a generalized and largely global point of view. A major theme is the study of the structures of degrees arising from two key notions of reducibility, the Turing degrees and the hyperdegrees, using ideas and techniques beyond those of classical Recursion Theory. These include structure Theory, hyperarithmetic determinacy and rigidity, basis theorems, independence results on Turing degrees, as well as applications to higher randomness.
-
Nonstandard Models In Recursion Theory And Reverse Mathematics
The Bulletin of Symbolic Logic, 2014Co-Authors: Chitat Chong, Yue YangAbstract: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.
-
Handbook of Computability Theory - Ordinal Recursion Theory
Handbook of Computability Theory, 1999Co-Authors: Chitat Chong, Sy-david FriedmanAbstract:This chapter presents the basic concepts and techniques of ordinal Recursion Theory, with particular emphasis on the new ideas that have been introduced to study Recursion-theoretic problems assuming only Є l -admissibility on a domain greater than ω. As Є 1 -admissibility is easily lost under relativization, the chapter discusses β-Recursion Theory, which attempts to develop Recursion Theory on arbitrary limit ordinals. The chapter concludes with the discussion of admissibility spectra. Some of the techniques and ideas that were invented in ordinal Recursion Theory have recently found applications in “Recursion Theory on fragments of Peano arithmetic.” This is an unexpected turn of events that signal a basic unity among various fields in Recursion Theory and fine structure Theory.
-
Ordinal Recursion Theory
arXiv: Logic, 1996Co-Authors: Chitat Chong, Sy-david FriedmanAbstract:In this article, intended for the Handbook of Recursion Theory, we survey Recursion Theory on the ordinal numbers, with sections devoted to $\alpha$-Recursion Theory, $\beta$-Recursion Theory and the study of the admissibility spectrum.
Steffen Lempp - One of the best experts on this subject based on the ideXlab platform.
-
Recursion Theory and Complexity: Proceedings of the Kazan '97 Workshop, Kazan, Russia, July 14-19, 1997 - Recursion Theory and Complexity: Proceedings of the Kazan '97 Workshop, Kazan, Russia, July 14-19, 1997
1999Co-Authors: Marat M. Arslanov, Steffen LemppAbstract:Priority method in generalized computability, I.V. Ashaev polynomial time versus computable Boolean algebras, D. Cenzer, J.B. Remmel the proof-theoretic strength of the Dushnik-Miller theorem, R.G. Downey, S. Lempp effectively nowhere simple relations on computable models, V. Harizanov jump traces with large gaps, P.G. Hinman weak recursive degrees and a problem of Spector, Sh.T. Ishmukhametov compositions of permutations and algorithmic reducibilities, K.V. Korovin some properties of majorant-computability, M.V. Korovina, O.V. Kudinov hyperarithmetical functions and algebraicity, A.C. Morozov weak presentation of fields, not extendible to Recursion presentations, A. Shlapentokh jumps of Sigma 0/2-high e-degrees and properly Sigma0/2 e-degrees, R.A. Shore, A. Sorbi the e-reducibility and problem of the nontotal property of e-degrees, B.Ja. Solon algebras of recursive functions, V.D. Solo'vev Sigma2-induction and cuppable degrees, Yang Yue. Open problems from Kazan '97 workshop. List of WORCT'97 participants, Recursion Theory. List of talks.
Marat M. Arslanov - One of the best experts on this subject based on the ideXlab platform.
-
Recursion Theory and Complexity: Proceedings of the Kazan '97 Workshop, Kazan, Russia, July 14-19, 1997 - Recursion Theory and Complexity: Proceedings of the Kazan '97 Workshop, Kazan, Russia, July 14-19, 1997
1999Co-Authors: Marat M. Arslanov, Steffen LemppAbstract:Priority method in generalized computability, I.V. Ashaev polynomial time versus computable Boolean algebras, D. Cenzer, J.B. Remmel the proof-theoretic strength of the Dushnik-Miller theorem, R.G. Downey, S. Lempp effectively nowhere simple relations on computable models, V. Harizanov jump traces with large gaps, P.G. Hinman weak recursive degrees and a problem of Spector, Sh.T. Ishmukhametov compositions of permutations and algorithmic reducibilities, K.V. Korovin some properties of majorant-computability, M.V. Korovina, O.V. Kudinov hyperarithmetical functions and algebraicity, A.C. Morozov weak presentation of fields, not extendible to Recursion presentations, A. Shlapentokh jumps of Sigma 0/2-high e-degrees and properly Sigma0/2 e-degrees, R.A. Shore, A. Sorbi the e-reducibility and problem of the nontotal property of e-degrees, B.Ja. Solon algebras of recursive functions, V.D. Solo'vev Sigma2-induction and cuppable degrees, Yang Yue. Open problems from Kazan '97 workshop. List of WORCT'97 participants, Recursion Theory. List of talks.