This book presents new results in computability theory, a branch of mathematical logic and computer science that has become increasingly relevant in recent years. The field's connections with disparate areas of mathematical logic and mathematics more generally have grown deeper, and now have a variety of applications in topology, group theory, and other subfields. This monograph establishes new directions in the field, blending classic results with modern research areas such as algorithmic randomness. The significance of the book lies not only (...) in the depth of the results contained therein, but also in the fact that the notions the authors introduce allow them to unify results from several subfields of computability theory. (shrink)

Turing progressions have been often used to measure the proof-theoretic strength of mathematical theories: iterate adding consistency of some weak base theory until you “hit” the target theory. Turing progressions based on n-consistency give rise to a \ proof-theoretic ordinal \ also denoted \. As such, to each theory U we can assign the sequence of corresponding \ ordinals \. We call this sequence a Turing-Taylor expansion or spectrum of a theory. In this paper, we relate (...) class='Hi'>Turing-Taylor expansions of sub-theories of Peano Arithmetic to Ignatiev’s universal model for the closed fragment of the polymodal provability logic \. In particular, we observe that each point in the Ignatiev model can be seen as Turing-Taylor expansions of formal mathematical theories. Moreover, each sub-theory of Peano Arithmetic that allows for a Turing-Taylor expansion will define a unique point in Ignatiev’s model. (shrink)

The Turing Test (TT), as originally specified, centres on theability to perform a social role. The TT can be seen as a test of anability to enter into normal human social dynamics. In this light itseems unlikely that such an entity can be wholly designed in an off-line mode; rather a considerable period of training insitu would be required. The argument that since we can pass the TT,and our cognitive processes might be implemented as a Turing Machine(TM), that (...) consequently a TM that could pass the TT could be built, isattacked on the grounds that not all TMs are constructible in a plannedway. This observation points towards the importance of developmentalprocesses that use random elements (e.g., evolution), but in these casesit becomes problematic to call the result artificial. This hasimplications for the means by which intelligent agents could bedeveloped. (shrink)

We define the notion of ordinal computability by generalizing standard Turing computability on tapes of length ω to computations on tapes of arbitrary ordinal length. We show that a set of ordinals is ordinal computable from a finite set of ordinal parameters if and only if it is an element of Gödel's constructible universe L. This characterization can be used to prove the generalized continuum hypothesis in L.

In [3], two different effective versions of Borel embedding are defined. The first, called computable embedding, is based on uniform enumeration reducibility, while the second, called Turing computable embedding, is based on uniform Turing reducibility. While [3] focused mainly on computable embeddings, the present paper considers Turing computable embeddings. Although the two notions are not equivalent, we can show that they behave alike on the mathematically interesting classes chosen for investigation in [3]. We give a “Pull-back Theorem”, (...) saying that if Φ is a Turing computable embedding of K into K’, then for any computable infinitary sentence φ in the language of K’, we can find a computable infinitary sentence φ* in the language of K such that for all. (shrink)

This paper continues our study of computable point-free topological spaces and the metamathematical points in them. For us, a point is the intersection of a sequence of basic open sets with compact and nested closures. We call such a sequence a sharp filter. A function fF from points to points is generated by a function F from basic open sets to basic open sets such that sharp filters map to sharp filters. We restrict our study to functions that have at (...) least all computable points in their domains.We follow Turing's approach in stating that a point is computable if it is the limit of a computable sharp filter; we then define the Turing degree Deg of a general point x in an analogous way. Because of the vagaries of the definition, a result of J. Miller applies and we note that not all points in all our spaces have Turing degrees; but we also show a certain class of points do. We further show that in ℝn all points have Turing degrees and that these degrees are the same as the classical Turing degrees of points defined by other researchers.We also prove the following: For a point x that has a Turing degree and lies either on a computable tree T or in the domain of a computable function fF, there is a sharp filter on T or in dom converging to x and with the same Turing degree as x. Furthermore, all possible Turing degrees occur among the degrees of such points for a given computable function fF or a complete, computable, binary tree T. For each x ∈ dom for which x and fF have Turing degrees, Deg) ≤ Deg. Finally, the Turing degrees of the sharp filters convergent to a given x are closed upward in the partial order of all Turing degrees. (shrink)

