We compare the elementary theories of Shannon information and Kolmogorov complexity, the extent to which they have a common purpose, and wherethey are fundamentally different. We discuss and relate the basicnotions of both theories: Shannon entropy, Kolmogorov complexity, Shannon mutual informationand Kolmogorov (``algorithmic'') mutual information. We explainhow universal coding may be viewed as a middle ground betweenthe two theories. We consider Shannon's rate distortion theory, whichquantifies useful (in a certain sense) information.We use the communication of (...) information as our guiding motif, and we explain howit relates to sequential question-answer sessions. (shrink)

We use a method suggested by Kolmogorov complexity to examine some relations between Kolmogorov complexity and noncomputability. In particular we show that the method consistently gives us more information than conventional ways of demonstrating noncomputability . Also, many sets which are awkward to embed into the halting problem are easily shown noncomputable. We also prove a gap-theorem for outputting consecutive integers and find, for a given length n, a statement of length n with maximal proof length.

We investigate the initial segment complexity of random reals. Let K denote prefix-free Kolmogorov complexity. A natural measure of the relative randomness of two reals α and β is to compare complexity K and K. It is well-known that a real α is 1-random iff there is a constant c such that for all n, Kn−c. We ask the question, what else can be said about the initial segment complexity of random reals. Thus, we study (...) the fine behaviour of K for random α. Following work of Downey, Hirschfeldt and LaForte, we say that αK β iff there is a constant such that for all n, . We call the equivalence classes under this measure of relative randomness K-degrees. We give proofs that there is a random real α so that lim supn K−K=∞ where Ω is Chaitin's random real. One is based upon work of Solovay, and the other exploits a new idea. Further, based on this new idea, we prove there are uncountably many K-degrees of random reals by proving that μ=0. As a corollary to the proof we can prove there is no largest K-degree. Finally we prove that if n ≠ m then the initial segment complexities of the natural n- and m-random sets and Ω︀) are different. The techniques introduced in this paper have already found a number of other applications. (shrink)

We investigate two constants cT and rT, introduced by Chaitin and Raatikainen respectively, defined for each recursively axiomatizable consistent theory T and universal Turing machine used to determine Kolmogorov complexity. Raatikainen argued that cT does not represent the complexity of T and found that for two theories S and T, one can always find a universal Turing machine such that equation image. We prove the following are equivalent: equation image for some universal Turing machine, equation image for (...) some universal Turing machine, and T proves some Π1-sentence which S cannnot prove. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

In this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov (...) class='Hi'>complexity for halting computations relative to the first jump of the halting problem. However, on machines that cannot erase their output –called monotone machines–, we prove that our complexity for non effective computations and the classical Kolmogorov complexity separate as much as we want. We also consider the prefix-free complexity for possibly infinite computations. We study several properties of the graph of these complexity functions and specially their oscillations with respect to the complexities for effective computations. (shrink)

We reconsider some classical natural semantics of integers in the perspective of Kolmogorov complexity. To each such semantics one can attach a simple representation of integers that we suitably effectivize in order to develop an associated Kolmogorov theory. Such effectivizations are particular instances of a general notion of “self-enumerated system” that we introduce in this paper. Our main result asserts that, with such effectivizations, Kolmogorov theory allows to quantitatively distinguish the underlying semantics. We characterize the families (...) obtained by such effectivizations and prove that the associated Kolmogorov complexities constitute a hierarchy which coincides with that of Kolmogorov complexities defined via jump oracles and/or infinite computations . This contrasts with the well-known fact that usual Kolmogorov complexity does not depend on the chosen arithmetic representation of integers, let it be in any base n ≥ 2 or in unary. Also, in a conceptual point of view, our result can be seen as a mean to measure the degree of abstraction of these diverse semantics. (shrink)

We use the notions of effective dimension and Kolmogorov complexity to describe a geometry on the set of infinite binary sequences. Geometric concepts that we define and use include angle, projections and scalar multiplication. A question related to compressibility is addressed using these ideas.

We shall prove the second incompleteness theorem via Kolmogorov complexity.

We study partitions of Fraïssé limits of classes of finite relational structures where the partitions are encoded by infinite binary strings which are random in the sense of Kolmogorov-Chaitin.

