Search
Search Results
-
Computable and c.e. Sets
This a brief introduction to Turing machines and Church’s Thesis. Some key terms such as “computable,”“c.e.,” and “c.e.n.” are defined and discussed.
-
Enumerations of Recursive and Semi-Recursive Sets
We saw that the semi-recursive sets are computably enumerable and vice versa (Sect. 6.4 ). In this chapter we...
-
Generically Computable Abelian Groups
Generically computable sets, as introduced by Jockusch and Schupp, have been of great interest in recent years. This idea of approximate...
-
Some Observations on Mitotic Sets
A computably enumerable (c.e.) set A is mitotic if it can be split into two c.e. sets...
-
C.E. Degrees and the Priority Method
Among the Turing degrees, the so-called computably enumerable (c.e.) degrees are all-important. This is because they stem from c.e. sets, the sets...
-
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...
-
Speedable Left-c.e. Numbers
A left-c.e. real number \(\alpha \) is \(\rho \)-speedable if there is a computable left approximation \(a_0, a_1, \ldots \) of \(\alpha \) and a...
-
Computability of Subsets of Metric Spaces
We present a survey on computability of subsets of Euclidean space and, more generally, computability concepts on metric spaces and their subsets. In...
-
On the Differences and Sums of Strongly Computably Enumerable Real Numbers
A real number is called left c.e. (right c.e.) if it is the limit of an increasing (decreasing) computable sequence of rational numbers. In...
-
Semi-Recursiveness
This chapter introduces the semi-recursive relations \(Q(\vec x)\) ....
-
Creative and Productive Sets; Completeness and Incompleteness
This chapter introduces the very important topic of productive and creative sets, the simple sets of Post, and also takes an in depth look at the...
-
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.
-
Fixed Point Theorems in Computability Theory
We give a quick survey of the various fixed point theorems in computability theory, partial combinatory algebra, and the theory of numberings, as...
-
Computability of Real Numbers
In scientific computation and engineering real numbers are typically approximated by rational numbers which approximate, in principle, the real...
-
Computability theory
One of our primary tools for studying the difficulty of producing a solution to a problem will be computability. The theory of computability is a...
-
Undecidable Problems
We prove a number of natural problems are undecidable. We do this by coding the halting problem into them. These problems include Conway’s...
-
A Journey to Computably Enumerable Structures (Tutorial Lectures)
The tutorial focuses on computably enumerable (c.e.) structures. These structures form a class that properly extends the class of all computable...
-
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...