A model is computable if its domain is a computable set and its relations and functions are uniformly computable. Let be a computable model and let R be an extra relation on the domain of . That is, R is not named in the language of . We define to be the set of Turing degrees of the images f under all isomorphisms f from to computable models. We investigate conditions on and R which are sufficient and necessary for (...) to contain every Turing degree. These conditions imply that if every Turing degree 0″ can be realized in via an isomorphism of the same Turing degree as its image of R, then contains every Turing degree. We also discuss an example of and R whose coincides with the Turing degrees which are 0′. (shrink)

What is the relation between intelligence and computation? Although the difficulty of defining `intelligence' is widely recognized, many are unaware that it is hard to give a satisfactory definition of `computational' if computation is supposed to provide a non-circular explanation for intelligent abilities. The only well-defined notion of `computation' is what can be generated by a Turing machine or a formally equivalent mechanism. This is not adequate for the key role in explaining the nature of mental processes, because it (...) is too general, as many computations involve nothing mental, nor even processes: they are simply abstract structures. We need to combine the notion of `computation' with that of `machine'. This may still be too restrictive, if some non-computational mechanisms prove to be useful for intelligence. We need a theory-based taxonomy of {\em architectures} and {\em mechanisms} and corresponding process types. Computational machines my turn out to be a sub-class of the machines available for implementing intelligent agents. The more general analysis starts with the notion of a system with independently variable, causally interacting sub-states that have different causal roles, including both `belief-like' and `desire-like' sub-states, and many others. There are many significantly different such architectures. For certain architectures (including simple computers), some sub-states have a semantic interpretation for the system. The relevant concept of semantics is defined partly in terms of a kind of Tarski-like structural correspondence (not to be confused with isomorphism). This always leaves some semantic indeterminacy, which can be reduced by causal loops involving the environment. But the causal links are complex, can share causal pathways, and always leave mental states to some extent semantically indeterminate. (shrink)

We describe an emerging field, that of nonclassical computability and nonclassical computing machinery. According to the nonclassicist, the set of well-defined computations is not exhausted by the computations that can be carried out by a Turing machine. We provide an overview of the field and a philosophical defence of its foundations.

A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields (...) that the realization of hypercomputing devices is implausible, and that Thesis P is not essentially different from the standard Church-Turing Thesis. (shrink)

Let be an infinite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on , first introduced and studied by Hird, is analogous to the computability-theoretic notion of hypersimplicity of R on A, given the definability of certain effective sequences of relations on A. Assuming that R is formally hypersimple on , we give general sufficient conditions for the existence of a computable isomorphic copy of on whose (...) domain the image of R is hypersimple and of arbitrary nonzero computably enumerable Turing degree. (shrink)

The main factor of intelligence is defined as the ability tocomprehend, formalising this ability with the help of new constructsbased on descriptional complexity. The result is a comprehension test,or C- test, which is exclusively defined in computational terms. Due toits absolute and non-anthropomorphic character, it is equally applicableto both humans and non-humans. Moreover, it correlates with classicalpsychometric tests, thus establishing the first firm connection betweeninformation theoretical notions and traditional IQ tests. The TuringTest is compared with the C- test and the (...) combination of the two isquestioned. In consequence, the idea of using the Turing Test as apractical test of intelligence should be surpassed, and substituted bycomputational and factorial tests of different cognitive abilities, amuch more useful approach for artificial intelligence progress and formany other intriguing questions that present themselves beyond theTuring Test. (shrink)

We define the bounded jump of $A$ by $A^{b}=\{x\in \omega \mid \exists i\leq x[\varphi_{i}\downarrow \wedge\Phi_{x}^{A\upharpoonright \!\!\!\upharpoonright \varphi_{i}}\downarrow ]\}$ and let $A^{nb}$ denote the $n$th bounded jump. We demonstrate several properties of the bounded jump, including the fact that it is strictly increasing and order-preserving on the bounded Turing degrees. We show that the bounded jump is related to the Ershov hierarchy. Indeed, for $n\geq2$ we have $X\leq_{bT}\emptyset ^{nb}\iff X$ is $\omega^{n}$-c.e. $\iff X\leq_{1}\emptyset ^{nb}$, extending the classical result that $X\leq_{bT}\emptyset (...) '\iff X$ is $\omega$-c.e. Finally, we prove that the analogue of Shoenfield inversion holds for the bounded jump on the bounded Turing degrees. That is, for every $X$ such that $\emptyset ^{b}\leq_{bT}X\leq_{bT}\emptyset ^{2b}$, there is a $Y\leq_{bT}\emptyset ^{b}$ such that $Y^{b}\equiv_{bT}X$. (shrink)

For [Formula: see text], the coarse similarity class of A, denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes (...) under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form [Formula: see text] where [Formula: see text] is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of [Formula: see text]. We then define a distance between Turing degrees based on Hausdorff distance in the metric space [Formula: see text]. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, [Formula: see text], and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance [Formula: see text] from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability. Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic. Finally, we study the completeness of [Formula: see text] from the perspectives of computability theory and reverse mathematics. (shrink)

This paper aims to show that dominant conceptions of intelligence used in artificial intelligence (AI) are biased by normative assumptions that originate from the Global North, making it questionable if AI can be uncritically applied elsewhere without risking serious harm to vulnerable people. After the introduction in Sect. 1 we shortly present the history of IQ testing in Sect. 2, focusing on its multiple discriminatory biases. To determine how these biases came into existence, we define intelligence ontologically and underline its (...) constructed and culturally variable character. Turning to AI, specifically the Turing Test (TT), in Sect. 3, we critically examine its underlying intelligence conceptions. The test has been of central influence in AI research and remains an important point of orientation. We argue that both the test itself and how it is used in practice risk promoting a limited conception of intelligence which solely originated in the Global North. Hence, this conception should be critically assessed in relation to the different global contexts in which AI technologies are and will be used. In Sect. 4, we highlight how unequal power relations in AI research are a real threat, rather than just philosophical sophistry while considering the history of IQ testing and the TT’s practical biases. In the last section, we examine the limits of our account and identify fields for further investigation. Tracing colonial continuities in AI intelligence research, this paper points to a more diverse and historically aware approach to the design, development, and use of AI. (shrink)

I propose to consider the question, "Can machines think?" This should begin with definitions of the meaning of the terms "machine" and "think." The definitions might be framed so as to reflect so far as possible the normal use of the words, but this attitude is dangerous, If the meaning of the words "machine" and "think" are to be found by examining how they are commonly used it is difficult to escape the conclusion that the meaning and the answer to (...) the question, "Can machines think?" is to be sought in a statistical survey such as a Gallup poll. But this is absurd. Instead of attempting such a definition I shall replace the question by another, which is closely related to it and is expressed in relatively unambiguous words. The new form of the problem can be described in terms of a game which we call the 'imitation game." It is played with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The interrogator stays in a room apart front the other two. The object of the game for the interrogator is to determine which of the other two is the man and which is the woman. He knows them by labels X and Y, and at the end of the game he says either "X is A and Y is B" or "X is B and Y is A." The interrogator is allowed to put questions to A and B. We now ask the question, "What will happen when a machine takes the part of A in this game?" Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman? These questions replace our original, "Can machines think?". (shrink)

Infinite time Turing machines represent a model of computability that extends the operations of Turing machines to transfinite ordinal time by defining the content of each cell at limit steps to be the lim sup of the sequences of previous contents of that cell. In this paper, we study a computational model obtained by replacing the lim sup rule with an ‘eventually constant’ rule: at each limit step, the value of each cell is defined if and only if (...) the content of that cell has stabilized before that limit step and is then equal to this constant value. We call these machines weak infinite time Turing machines. We study different variants of wITTMs adding multiple tapes, heads, or bidimensional tapes. We show that some of these models are equivalent to each other concerning their computational strength. We show that wITTMs decide exactly the arithmetic relations on natural numbers. (shrink)

We consider questions related to the rigidity of the structure R, the PTIME-Turing degrees of recursive sets of strings together with PTIME-Turing reducibility, pT, and related structures; do these structures have nontrivial automorphisms? We prove that there is a nontrivial automorphism of an ideal of R. This can be rephrased in terms of partial relativizations. We consider the sets which are PTIME-Turing computable from a set A, and call this class PTIMEA. Our result can be stated as (...) follows: There is an oracle, A, relative to which the PTIME-Turing degrees are not rigid . Furthermore, the automorphism can be made to preserve the complexity classes DTIMEA for all k 1, or to move any DTIMEA for n 2. From the existence of such an automorphism we conclude as a corollary that there is an oracle A relative to which the classes DTIME are not definable over R. We carry out the corresponding partial relativization for the many-one degrees to construct an oracle, A, relative to which the PTIMA-many-one degrees relative to A have a nontrivial automorphism, and one relative to which the lattice of sets in PTIMEA under inclusion have a nontrivial automorphism. The proof is phrased as a forcing argument; we construct the set A to meet a particular collection of dense sets in our notion of forcing. Roughly, the dense sets will guarantee that if A meets these sets and we split A into two pieces, A0 and A1, in a simple way, and then switching the roles of A0 and A1 in all computations from A will produce an automorphism of the ideal of PTIMA-degrees below A. We force A0 and A1 to have different PTIME-Turing degree; this will then make the automorphism nontrivial. An appropriately generic set A is constructed using a priority argument. (shrink)

This paper argues that the Turing test is based on a fixed and de-contextualized view of communicative competence. According to this view, a machine that passes the test will be able to communicate effectively in a variety of other situations. But the de-contextualized view ignores the relationship between language and social context, or, to put it another way, the extent to which speakers respond dynamically to variations in discourse function, formality level, social distance/solidarity among participants, and participants' relative degrees (...) of power and status. In the case of the Loebner Contest, a present day version of the Turing test, the social context of interaction can be interpreted in conflicting ways. For example, Loebner discourse is defined 1) as a friendly, casual conversation between two strangers of equal power, and 2) as a one-way transaction in which judges control the conversational floor in an attempt to expose contestants that are not human. This conflict in discourse function is irrelevant so long as the goal of the contest is to ensure that only thinking, human entities pass the test. But if the function of Loebner discourse is to encourage the production of software that can pass for human on the level of conversational ability, then the contest designers need to resolve this ambiguity in discourse function, and thus also come to terms with the kind of competence they are trying to measure. (shrink)

We consider implicit definability over the natural number system $\mathbb{N},+,\times,=$. We present a new proof of two theorems of Leo Harrington. The first theorem says that there exist implicitly definable subsets of $\mathbb{N}$ which are not explicitly definable from each other. The second theorem says that there exists a subset of $\mathbb{N}$ which is not implicitly definable but belongs to a countable, explicitly definable set of subsets of $\mathbb{N}$. Previous proofs of these theorems have used finite- (...) or infinite-injury priority constructions. Our new proof is easier in that it uses only a nonpriority oracle construction, adapted from the standard proof of the Friedberg jump theorem. (shrink)

We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to relative computability (Turing reducibility).

We show that there are Π5 formulas in the language of the Turing degrees, [Formula: see text], with ≤, ∨ and ∧, that define the relations x″ ≤ y″, x″ = y″ and so {x ∈ L2 = x ≥ y|x″ = y″} in any jump ideal containing 0. There are also Σ6&Π6 and Π8 formulas that define the relations w = x″ and w = x', respectively, in any such ideal [Formula: see text]. In the language with just (...) ≤ the quantifier complexity of each of these definitions increases by one. For a lower bound on definability, we show that no Π2 or Σ2 formula in the language with just ≤ defines L2 or L2. Our arguments and constructions are purely degree theoretic without any appeals to absoluteness considerations, set theoretic methods or coding of models of arithmetic. As a corollary, we see that every automorphism of [Formula: see text] is fixed on every degree above 0″ and every relation on [Formula: see text] which is invariant under the double jump or under join with 0″ is definable over [Formula: see text] if and only if it is definable in second order arithmetic with set quantification ranging over sets whose degrees are in [Formula: see text]. (shrink)

What would it take for an artificial agent to be treated as having moral value? As a first step toward answering this question, we ask what it would take for an artificial agent to be capable of the sort of autonomous, adaptive social behavior that is characteristic of the animals that humans interact with. We propose that this sort of capacity is best measured by what we call the Embodied Turing Test. The Embodied Turing test is a test (...) in which intelligence is operationally defined in terms of autonomous, adaptive interaction with the environment and with other animals. Three versions of the Embodied Turing test were performed with a SONY AIBO robot. Human participants were asked to differentiate between AIBO in a human-controlled mode and AIBO in a software-controlled mode. Our results indicate that the human participants were guessing at how AIBO was controlled. Our data reveals that people do not have enough experience with robots to accurately evaluate its behavior. This indicates that today’s humans do not have enough experience with artificial agents to treat them as morally valuable. (shrink)

TheK-trivial sets form an ideal in the Turing degrees, which is generated by its computably enumerable members and has an exact pair below the degree of the halting problem. The question of whether it has an exact pair in the c.e. degrees was first raised in [22, Question 4.2] and later in [25, Problem 5.5.8].We give a negative answer to this question. In fact, we show the following stronger statement in the c.e. degrees. There exists aK-trivial degreedsuch that for (...) all degreesa, bwhich are notK-trivial anda > d, b > dthere exists a degreevwhich is notK-trivial anda > v, b > v. This work sheds light to the question of the definability of theK-trivial degrees in the c.e. degrees. (shrink)

We investigate computability theoretic and topological properties of spaces of orders on computable orderable groups. A left order on a group G is a linear order of the domain of G, which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. In particular, we study groups for which the spaces of left orders are homeomorphic to the Cantor set, and their Turing degree spectra contain certain upper cones of degrees. Our approach unifies and extends Sikora’s (...) [28] investigation of orders on groups in topology and Solomon’s [31] investigation of these orders in computable algebra. Furthermore, we establish that a computable free group Fn of rank n>1 has a bi-order in every Turing degree. (shrink)

In [7], open questions are raised regarding the computational strengths of so-called ∞-α -Turing machines, a family of models of computation resembling the infinite-time Turing machine model of [2], except with α -length tape . Let TαTα denote the machine model of tape length α . Define that TαTα is computationally stronger than TβTβ precisely when TαTα can compute all TβTβ-computable functions ƒ: min2→min2 plus more. The following results are found: Tω1≻TωTω1≻Tω. There are countable ordinals α such that (...) Tα≻TωTα≻Tω, the smallest of which is precisely γ , the supremum of ordinals clockable by TωTω. In fact, there is a hierarchy of countable TαTαs of increasing strength corresponding to the transfinite Turing-jump operator ▼. There is a countable ordinal μ such that neither Tμ⪰Tω1Tμ⪰Tω1 nor Tμ⪯Tω1Tμ⪯Tω1—that is, the models TμTμ and Tω1Tω1 are computation-strength incommensurable . A similar fact holds for any larger uncountable device replacing Tω1Tω1. Further observations are made about countable TαTα. (shrink)

Turing’s paper on computable numbers has played its role in underpinning different perspectives on the world of information. On the one hand, it encourages a digital ontology, with a perceived flatness of computational structure comprehensively hosting causality at the physical level and beyond. On the other, it can give an insight into the way in which higher order information arises and leads to loss of computational control—while demonstrating how the control can be re-established, in special circumstances, via suitable type (...) reductions. We examine the classical computational framework more closely than is usual, drawing out lessons for the wider application of information–theoretical approaches to characterizing the real world. The problem which arises across a range of contexts is the characterizing of the balance of power between the complexity of informational structure and the means available to bring this information back into the computational fold. We proceed via appropriate mathematical modelling to a more coherent view of the computational structure of information, relevant to a wide spectrum of areas of investigation. (shrink)

We carry out a study of definability issues in the standard models of Presburger and Skolem arithmetics (henceforth referred to simply as Presburger and Skolem arithmetics, for short, because we only deal with these models, not the theories, thus there is no risk of confusion) supplied with free unary predicates—which are strongly related to definability in the monadic SOA (second-order arithmetic) without × or + , respectively. As a consequence, we obtain a very direct proof for ${\Pi^1_1}$ -completeness of Presburger, (...) and also Skolem, arithmetic with a free unary predicate, generalize it to all ${\Pi^1_n}$ -levels, and give an alternative description of the analytical hierarchy without × or + . Here ‘direct’ means that one explicitly m-reduces the truth of ${\Pi^1_1}$ -formulae in SOA to the truth in the extended structures. Notice that for the case of Presburger arithmetic, the ${\Pi^1_1}$ -completeness was already known, but the proof was indirect and exploited some special ${\Pi^1_1}$ -completeness results on so-called recurrent nondeterministic Turing machines—for these reasons, it was hardly able to shed any light on definability issues or possible generalizations. (shrink)

§1. Introduction. Natural sets that can be enumerated by a computable function always seem to be either actually computable or of the same complexity as the Halting Problem, the complete r.e. set K. The obvious question, first posed in Post [1944] and since then called Post's Problem is then just whether there are r.e. sets which are neither computable nor complete, i.e., neither recursive nor of the same Turing degree as K?Let be the r.e. degrees, i.e., the r.e. sets (...) modulo the equivalence relation of equicomputable with the partial order induced by Turing computability. This structure is a partial order with least element 0, the degree of the computable sets, and greatest element 1 or 0′, the degree of K. Post's problem then asks if there are any other elements of.The solution of Post's problem by Friedberg [1957] and Muchnik [1956] was followed by various algebraic or order theoretic results that were interpreted as saying that the structure was in some way well behaved:Theorem 1.1. Every countable partial ordering or even uppersemilattice can be embedded into.Theorem 1.2. For every nonrecursive r.e. degreeathere are r.e. degreesb, c < asuch thatb ∨ c = a.Theorem 1.3. For every pair of nonrecursive r.e. degreesa < bthere is an r.e. degreecsuch thata < c < b. (shrink)

Kripke (1982, Wittgenstein on rules and private language. Cambridge, MA: MIT Press) presents a rule-following paradox in terms of what we meant by our past use of “plus”, but the same paradox can be applied to any other term in natural language. Many responses to the paradox concentrate on fixing determinate meaning for “plus”, or for a small class of other natural language terms. This raises a problem: how can these particular responses be generalised to the whole of natural language? (...) In this paper, I propose a solution. I argue that if natural language is computable in a sense defined below, and the Church–Turing thesis is accepted, then this auxiliary problem can be solved. (shrink)

We show that the double jump is definable in the computably enumerable sets. Our main result is as follows: let [Formula: see text] is the Turing degree of a [Formula: see text] set J ≥T0″}. Let [Formula: see text] such that [Formula: see text] is upward closed in [Formula: see text]. Then there is an ℒ property [Formula: see text] such that [Formula: see text] if and only if there is an A where A ≡T F and [Formula: (...) see text]. A corollary of this is that, for all n ≥ 2, the high n computably enumerable degrees are invariant in the computably enumerable sets. Our work resolves Martin's Invariance Conjecture. (shrink)

Where $\underline{a}$ is a Turing degree and ξ is an ordinal $ , the result of performing ξ jumps on $\underline{a},\underline{a}^{(\xi)}$ , is defined set-theoretically, using Jensen's fine-structure results. This operation appears to be the natural extension through $(\aleph_1)^{L^\underline{a}}$ of the ordinary jump operations. We describe this operation in more degree-theoretic terms, examine how much of it could be defined in degree-theoretic terms and compare it to the single jump operation.

We show that the lattice L 20 is not embeddable into the lattice of ideals of computably enumerable Turing degrees (J). We define a structure called a pseudolattice that generalizes the notion of a lattice, and show that there is a Π 2 necessary and sufficient condition for embedding a finite pseudolattice into J.

Though less well known than his other work, Turings 1938 Princeton Thesis, this title which includes his notion of an oracle machine, has had a lasting influence on computer science and mathematics. It presents a facsimile of the original typescript of the thesis along with essays by Appel and Feferman that explain its still-unfolding significance.

In this paper, I explore an intriguing view of definable numbers proposed by a Cambridge mathematician Ernest Hobson, and his solution to the paradoxes of definability. Reflecting on König’s paradox and Richard’s paradox, Hobson argues that an unacceptable consequence of the paradoxes of definability is that there are numbers that are inherently incapable of finite definition. Contrast to other interpreters, Hobson analyses the problem of the paradoxes of definability lies in a dichotomy between finitely definable numbers and not (...) finitely definable numbers. To bypass this predicament, Hobson proposes a language dependent analysis of definable numbers, where the diagonal argument is employed as a means to generate more and more definable numbers. This paper examines Hobson’s work in its historical context, and articulates his argument in detail. It concludes with a remark on Hobson’s analysis of definability and Alan Turing’s analysis of computability. (shrink)