Kolmogorov complexity was originally defined for finitely-representable objects. Later, the definition was extended to real numbers based on the asymptotic behaviour of the sequence of the Kolmogorov complexities of the finitely-representable objects—such as rational numbers—used to approximate them.This idea will be taken further here by extending the definition to continuous functions over real numbers, based on the fact that every continuous real function can be represented as the limit of a sequence of finitely-representable enclosures, such as polynomials (...) with rational coefficients.Based on this definition, we will prove that for any growth rate imaginable, there are real functions whose Kolmogorov complexities have higher growth rates. In fact, using the concept of prevalence, we will prove that ‘almost every’ continuous real function has such a high-growth Kolmogorov complexity. An asymptotic bound on the Kolmogorov complexities of total single-valued computable real functions will be presented as well. (shrink)

In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ‮א‬₀-categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity. With a variation of this construction, we also provide an example of an ‮א‬₁-categorical but not ‮א‬₀-categorical saturated $\Sigma _{1}^{0}$ -structure with a unique computable isomorphism type. In addition, using the construction we give an example of an (...) ‮א‬₁-categorical but not ‮א‬₁-categorical theory whose only non-computable model is the prime one. (shrink)

This paper continues the study of the metric topology on $2^{\mathbb {N}}$ that was introduced by S. Binns. This topology is induced by a directional metric where the distance from $Y\in2^{\mathbb {N}}$ to $X\in2^{\mathbb {N}}$ is given by \[\limsup_{n}\frac{C(X\upharpoonright n|Y\upharpoonright n)}{n}.\] This definition is closely related to the notions of effective Hausdorff and packing dimensions. Here we establish that this is a path-connected topology on $2^{\mathbb {N}}$ and that under it the functions $X\mapsto\operatorname{dim}_{\mathcal{H}}X$ and $X\mapsto\operatorname{dim}_{p}X$ are continuous. We also investigate (...) the scalar multiplication operation that was introduced by Binns. The multiplication of a real $X\in2^{\mathbb {N}}$ by an element $\alpha\in[0,1]$ represents a dilution of the information in $X$ by a factor of $\alpha$ . Our main result is to show that every regular real is the dilution of a real of Hausdorff dimension 1. That is, that the information in every regular real can be maximally compressed. (shrink)

Consider a randomness notion C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}. A uniform test in the sense of C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document} is a total computable procedure that each oracle X produces a test relative to X in the sense of C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}. We say that a binary sequence Y is C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}-random uniformly relative to (...) X if Y passes all uniform C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document} tests relative to X. Suppose now we have a pair of randomness notions C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document} and D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{D}}$$\end{document} where C⊆D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C} \subseteq \mathcal{D}}$$\end{document}, for instance Martin-Löf randomness and Schnorr randomness. Several authors have characterized classes of the form Low which consist of the oracles X that are so feeble that C⊆DX\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C} \subseteq \mathcal{D}^X}$$\end{document}. Our goal is to do the same when the randomness notion D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{D}}$$\end{document} is relativized uniformly: denote by Low \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\star}$$\end{document} the class of oracles X such that every C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}-random is uniformly D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{D}}$$\end{document}-random relative to X. We show that X∈Low⋆\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X\in Low ^\star}$$\end{document} if and only if X is c.e. tt-traceable if and only if X is anticomplex if and only if X is Martin-Löf packing measure zero with respect to all computable dimension functions. We also show that X∈Low⋆\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X\in Low^\star}$$\end{document} if and only if X is computably i.o. tt-traceable if and only if X is not totally complex if and only if X is Schnorr Hausdorff measure zero with respect to all computable dimension functions. (shrink)

This is a presentation about joint work between Hector Zenil and Jean-Paul Delahaye. Zenil presents Experimental Algorithmic Theory as Algorithmic Information Theory and NKS, put together in a mixer. Algorithmic Complexity Theory defines the algorithmic complexity k(s) as the length of the shortest program that produces s. But since finding this short program is in general an undecidable question, the only way to approach k(s) is to use compression algorithms. He shows how to use the Compress function in (...) Mathematica to give an idea about the compressibility of various sequences. However, the idea of applying a compression algorithm breaks down for very short sequences. This is true not only for the Compress function, but also for any other compression algorithm. Zenil's approach is to construct a metric of algorithmic complexity for short sequences from scratch. He defines the algorithmic probability as the probability that an arbitrary program produces a sequence. The basic idea is to run a whole class of computational devices such as Turing Machines or Cellular Automata, and compute the distributions of the sequences they generate. Zenil presents a comparison of frequency distributions of sequences generated by 2-state 3-color Turing Machines and 2-color radius 1 Cellular Automata. He also compared these distributions to distributions found in data from the real world, and found that not only there is correlation across different systems, but also that the distributions are rather stable, and the difference between the distributions in abstract systems and real-world data can be attributed to noise. In his paper Zenil elaborates on the nature of the noise he has encountered. Zenil conjectures that the correlation distances between different systems decreases with a larger number of steps, and converge in the infinite limit case. (shrink)

