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"”.
-
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.
-
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 …
-
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 …
-
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.
-
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.
-
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 …
-
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 …
-
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 …
-
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.) …
-
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, …
-
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 …
-
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 …
-
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 …
-
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, …
-
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, …
-
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 …