Martin’s Axiom and embeddings of upper semi-lattices into the Turing degrees

It is shown that every locally countable upper semi-lattice of cardinality the continuum can be embedded into the Turing degrees, assuming Martin’s Axiom.     

Spaces of orders and their Turing degree spectra

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 (2004) [28] investigation of orders on groups in topology and Solomon’s (2002) [31] investigation of these orders in computable algebra. Furthermore, we establish that a computable free group F_n of rank n>1 has a bi-order in every Turing degree.     

Turing cones and set theory of the reals

We investigate Turing cones as sets of reals, and look at the relationship between Turing cones, measures, Baire category and special sets of reals, using these methods to show that Martin's proof of Turing Determinacy (every determined Turing closed set contains a Turing cone or is disjoint from one) does not work when you replace “determined” with “Blackwell determined”. This answers a question of Tony Martin. Received: 6 December 1999 / Revised version: 28 June 2000 Published online: 3 October 2001     

The computable Lipschitz degrees of computably enumerable sets are not dense

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) [2]), however the problem for the computable Lipschitz degrees is more complex.     

Low upper bounds in the LR degrees

We say that A≤_LRB if every B-random real is A-random—in other words, if B has at least as much derandomization power as A. The LR reducibility is a natural weak reducibility in the context of randomness, and generalizes lowness for randomness. We study the existence and properties of upper bounds in the context of the LR degrees. In particular, we show that given two (or even finitely many) low sets, there is a low c.e. set which lies LR above both. This is very different from the situation in the Turing degrees, where Sacks’ splitting theorem shows that two low sets can join to 0^′.     

The ω-Turing degrees

In this paper we initiate the study of the ω-Turing reducibility between sequences of sets of natural numbers. We shall prove that the induced degree structure is an extension of the structure of the Turing degrees and that the two structures are closely connected, but different enough. Further we shall prove some definability results for the local theory of the newly defined structure.     

Post’s Problem for ordinal register machines: An explicit approach

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.     

A measure-theoretic proof of Turing incomparability

We prove that if S is an ω-model of weak weak König’s lemma and , is incomputable, then there exists , such that A and B are Turing incomparable. This extends a recent result of Ku?era and Slaman who proved that if S₀ is a Scott set (i.e. an ω-model of weak König’s lemma) and A∈S₀, A⊆ω, is incomputable, then there exists B∈S₀, B⊆ω, such that A and B are Turing incomparable.     

Electricity swing option pricing by stochastic bilevel optimization: A survey and new approaches

We demonstrate how the problem of determining the ask price for electricity swing options can be considered as a stochastic bilevel program with asymmetric information. Unlike as for financial options, there is no way for basing the pricing method on no-arbitrage arguments. Two main situations are analyzed: if the seller has strong market power he/she might be able to maximize his/her utility, while in fully competitive situations he/she will just look for a price which makes profit and has acceptable risk. In both cases the seller has to consider the decision problem of a potential buyer – the valuation problem of determining a fair value for a specific option contract – and anticipate the buyer’s optimal reaction to any proposed strike price. We also discuss some methods for finding numerical solutions of stochastic bilevel problems with a special emphasis on using duality gap penalizations.     

Truth‐table Schnorr randomness and truth‐table reducible randomness

Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth‐table Schnorr randomness (defined in 6 too only by martingales) and truth‐table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth‐table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth‐table Schnorr randomness. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Computable analogs of cardinal characteristics: Prediction and rearrangement

There has recently been work by multiple groups in extracting the properties associated with cardinal invariants of the continuum and translating these properties into similar analogous combinatorial properties of computational oracles. Each property yields a highness notion in the Turing degrees. In this paper we study the highness notions that result from the translation of the evasion number and its dual, the prediction number, as well as two versions of the rearrangement number. When translated appropriately, these yield four new highness notions. We will define these new notions, show some of their basic properties and place them in the computability-theoretic version of Cichoń's diagram.     

The distribution of ITRM-recognizable reals