An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our (...) first main result states that KL-random sequences are close to Martin-Löf random sequences in so far as every KL-random sequence has arbitrarily dense subsequences that are Martin-Löf random. A key lemma in the proof of this result is that for every effective split of a KL-random sequence at least one of the halves is Martin-Löf random. However, this splitting property does not characterize KL-randomness; we construct a sequence that is not even computably random such that every effective split yields two subsequences that are 2-random. Furthermore, we show for any KL-random sequence A that is computable in the halting problem that, first, for any effective split of A both halves are Martin-Löf random and, second, for any computable, nondecreasing, and unbounded function g and almost all n, the prefix of A of length n has prefix-free Kolmogorov complexity at least n−g. Again, the latter property does not characterize KL-randomness, even when restricted to left-r.e. sequences; we construct a left-r.e. sequence that has this property but is not KL-stochastic and, in fact, is not even Mises–Wald–Church stochastic.Turning our attention to KL-stochasticity, we construct a non-empty class of KL-stochastic sequences that are not weakly 1-random; by the usual basis theorems we obtain such sequences that in addition are left-r.e., are low, or are of hyperimmune-free degree.Our second main result asserts that every KL-stochastic sequence has effective dimension 1, or equivalently, a sequence cannot be KL-stochastic if it has infinitely many prefixes that can be compressed by a factor of α<1. This improves on a result by Muchnik, who has shown that were they to exist, such compressible prefixes could not be found effectively. (shrink)

A Martin-Löf random sequence is an infinite binary sequence with the property that every initial segment $\sigma$ has prefix-free Kolmogorov complexity $K$ at least $|\sigma| - c$, for some constant $c \in \omega$. Informally, initial segments of Martin-Löf randoms are highly complex in the sense that they are not compressible by more than a constant number of bits. However, all Martin-Löf randoms necessarily have contiguous substrings of arbitrarily low complexity. If we demand that all substrings of a (...) sequence be uniformly complex, then we arrive at the notion of shift-complex sequences. In this paper, we collect some of the existing results on these sequences and contribute two new ones. Rumyantsev showed that the measure of oracles that compute shift-complex sequences is zero. We strengthen this result by proving that the Martin-Löf random sequences that do not compute shift-complex sequences are exactly the incomplete ones, in other words, the ones that do not compute the halting problem. In order to do so, we make use of the characterization by Franklin and Ng of the class of incomplete Martin-Löf randoms via a notion of randomness called difference randomness. Turning to the power of shift-complex sequences as oracles, we show that there are shift-complex sequences that do not compute Martin-Löf random sequences. (shrink)

A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, (...) which assigns to each string x its Kolmogorov complexity: • For every underlying universal machine U, there is a constant a such that C is k(n)-enumerable only if k(n) ≥ n/a for almost all n. • For any given constant k, the Kolmogorov function is k-enumerable relative to an oracle A if and only if A is at least as hard as the halting problem. • There exists an r.e., Turing-incomplete set A such for every non-decreasing and unbounded recursive function k, the Kolmogorov function is k(n)-enumerable relative to A. The last result is obtained by using a relativizable construction for a nonrecursive set A relative to which the prefix-free Kolmogorov complexity differs only by a constant from the unrelativized prefix-free Kolmogorov complexity. Although every 2-enumerator for C is Turing hard for K, we show that reductions must depend on the specific choice of the 2-enumerator and there is no bound on the quantity of their queries. We show our negative results even for strong 2-enumerators as an oracle where the querying machine for any x gets directly an explicit list of all hypotheses of the enumerator for this input. The limitations are very general and we show them for any recursively bounded function g: • For every Turing reduction M and every non-recursive set B, there is a strong 2-enumerator f for g such that M does not Turing reduce B to f. • For every non-recursive set B, there is a strong 2-enumerator f for g such that B is not wtt-reducible to f. Furthermore, we deal with the resource-bounded case and give characterizations for the class ${\rm S}_{2}^{{\rm P}}$ introduced by Canetti and independently Russell and Sundaram and the classes PSPACE, EXP. • ${\rm S}_{2}^{{\rm P}}$ is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time tt-reduction which reduces A to every strong 2-enumerator for g. • PSPACE is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time Turing reduction which reduces A to every strong 2-enumerator for g. Interestingly, g can be taken to be the Kolmogorov function for the conditional space bounded Kolmogorov complexity. • EXP is the class of all sets A for which there is a polynomially bounded function g and a machine M which witnesses A ∈ PSPACEf for all strong 2-enumerators f for g. Finally, we show that any strong O(log n)-enumerator for the conditional space bounded Kolmogorov function must be PSPACE-hard if P = NP. (shrink)

