Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 16 of 16 for “"recursion theory"”.

  1. Classical Theorems in Reverse Mathematics and Higher Recursion Theory

    … the view point of reverse mathematics and higher recursion theory. These classical theorems include the existence of a proper d-r.e. degree, Friedberg numbering and the Kechris-Woodin rank of everywhere differentiable functions.

    nus Repository record for Classical Theorems in Reverse Mathematics and Higher Recursion Theory (opens in a new tab) Download file for Classical Theorems in Reverse Mathematics and Higher Recursion Theory (opens in a new tab)

  2. Aspects of Recursion Theory in Arithmetical Theories and Categories

    Traditional recursion theory is the study of computable functions on the natural numbers. This thesis considers recursion theory in first-order arithmetical theories and categories, thus expanding the work of Ritchie and Young, Lambek, Scott, and Hofstra. We give a complete characterisation of the …

    ottawa-retro Repository record for Aspects of Recursion Theory in Arithmetical Theories and Categories (opens in a new tab)

  3. Elements Of Classical Recursion Theory: Degree-Theoretic Properties And Combinatorial Properties

    In Recursion Theory (Computability Theory), we study Turing degrees in terms of their degree-theoretic properties and combinatorial properties. In this dissertation we present several results in terms of connections either between these two categories of properties or within each category. Our …

    cornell Repository record for Elements Of Classical Recursion Theory: Degree-Theoretic Properties And Combinatorial Properties (opens in a new tab)

  4. Another notion of recursiveness

    … these properties coincide with the ones for recursion theory. The equivalences of finite describability and recursiveness bring model theory and recursion theory slightly together.

    ubc Repository record for Another notion of recursiveness (opens in a new tab) Download PDF for Another notion of recursiveness (opens in a new tab)

  5. Some results on e-genericity and recursively enumerable weak truth table degrees

    In this manuscript we explore two topics in recursion theory and their interaction.

    uiuc Repository record for Some results on e-genericity and recursively enumerable weak truth table degrees (opens in a new tab)

  6. TURNING DEGREES CONSTRUCTIONS AND THEIR INDUCTION STRENGTH IN REVERSE MATHEMATICS

    … in the context of classical computability theory (recursion Theory) and reverse recursion theory. In the first part, we prove that P + \Sigma_1 Induction proves the existence of isolated d.c.e. degrees and upper isolated d.c.e. degrees. We also prove that P + \Sigma_3 Induction verifies the …

    nus Repository record for TURNING DEGREES CONSTRUCTIONS AND THEIR INDUCTION STRENGTH IN REVERSE MATHEMATICS (opens in a new tab) Download file for TURNING DEGREES CONSTRUCTIONS AND THEIR INDUCTION STRENGTH IN REVERSE MATHEMATICS (opens in a new tab)

  7. ON TRANSFINITE LEVELS OF THE ERSHOV HIERARCHY

    … study Turing degrees in the context of classical recursion theory. The dissertation is motivated by the \Sigma_1-elementary substructure problem. We consider the problem for transfinite levels of the Ershov hierarchy. The techniques in our results are motivated by two remarkable theorems, Sacks …

    nus Repository record for ON TRANSFINITE LEVELS OF THE ERSHOV HIERARCHY (opens in a new tab) Download file for ON TRANSFINITE LEVELS OF THE ERSHOV HIERARCHY (opens in a new tab)

  8. Universal domains for sequential computation

    Classical recursion theory asserts that all conventional programming languages are equally expressive because they can define all partial recursive functions over the natural numbers. However, most real programming languages support some form of higher-order data such as potentially infinite …

    rice Repository record for Universal domains for sequential computation (opens in a new tab)

  9. Sets, Models, And Proofs: Topics In The Theory Of Recursive Functions

    SETS, MODELS, AND PROOFS: TOPICS IN THE THEORY OF RECURSIVE FUNCTIONS David Roger Belanger, Ph.D. Cornell University We prove results in various areas of recursion theory. First, in joint work with Richard Shore, we prove a new jump-inversion result for ideals of recursively enumerable (r.e.) …

    cornell Repository record for Sets, Models, And Proofs: Topics In The Theory Of Recursive Functions (opens in a new tab)

  10. The role of true finiteness in the admissible recursively enumerable degrees

    When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, …

    cornell Repository record for The role of true finiteness in the admissible recursively enumerable degrees (opens in a new tab)

  11. Type-free truth

    … to investigate some of their model-theoretic, recursion-theoretic and proof-theoretic aspects, and to evaluate their philosophical significance. In Part I we first outline some motivations for studying formal theories of truth, fix some terminology, provide some background on Tarski’s and …

    lmu-germany Repository record for Type-free truth (opens in a new tab)

  12. THE STRUCTURE OF D.R.E. DEGREES

    This thesis is highly motivated by d.r.e. Nondensity Theorem (Cooper, Harrington, Lachlan, Lempp, and Soare in 1991), which states that there exists a maximal d.r.e. degree. Very few results on maximal d.r.e. degrees were found as the construction is too complicated to work with. Therefore, it is …

    nus Repository record for THE STRUCTURE OF D.R.E. DEGREES (opens in a new tab) Download file for THE STRUCTURE OF D.R.E. DEGREES (opens in a new tab)

  13. Constructing higher-order de Bruijn graphs

    We construct binary de Bruijn graphs of odd order using recursive generation. We also explore the properties and nuances of these particular graphs. The recursive method developed for this thesis could in principle be used for other de Bruijn graphs of a different order. Suggestions on how this is …

    nps Repository record for Constructing higher-order de Bruijn graphs (opens in a new tab)

  14. Well-Ordering Principles across Reverse Mathematics

    … We begin by exploring effective transfinite recursion, a concept from recursion theory that can be used for the definition of computable functions along ordinals. In the context of second-order arithmetic, the logical framework of reverse mathematics, we can formulate a similar principle, …

    wurz-thes Repository record for Well-Ordering Principles across Reverse Mathematics (opens in a new tab)

  15. Computability Theory and Some Applications

    We explore various areas of computability theory, ranging from applications in computable structure theory primarily focused on problems about computing isomorphisms, to a number of new results regarding the degree-theoretic notion of the bounded Turing hierarchy. In Chapter 2 (joint with Csima, …

    waterloo Repository record for Computability Theory and Some Applications (opens in a new tab)

  16. Números naturais parciais

    Os números naturais parciais são informações parciais sobre números naturais e w. As propriedades matemáticas do domínio de números naturais parciais e de funções que envolvem este domínio são estudadas via o use da teoria dos domínios de Scott. A manipulação formal de naturais parciais é estudada …

    brazil-ufrgs Repository record for Números naturais parciais (opens in a new tab)