Search
Search Results
-
Deeper Computability
In this Chapter, we will develop a number of more advanced tools we can use to tackle issues in computability theory. In particular, we will be able...
-
A Tree of Guesses (Weak Thickness Lemma)
The priority tree, which we call a “tree of guesses,” is introduced, and used for a construction involving infinite injury. The associated concept of...
-
Priorities (A Splitting Theorem)
A simple priority argument is motivated and presented.
-
Notation and Terms
An index of notation and terms is given, along with general comments about the notation and the pseudo-code used in this book.
-
Induction and bounding
The most common kind of reverse mathematics result shows that a given problem requires a particular set existence axiom to solve. Accordingly, we...
-
Witness Lists (Density Theorem)
The algorithm in this chapter uses and extends many of the techniques that we have seen so far. Also, it introduces a few more, such as “coding,”...
-
The propositional normal default logic and the finite/infinite injury priority method
In propositional normal default logic, given a default theory (Δ, D ) and a well-defined ordering of D , there is a method to construct an extension of...
-
Computability of Real Numbers
In scientific computation and engineering real numbers are typically approximated by rational numbers which approximate, in principle, the real...
-
Ramsey’s theorem
Ramsey proved his eponymous theorem in his 1929 paper “On a problem of formal logic” [253]. The focus was actually not on combinatorics at all, but...
-
Other combinatorial principles
Seetapun’s theorem (Theorem 8.3.1) and the follow-up work of Cholak, Jockusch, and Slaman [33] led to the realization that not only are there natural...
-
Semilattices of Punctual Numberings
The theory of numberings studies uniform computations for classes of mathematical objects. A large body of literature is devoted to investigations of...
-
Computable Measure Theory and Algorithmic Randomness
We provide a survey of recent results in computable measure and probability theory, from the perspectives of both computable analysis and algorithmic...
-
Prolepsis
Learning something is not a trivial act – the ancient Greeks were quite aware of the difficulties attendant to the creation of something from...
-
The Finite Injury Method
A positive solution to Post’s problem was finally achieved by Friedberg in [Friedberg 1957] and independently by Muchnik in [Muchnik 1956], who built...
-
Genericity of Weakly Computable Objects
In computability theory many results state the existence of objects that in many respects lack algorithmic structure but at the same time are...
-
Strength and Weakness in Computable Structure Theory
We survey the current results about degrees of categoricity and the degrees that are low for isomorphism as well as the proof techniques used in the...
-
More Lachlan Games
With the Kleene-Post [1954] paper on oracle constructions presented in Chapter 6 , and the...
-
There Are No Maximal d.c.e. wtt-degrees
In this article, we will study the weak-truth-table (wtt, for short) degrees of d.c.e. sets and show that there is no maximal d.c.e. wtt-degree.
-
Detecting requirements defects with NLP patterns: an industrial experience in the railway domain
In the railway safety-critical domain requirements documents have to abide to strict quality criteria. Rule-based natural language processing (NLP)...
-
Nondensity of Double Bubbles in the D.C.E. Degrees
In this paper, we show that the so-called “double bubbles” are not downward dense in the d.c.e. degrees. Here, a pair of d.c.e. degrees...