We study reals with infinitely many incompressible prefixes. Call $A \in 2^{\omega}$ Kolmogorot random if $(\exists^{\infty}n) C(A \upharpoonright n) \textgreater n - \mathcal{O}(1)$ , where C denotes plain Kolmogorov complexity. This property was suggested by Loveland and studied by $Martin-L\ddot{0}f$ , Schnorr and Solovay. We prove that 2-random reals are Kolmogorov random. Together with the converse-proved by Nies. Stephan and Terwijn [11]-this provides a natural characterization of 2-randomness in terms of plain complexity. We finish with a (...) related characterization of 2-randomness. (shrink)

We investigate the question of whether one can characterize complexity classes in terms of efficient reducibility to the set of Kolmogorov-random strings . This question arises because and , and no larger complexity classes are known to be reducible to in this way. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the definition of Kolmogorov complexity. What follows is a list of some (...) of our main results.• Although Kummer showed that, for every universal machine U there is a time bound t such that the halting problem is disjunctive truth-table reducible to in time t, there is no such time bound t that suffices for every universal machine U. We also show that, for some machines U, the disjunctive reduction can be computed in as little as doubly-exponential time.• Although for every universal machine U, there are very complex sets that are -reducible to , it is nonetheless true that . • Any decidable set that is polynomial-time monotone-truth-table reducible to is in .• Any decidable set that is polynomial-time truth-table reducible to via a reduction that asks at most f queries on inputs of size n lies in. (shrink)

We define a program size complexity function $H^\infty$ as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in ${\{0,1\}}^\omega$ relative to the $H^\infty$ complexity. We prove that the classes of Martin-Löf random sequences and $H^\infty$-random sequences coincide and that the $H^\infty$-trivial sequences are exactly the recursive ones. We also study some properties of $H^\infty$ and compare it with other (...) class='Hi'>complexity functions. In particular, $H^\infty$ is different from $H^A$, the prefix-free complexity of monotone machines with oracle A. (shrink)

We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with.

"Complexity" is a catchword of certain extremely popular and rapidly developing interdisciplinary new sciences, often called accordingly the sciences of complexity. It is often closely associated with another notably popular but ambiguous word, "information"; information, in turn, may be justly called the central new concept in the whole 20th century science. Moreover, the notion of information is regularly coupled with a key concept of thermodynamics, viz. entropy. And like this was not enough it is quite usual to add (...) one more at present extraordinarily popular notion, namely chaos, and wed it with the abovementioned concepts. It is my aim in this paper to critically analyse this conceptual mess from a logical and philosophical point of view concentrating on the concepts of complexity and information and the question concerning the true relation between them. (shrink)

Seven problems that occur in attempts to measure complexity are pointed out as they occur in four proposed measurement techniques. Each example method is an improvement over the previous examples. It turns out, however, that none are up to the challenge of complexity. Apparently, there is no currently available method that truly gets the measure of complexity. There are two reasons. First, the most natural approach, quantitative analysis, is rendered inadequate by the very nature of complexity. (...) Second, the intrinsic magnitude of complexity is still holding at bay attempts to use both quantitative and qualitative methods combined. Further progress in complexity science and in systems science is required. Any method that simplifies will fail because it ignores what complexity is. Techniques of understanding that do not simplify, but rather provide ways for the mind to grasp and work with complexity are more effective in getting its measure. (shrink)

To formalize the human judgment of rhythm complexity, we used five measures from information theory and algorithmic complexity to measure the complexity of 48 artificially generated rhythmic sequences. We compared these measurements to human prediction accuracy and easiness judgments obtained from a listening experiment, in which 32 participants guessed the last beat of each sequence. We also investigated the modulating effects of musical expertise and general pattern identification ability. Entropy rate and Kolmogorov complexity were correlated (...) with prediction accuracy, and highly correlated with easiness judgments. A logistic regression showed main effects of musical training, entropy rate, and Kolmogorov complexity, and an interaction between musical training and both entropy rate and Kolmogorov complexity. These results indicate that information-theoretic concepts capture some salient features of the human judgment of rhythm complexity, and they confirm the influence of musical expertise on complexity judgments. (shrink)

