We describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's Degrees of Unsolvability have had in the development of recursion theory over the past thirty years.

This paper surveys the recent developments in the area that grew out of attempts to solve an analog of Hilbert's Tenth Problem for the field of rational numbers and the rings of integers of number fields. It is based on a plenary talk the author gave at the annual North American meeting of ASL at the University of Notre Dame in May of 2009.

We show that Diophantine equivalence of two suitably presented countable rings implies that the existential polynomial languages of the two rings have the same "expressive power" and that their Diophantine sets are in some sense the same. We also show that a Diophantine class of countable rings is contained completely within a relative enumeration class and demonstrate that one consequence of this fact is the existence of infinitely many Diophantine classes containing holomophy rings of Q.

§1. Overview. Philosophers and mathematicians have drawn lots of conclusions from Gödel's incompleteness theorems, and related results from mathematical logic. Languages, minds, and machines figure prominently in the discussion. Gödel's theorems surely tell us something about these important matters. But what?A descriptive title for this paper would be “Gödel, Lucas, Penrose, Turing, Feferman, Dummett, mechanism, optimism, reflection, and indefinite extensibility”. Adding “God and the Devil” would probably be redundant. Despite the breath-taking, whirlwind tour, I have the modest aim of forging (...) connections between different parts of this literature and clearing up some confusions, together with the less modest aim of not introducing any more confusions.I propose to focus on three spheres within the literature on incompleteness. The first, and primary, one concerns arguments that Gödel's theorem refutes the mechanistic thesis that the human mind is, or can be accurately modeled as, a digital computer or a Turing machine. The most famous instance is the much reprinted J. R. Lucas [18]. To summarize, suppose that a mechanist provides plans for a machine,M, and claims that the output ofMconsists of all and only the arithmetic truths that a human, or the totality of human mathematicians, will ever or can ever know. We assume that the output ofMis consistent. (shrink)

We compare the degrees of enumerability and the closed Medvedev degrees and find that many situations occur. There are nonzero closed degrees that do not bound nonzero degrees of enumerability, there are nonzero degrees of enumerability that do not bound nonzero closed degrees, and there are degrees that are nontrivially both degrees of enumerability and closed degrees. We also show that the compact degrees of enumerability exactly correspond to the cototal enumeration degrees.

It is well known that any finitary operation is recursive in a suitable total numeration. A. Orlicki showed that there is an ω-operation not recursive in any total numeration. We will show that any ω-operation is recursive in a partial numeration.

We consider fine hierarchies in recursion theory, descriptive set theory, logic and complexity theory. The main results state that the sets of values of different Boolean terms coincide with the levels of suitable fine hierarchies. This gives new short descriptions of these hierarchies and shows that collections of sets of values of Boolean terms are almost well ordered by inclusion. For the sake of completeness we mention also some earlier results demonstrating the usefulness of fine hierarchies.

We investigate the structure of the Medvedev lattice as a partial order. We prove that every interval in the lattice is either finite, in which case it is isomorphic to a finite Boolean algebra, or contains an antichain of size $2^{2^{\aleph }0}$ , the size of the lattice itself. We also prove that it is consistent with ZFC that the lattice has chains of size $2^{2^{\aleph }0}$ , and in fact these big chains occur in every infinite interval. We also (...) study embeddings of lattices and algebras. We show that large Boolean algebras can be embedded into the Medvedev lattice as upper semilattices, but that a Boolean algebra can be embedded as a lattice only if it is countable. Finally we discuss which of these results hold for the closely related Muchnik lattice. (shrink)

