Explore the vast range of titles available.

We demonstrate that the Weihrauch lattice can be used to classify the uniform computational content of computability-theoretic properties as well as the computational content of theorems in one common setting. The properties that we study include diagonal non-computability, hyperimmunity, complete consistent extensions of Peano arithmetic, 1-genericity, Martin-Löf randomness, and cohesiveness. The theorems that we include in our case study are the low basis theorem of Jockusch and Soare, the Kleene-Post theorem, and Friedberg’s jump inversion theorem. It turns out that all the aforementioned properties and many theorems in computability theory, including all theorems that claim the existence of some Turing degree, have very little uniform computational content: they are located outside of the upper cone of binary choice (also known as LLPO); we call problems with this property indiscriminative . Since practically all theorems from classical analysis whose computational content has been classified are discriminative, our observation could yield an explanation for why theorems and results in computability theory typically have very few direct consequences in other disciplines such as analysis. A notable exception in our case study is the low basis theorem which is discriminative. This is perhaps why it is considered to be one of the most applicable theorems in computability theory. In some cases a bridge between the indiscriminative world and the discriminative world of classical mathematics can be established via a suitable residual operation and we demonstrate this in the case of the cohesiveness problem and the problem of consistent complete extensions of Peano arithmetic. Both turn out to be the quotient of two discriminative problems.

Generalizing the notion of automatic complexity of individual words due to Shallit and Wang, we define the automatic complexity A ( E ) of an equivalence relation E on a finite set S of words. We prove that the problem of determining whether A ( E ) equals the number | E | of equivalence classes of E is NP -complete. The problem of determining whether A ( E ) = | E | + k for a fixed k ≥ 1 is complete for the second level of the Boolean hierarchy for NP , i.e., BH 2 -complete. Let L be the language consisting of all words of maximal nondeterministic automatic complexity. We characterize the complexity of infinite subsets of L by showing that they can be co-context-free but not context-free, i.e., L is CFL -immune, but not coCFL -immune. We show that for each ε > 0, L ε ∉ coCFL , where L ε is the set of all words whose deterministic automatic complexity A ( x ) satisfies A ( x ) ≥ | x | 1/2− ε .

In this paper we derive several results which generalise the constructive dimension of (sets of) infinite strings to the case of exact dimension. We start with proving a martingale characterisation of exact Hausdorff dimension. Then using semi-computable super-martingales we introduce the notion of exact constructive dimension of (sets of) infinite strings. This allows us to derive several bounds on the complexity functions of infinite strings, that is, functions assigning to every finite prefix its Kolmogorov complexity. In particular, it is shown that the exact Hausdorff dimension of a set of infinite strings lower bounds the maximum complexity function of strings in this set. Furthermore, we show a result bounding the exact Hausdorff dimension of a set of strings having a certain computable complexity function as upper bound. Obviously, the Hausdorff dimension of a set of strings alone without any computability constraints cannot yield upper bounds on the complexity of strings in the set. If we require, however, the set of strings to be Σ 2 -definable several results upper bounding the complexity by the exact Hausdorff dimension hold true. First we prove that for a Σ 2 -definable set with computable dimension function one can construct a computable – not only semi-computable – martingale succeeding on this set. Then, using this result, a tight upper bound on the prefix complexity function for all strings in the set is obtained.

Let { φ p } be an optimal Gödel numbering of the family of computable functions (in Schnorr’s sense), where p ranges over binary strings. Assume that a list of strings L ( p ) is computable from p and for all p contains a φ -program for φ p whose length is at most ε bits larger than the length of the shortest φ -programs for φ p . We show that for infinitely many p the list L ( p ) must have 2 | p |− ε − O (1) strings. Here ε is an arbitrary function of p .

The definition of conditional probability in the case of continuous distributions (for almost all conditions) was an important step in the development of mathematical theory of probabilities. Can we define this notion in algorithmic probability theory for individual random conditions? Can we define randomness with respect to the conditional probability distributions? Can van Lambalgen’s theorem (relating randomness of a pair and its elements) be generalized to conditional probabilities? We discuss the developments in this direction. We present almost no new results trying to put known results into perspective and explain their proofs in a more intuitive way. We assume that the reader is familiar with basic notions of measure theory and algorithmic randomness (see, e.g., Shen et al. ??2013 or Shen ??2015 for a short introduction).

An a priori semimeasure (also known as “algorithmic probability” or “the Solomonoff prior” in the context of inductive inference) is defined as the transformation, by a given universal monotone Turing machine, of the uniform measure on the infinite strings. It is shown in this paper that the class of a priori semimeasures can equivalently be defined as the class of transformations, by all compatible universal monotone Turing machines, of any continuous computable measure in place of the uniform measure. Some consideration is given to possible implications for the association of algorithmic probability with certain foundational principles of statistics.

Semiautomatic structures generalise automatic structures in the sense that for some of the relations and functions in the structure one only requires the derived relations and functions are automatic when all but one input are filled with constants. One can also permit that this applies to equality in the structure so that only the sets of representatives equal to a given element of the structure are regular while equality itself is not an automatic relation on the domain of representatives. It is shown that one can find semiautomatic representations for the field of rationals and also for finite algebraic field extensions of it. Furthermore, one can show that infinite algebraic extensions of finite fields have semiautomatic representations in which the addition and equality are both automatic. Further prominent examples of semiautomatic structures are term algebras, any relational structure over a countable domain with a countable signature and any permutation algebra with a countable domain. Furthermore, examples of structures which fail to be semiautomatic are provided.

This study deals with the problem of finite-time reliable ℒ2 − ℒ∞/ℋ∞ control for non-linear systems with actuator faults through Takagi–Sugeno fuzzy model approach. The actuator failure model under consideration is assumed to be governed by a homogenous Markov chain. The focus is on the design of a fuzzy Markov switching fault-tolerant controller such that the resulting closed-loop system is stochastically finite-time bounded with a mixed ℒ2 − ℒ∞/ℋ∞ performance level over a finite-time interval. Some sufficient conditions for the solvability of the above problem are given in terms of linear matrix inequalities by introducing a new mixed ℒ2 − ℒ∞/ℋ∞ performance function. Finally, a quarter-vehicle suspension model is employed to demonstrate the effectiveness of our proposed approach.

Quantum computing has been studied over the past four decades based on two computational models of quantum circuits and quantum Turing machines. To capture quantum polynomial-time computability, a new recursion-theoretic approach was taken lately by Yamakami [J. Symb. Logic 80, pp. 1546–1587, 2020] by way of recursion schematic definition, which constitutes six initial quantum functions and three construction schemes of composition, branching, and multi-qubit quantum recursion. By taking a similar approach, we look into quantum polylogarithmic-time computability and further explore the expressing power of elementary schemes designed for such quantum computation. In particular, we introduce an elementary form of the quantum recursion, called the fast quantum recursion, and formulate $EQS$ (elementary quantum schemes) of “elementary” quantum functions. This class $EQS$ captures exactly quantum polylogarithmic-time computability, which forms the complexity class BQPOLYLOGTIME. We also demonstrate the separation of BQPOLYLOGTIME from NLOGTIME and PPOLYLOGTIME. As a natural extension of $EQS$, we further consider an algorithmic procedural scheme that implements the well-known divide-and-conquer strategy. This divide-and-conquer scheme helps compute the parity function, but the scheme cannot be realized within our system $EQS$.