The Kolmogorov complexity of a finite binary string is the length of the shortest description of the string. This gives rise to some ‘standard’ lowness notions for reals: A isK-trivial if its initial segments have the lowest possible complexity and A is low forKif using A as an oracle does not decrease the complexity of strings by more than a constant factor. We weaken these notions by requiring the defining inequalities to hold only up to all${\rm{\Delta (...) }}_2^0$orders, and call the new notions${\rm{\Delta }}_2^0$-bounded K-trivialand${\rm{\Delta }}_2^0$-bounded low for K. Several of the ‘nice’ properties ofK-triviality are lost with this weakening. For instance, the new weaker definitions both give uncountable set of reals. In this paper we show that the weaker definitions are no longer equivalent, and that the${\rm{\Delta }}_2^0$-boundedK-trivials are cofinal in the Turing degrees. We then compare them to other previously studied weakenings, namelyinfinitely-often K-trivialityandweak lowness for K. We show that${\rm{\Delta }}_2^0$-boundedK-trivial implies infinitely-oftenK-trivial, but no implication holds between${\rm{\Delta }}_2^0$-bounded low forKand weakly low forK. (shrink)

An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a Π₁⁰ class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y⊆ω there is an X in P such that X≥wtt Y. We show that this is also equivalent to the Π₁⁰ class's being large in some sense. (...) We give an example of how this result can be used in the study of scattered linear orders. (shrink)

ABSTRACT: How can we think about a universal ethics that could be adopted by any intelligent being, including the rising population of cyborgs, intelligent machines, intelligent algorithms or even potential extraterrestrial life? We generally give value to complex structures, to objects resulting from a long work, to systems with many elements and with many links finely adjusted. These include living beings, books, works of art or scientific theories. Intuitively, we want to keep, multiply, and share such structures, as well as (...) prevent their destruction. Such objects have value not because more information would simply mean more value. Instead, they have value because they require a long computational history, numerous interactions for their construction that we can assimilate to a computation, and they display what we call organized complexity. To propose the foundations of a universal ethics based on the intrinsic value of organized complexity, we first discuss conceptions of complexity, and argue that Charles Bennett’s logical depth is certainly a first approximation of what we are looking for. We then put forward three fundamental imperatives: to preserve, augment and recursively promote organized complexity. We show a broad range of applications with human, non-human and non-living examples. Finally, we discuss some specific issues of our framework such as the distribution of complexity, of managing copies and erasures, and how our universal ethics tackles classical ethical issues. In sum, we propose a clear, homogenous and consistent ethical foundation that can integrate many universal ethics desiderata. (shrink)

In this article, I will discuss possible differences between ecosystems and organisms on the basis of their intrinsic complexity. As the concept of complexity still remains highly debated, I propose here a practical and original way to measure the complexity of an ecosystem or an organism. For this purpose, I suggest using the concept of logical depth (LD) in a specific manner, in order to take into account the difficulty as well as the time needed to generate (...) the studied object. I illustrate this method with fully controlled Daisyworld simulations (i.e., simulations based on the Gaia hypothesis) that have often been proposed to mimic living systems. The method consists of the following sequential stages: (1) identification of the shortest program able to numerically model the studied system (also called the Kolmogorov–Solomonoff complexity); (2) running the program, once if there are no stochastic components in the system, several times if stochastic components are there; and (3) computing the time needed to generate the system with LD complexity. This measure is supposed to estimate the system complexity. It appears in this study that LD estimations fit well with the intuition we have of complex systems, with higher complexities being found for more realistic Daisyworlds. With such a method of capturing the time needed to build a system, we expect to detect in future studies any quantified differences between complex ecosystems and organisms. (shrink)