This paper is primarily concerned with ℵ 0 -categoricity of theories of partially ordered sets. It contains some general conjectures, a collection of known results and some new theorems on ℵ 0 -categoricity. Among the latter are the following. Corollary 3.3. For every countable ℵ 0 -categorical U there is a linear order of A such that $(\mathfrak{U}, is ℵ 0 -categorical. Corollary 6.7. Every ℵ 0 -categorical theory of a partially ordered set of finite width has a decidable theory. (...) Theorem 7.7. Every ℵ 0 -categorical theory of reticles has a decidable theory. There is a section dealing just with decidability of partially ordered sets, the main result of this section being. Theorem 8.2. If $(P, is a finite partially ordered set and K P is the class of partially ordered sets which do not embed $(P, , then Th(K P ) is decidable iff K P contains only reticles. (shrink)

The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined even if it is not sufficiently formal and precise to belong to mathematics proper (in a narrow sense)—and even if (as many have asserted) for that reason the Church–Turing thesis is unprovable. It is proved logically that the class of effective procedures is not decidable, i.e., that there is no effective procedure for ascertaining whether a given procedure is effective. This (...) result is proved directly from the notion itself of an effective procedure, without reliance on any (partly) mathematical lemma, conjecture, or thesis invoking recursiveness or Turing-computability. In fact, there is no reliance on anything very mathematical. The proof does not even appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of an effective procedure. Though the result that effectiveness is undecidable is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure invariably terminates with the correct verdict. (shrink)

This is a non-technical version of "The Decision Problem for Effective Procedures." The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that reason, the Church–Turing thesis (that the effectively calculable functions on natural numbers are exactly the general recursive functions), cannot be proved. However, it is logically provable from the notion of an (...) effective procedure, without reliance on any (partially) mathematical thesis or conjecture concerning effective procedures, such as the Church–Turing thesis, that the class of effective procedures is undecidable, i.e., that there is no effective procedure for ascertaining whether a given procedure is effective. The proof does not even appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of such a procedure. Though the result itself is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure is, in fact, a decision procedure, i.e., effective—for example, that it invariably terminates with the correct verdict. (shrink)

Smullyan in [Smu61] identified the recursion theoretic essence of incompleteness results such as Gödel's first incompleteness theorem and Rosser's theorem. Smullyan showed that, for sufficiently complex theories, the collection of provable formulae and the collection of refutable formulae are effectively inseparable—where formulae and their Gödel numbers are identified. This paper gives a similar treatment for proof speed-up. We say that a formal system S1is speedable over another system S0on a set of formulaeAiff, for each recursive functionh, there is a formulaαinAsuch (...) that the length of the shortest proof ofαin S0is larger thanhof the shortest proof ofαin S1. We characterize speedability in terms of the inseparability by r.e. sets of the collection of formulae which are provable in S1but unprovable in S0from the collectionA–where again formulae and their Gödel numbers are identified. We provide precise definitions of proof length, speedability and r.e. inseparability below.We follow the terminology and notation of [Rog87] with borrowings from [Soa87]. Below,ϕis an acceptable numbering of the partial recursive functions [Rog87] andΦa complexity measure associated withϕ[Blu67], [DW83]. (shrink)

The sentences employed in semantic paradoxes display a wide range of semantic behaviours. However, the main theories of truth currently available either fail to provide a theory of paradox altogether, or can only account for some paradoxical phenomena by resorting to multiple interpretations of the language. In this paper, I explore the wide range of semantic behaviours displayed by paradoxical sentences, and I develop a unified theory of truth and paradox, that is a theory of truth that also provides a (...) unified account of paradoxical sentences. The theory I propose here yields a threefold classification of paradoxical sentences – liar-like sentences, truth-teller-like sentences, and revenge sentences. Unlike existing treatments of semantic paradox, the theory put forward in this paper yields a way of interpreting all three kinds of paradoxical sentences, as well as unparadoxical sentences, within a single model. (shrink)

A well-known theorem by Martin asserts that the degrees of maximal sets are precisely the high recursively enumerable degrees, and the same is true with ‘maximal’ replaced by ‘dense simple’, ‘r-maximal’, ‘strongly hypersimple’ or ‘finitely strongly hypersimple’. Many other constructions can also be carried out in any given high r. e. degree, for instance r-maximal or hyperhypersimple sets without maximal supersets . In this paper questions of this type are considered systematically. Ultimately it is shown that every conjunction of simplicity- (...) and non-extensibility properties can be accomplished, unless it is ruled out by well-known, elementary results. Moreover, each construction can be carried out in any given high r. e. degree, as might be expected. For instance, every high r. e. degree contains a dense simple, strongly hypersimple set A which is contained neither in a hyperhypersimple nor in an r-maximal set. The paper also contains some auxiliary results, for instance: every r. e. set B can be transformed into an r. e. set A such that A has no dense simple superset, the transformation preserves simplicity- or non-extensibility properties as far as this is consistent with , and A [TRIPLE BOND]TB if B is high, and A ≥TB otherwise. Several proofs involve refinements of known constructions; relationships to earlier results are discussed in detail. (shrink)

This paper introduces the notion of cW10-creative set, which strengthens that of semicreative set in a similar way as complete creativity strengthens creativity. Two results are proven, both of which imply that not all semicreative sets are cW10-creative. First, it is shown that semicreative Dedekind cuts cannot be cW10-creative; the existence of semicreative Dedekind cuts was shown by Soare. Secondly, it is shown that if A ⊕ B, the join of A and B, is cW10-creative, then either A or B (...) is cW10-creative, and the same is not true with ‘cW10-creative’ replaced by ‘semicreative’. Moreover, sets A, B which provide a counterexample for can be constructed within any given nonrecursive r.e. T-degrees a, b. MSC: 03D30. (shrink)

Krull [4] extended Galois theory to arbitrary normal extensions, in which the Galois groups are precisely the profinite groups. Metakides and Nerode [7] produced two recursively presented algebraic extensionsK⊂Fof the rationals such thatFis abelian,Fis of infinite degree overK, and the Galois group ofFoverK, although of cardinalityc, has only one recursive element. This indicated the limits of effectiveness for Krull's theory. Nerode suggested developing a natural effective version of Krull's theory.It is evident from the classical literature that the free profinite group (...) on denumerably many generators can be obtained effectively as the Galois group of a recursive extension of the rationals over a subfield. Nerode conjectured that it could be obtained effectively as the Galois group of the algebraic numbers over a suitable subfield. The case of finitely many generators was done non-effectively by Jarden [3]. The author believes that the denumerable case, as presented in §2, is also new classically. Using this result and the effective Krull theory, every “co-recursively enumerable” profinite group is effectively the Galois group of a recursively enumerable field of algebraic numbers over a recursive subfield. (shrink)

The modern theory of computability is based on the works of Church, Markov and Turing who, starting from quite different models of computation, arrived at the same class of computable functions. The purpose of this paper is the show how the main results of the Church-Markov-Turing theory of computable functions may quickly be derived and understood without recourse to the largely irrelevant theories of recursive functions, Markov algorithms, or Turing machines. We do this by ignoring the problem of what constitutes (...) a computable function and concentrating on the central feature of the Church-Markov-Turing theory: that the set of computable partial functions can be effectively enumerated. In this manner we are led directly to the heart of the theory of computability without having to fuss about what a computable function is.The spirit of this approach is similar to that of [RGRS]. A major difference is that we operate in the context of constructive mathematics in the sense of Bishop [BSH1], so all functions are computable by definition, and the phrase “you can find” implies “by a finite calculation.” In particular ifPis some property, then the statement “for eachmthere isnsuch thatP” means that we can construct a functionθsuch thatP)for allm. Church's thesis has a different flavor in an environment like this where the notion of a computable function is primitive.One point of such a treatment of Church's thesis is to make available to Bishopstyle constructivists the Markovian counterexamples of Russian constructivism and recursive function theory. The lack of serious candidates for computable functions other than recursive functions makes it quite implausible that a Bishopstyle constructivist could refute Church's thesis, or any consequence of Church's thesis. Hence counterexamples such as Specker's bounded increasing sequence of rational numbers that is eventually bounded away from any given real number [SPEC] may be used, as Brouwerian counterexamples are, as evidence of the unprovability of certain assertions. (shrink)

Let $V_\propto$ be a fixed, fully effective, infinite dimensional vector space. Let $\mathscr{L}(V_\propto)$ be the lattice consisting of the recursively enumerable (r.e.) subspaces of $V_\propto$ , under the operations of intersection and weak sum (see § 1 for precise definitions). In this article we examine the algebraic properties of $\mathscr{L}(V_\propto)$ . Early research on recursively enumerable algebraic structures was done by Rabin [14], Frolich and Shepherdson [5], Dekker [3], Hamilton [7], and Guhl [6]. Our results are based upon the more (...) recent work concerning vector spaces of Metakides and Nerode [12], Crossley and Nerode [2], Remmel [15], [16], and Kalantari [8]. In the main theorem below, we extend a result of Lachlan from the lattice E of r.e. sets to $\mathscr{L}(V_\propto)$ . We define hyperhypersimple vector spaces, discuss some of their properties and show if $A, B \in \mathscr{L}(V_\propto)$ , and A is a hyperhypersimple subspace of B then there is a recursive space C such that A + C = B. It will be proven that if $V \in \mathscr{L}(V_\propto)$ and the lattice of superspaces of V is a complemented modular lattice then V is hyperhypersimple. The final section contains a summary of related results concerning maximality and simplicity. (shrink)