Infinite Time Register Machines (ITRM's) are a well-established machine model for infinitary computations. Their computational strength relative to oracles is understood, see e.g. ,  and . We consider the notion of recognizability, which was first formulated for Infinite Time Turing Machines in [6] and applied to ITRM's in [3]. A real x is ITRM-recognizable iff there is an ITRM-program P   such that P^y$P^y$ stops with output 1 iff y=x$y=x$, and otherwise stops with output 0. In [3], it is shown that the recognizable reals are not contained in the ITRM-computable reals. Here, we investigate in detail how the ITRM  -recognizable reals are distributed along the canonical well-ordering _<L${<}_L$ of Gödel's constructible hierarchy L  . In particular, we prove that the recognizable reals have gaps in _<L${<}_L$, that there is no universal ITRM in terms of recognizability and consider a relativized notion of recognizability.     

Generics for computable Mathias forcing

We study the complexity of generic reals for computable Mathias forcing in the context of computability theory. The n-generics and weak n-generics form a strict hierarchy under Turing reducibility, as in the case of Cohen forcing. We analyze the complexity of the Mathias forcing relation, and show that if G is any n  -generic with n≥2$n\ge 2$ then it satisfies the jump property G⁽ⁿ⁻¹⁾_≡TG^′⊕∅⁽ⁿ⁾$G^{(n-1)}{\equiv }_T{G}^{\prime }\oplus {\varnothing }^{(n)}$. We prove that every such G has generalized high Turing degree, and so cannot have even Cohen 1-generic degree. On the other hand, we show that every Mathias n-generic real computes a Cohen n-generic real.     

God, king, and geometry: revisiting the introduction to Cauchy’s Cours d’analyse

This article offers a systematic reading of the introduction to Augustin-Louis Cauchy’s landmark 1821 mathematical textbook, the Cours d’analyse. Despite its emblematic status in the history of mathematical analysis and, indeed, of modern mathematics as a whole, Cauchy’s introduction has been more a source for suggestive quotations than an object of study in its own right. Cauchy’s short mathematical metatext offers a rich snapshot of a scholarly paradigm in transition. A close reading of Cauchy’s writing reveals the complex modalities of the author’s epistemic positioning, particularly with respect to the geometric study of quantities in space, as he struggles to refound the discipline on which he has staked his young career.     

Wang’s B machines are efficiently universal,as is Hasenjaeger’s small universal electromechanical toy

In the 1960s Gisbert Hasenjaeger built Turing Machines from electromechanical relays and uniselectors. Recently, Glaschick reverse engineered the program of one of these machines and found that it is a universal Turing machine. In fact, its program uses only four states and two symbols, making it a very small universal Turing machine. (The machine has three tapes and a number of other features that are important to keep in mind when comparing it to other small universal machines.) Hasenjaeger’s machine simulates Hao Wang’s B machines, which were proved universal by Wang. Unfortunately, Wang’s original simulation algorithm suffers from an exponential slowdown when simulating Turing machines. Hence, via this simulation, Hasenjaeger’s machine also has an exponential slowdown when simulating Turing machines. In this work, we give a new efficient simulation algorithm for Wang’s B machines by showing that they simulate Turing machines with only a polynomial slowdown. As a second result, we find that Hasenjaeger’s machine also efficiently simulates Turing machines in polynomial time. Thus, Hasenjaeger’s machine is both small and fast. In another application of our result, we show that Hooper’s small universal Turing machine simulates Turing machines in polynomial time, an exponential improvement.     

Turing oracle machines, online computing, and three displacements in computability theory

We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines (a-machines). To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine (o-machine) and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form.A number of topics arose from Turing functionals including continuous functionals on Cantor space and online computations. Almost all the results in theoretical computability use relative reducibility and o-machines rather than a-machines and most computing processes in the real world are potentially online or interactive. Therefore, we argue that Turing o-machines, relative computability, and online computing are the most important concepts in the subject, more so than Turing a-machines and standard computable functions since they are special cases of the former and are presented first only for pedagogical clarity to beginning students. At the end in §10–§13 we consider three displacements in computability theory, and the historical reasons they occurred. Several brief conclusions are drawn in §14.     

A blow-up criterion for 3D Boussinesq equations in Besov spaces

In this paper, we consider the 3D Boussinesq equations with the incompressibility condition. We obtain a regularity condition for the three-dimensional Boussinesq equations by means of the Littlewood-Paley theory and Bony’s paradifferential calculus.