Levin and Schnorr (independently) introduced the monotone complexity, Km(α), of a binary string α. We use monotone complexity to define the relative complexity (or relative randomness) of reals. We define a partial ordering ≤Km on 2ω by α ≤Km β iff there is a constant c such that Km(α ↾ n) ≤ Km(β ↾ n) + c for all n. The monotone degree of α is the set of all β such that α ≤Km β and β (...) ≤Km α. We show the monotone degrees contain an antichain of size 2N0, a countable dense linear ordering (of degrees of cardinality 2N0), and a minimal pair. Downey, Hirschfeldt, LaForte, Nies and others have studied a similar structure, the K -degrees, where K is the prefix-free Kolmogorov complexity. A minimal pair of K -degrees was constructed by Csima and Montalbán. Of particular interest are the noncomputable trivial reals, first constructed by Solovay. We define a real to be (Km, K)-trivial if for some constant c, Km(α ↾ n) ≤ K(n)+c for all n. It is not known whether there is a Km-minimal real, but we show that any such real must be (Km, K)-trivial. Finally, we consider the monotone degrees of the computably enumerable (c.e.) and strongly computably enumerable (s.c.e.) reals. We show there is no minimal c.e. monotone degree and that Solovay reducibility does not imply monotone reducibility on the c.e. reals. We also show the s.c.e. monotone degrees contain an infinite antichain and a countable dense linear ordering. (shrink)

This paper is devoted to the control problem of a nonlinear dynamical system obtained by a truncation of the two-dimensional Navier–Stokes equations with periodic boundary conditions and with a sinusoidal external force along the x-direction. This special case of the 2D N-S equations is known as the 2D Kolmogorov flow. Firstly, the dynamics of the 2D Kolmogorov flow which is represented by a nonlinear dynamical system of seven ordinary differential equations of a laminar steady state flow regime and (...) a periodic flow regime are analyzed; numerical simulations are given to illustrate the analysis. Secondly, an adaptive controller is designed for the system of seven ODEs representing the approximation of the dynamics of the 2D Kolmogorov flow to control its dynamics either to a steady-state regime or to a periodic regime; the value of the Reynolds number is determined using an update law. Then, a static sliding mode controller and a dynamic sliding mode controller are designed for the system of seven ODEs representing the approximation of the dynamics of the 2D Kolmogorov flow to control its dynamics either to a steady-state regime or to a periodic regime. Numerical simulations are presented to show the effectiveness of the proposed three control schemes. The simulation results clearly show that the proposed controllers work well. (shrink)

This paper brings together cutting-edge, quantitative corpus methodologies and discourse analysis to explore the relationship between text complexity and subjectivity as descriptive features of opinionated language. We are specifically interested in how text complexity and markers of subjectivity and argumentation interact in opinionated discourse. Our contributions include the marriage of quantitative approaches to text complexity with corpus linguistic methods for the study of subjectivity, in addition to large-scale analyses of evaluative discourse. As our corpus, we use the (...) Simon Fraser Opinion and Comments Corpus, which comprises approximately 10,000 opinion articles and the corresponding reader comments from the Canadian online newspaper The Globe and Mail, as well as a parallel corpus of hard news articles also sampled from The Globe and Mail. Methodologically, we combine conditional inference trees with the analysis of random forests, an ensemble learning technique, to investigate the interplay between text complexity and subjectivity. Text complexity is defined in terms of Kolmogorov complexity, that is, the complexity of a text is measured based on its description length. In this approach, texts which can be described more efficiently are considered to be linguistically less complex. Thus, Kolmogorov complexity is a measure of structural surface redundancy. Our take on subjectivity is inspired by research in evaluative language, stance and Appraisal and defined as the expression of evaluation and opinion in language. Drawing on a sentiment analysis lexicon and the literature on stance markers, a custom set of subjectivity and argumentation markers is created. The results show that complexity can be a powerful tool in the classification of text into different text types, and that stance adverbials serve as distinctive features of subjectivity in online news comments. (shrink)

This work presents a discussion about the application of the Kolmogorov; López-Ruiz, Mancini, and Calbet ; and Shiner, Davison, and Landsberg complexity measures to a common situation in physics described by the Maxwell–Boltzmann distribution. The first idea about complexity measure started in computer science and was proposed by Kolmogorov, calculated similarly to the informational entropy. Kolmogorov measure when applied to natural phenomena, presents higher values associated with disorder and lower to order. However, it is considered (...) that high complexity must be associated to intermediate states between order and disorder. Consequently, LMC and SDL measures were defined and used in attempts to model natural phenomena but with the inconvenience of being defined for discrete probability distributions defined over finite intervals. Here, adapting the definitions to a continuous variable, the three measures are applied to the known Maxwell–Boltzmann distribution describing thermal neutron velocity in a power reactor, allowing extension of complexity measures to a continuous physical situation and giving possible discussions about the phenomenon. (shrink)

We suggest some new ways to effectivize the definitions of several classes of simple sets. On this basis, new completeness criterions for simple sets are obtained. In particular, we give descriptions of the class of complete maximal sets.