Abstracts

P. Gacs

While Kolmogorov complexity is the accepted absolute measure of information content of an individual finite object, a similarly absolute notion is needed for the relation between an individual data sample and an individual model summarizing the information in the data, for example, a finite set (or probability distribution) where the data sample typically came from. The statistical theory based on such relations between individual objects can be called algorithmic statistics, in contrast to classical statistical theory that deals with relations between probabilistic ensembles. We develop the algorithmic theory of statistic, sufficient statistic, and minimal sufficient statistic. This theory is based on two-part codes consisting of the code for the statistic (the model summarizing the regularity, the meaningful information, in the data) and the model-to-data code. In contrast to the situation in probabilistic statistical theory, the algorithmic relation of (minimal) sufficiency is an absolute relation between the individual model and the individual data sample. We distinguish implicit and explicit descriptions of the models. We give characterizations of algorithmic (Kolmogorov) minimal sufficient statistic for all data samples for both description modes---in the explicit mode under some constraints. We also strengthen and elaborate earlier results on the ``Kolmogorov structure function'' and ``absolutely non-stochastic objects''---those rare objects for which the simplest models that summarize their relevant information (minimal sufficient statistics) are at least as complex as the objects themselves. We demonstrate a close relation between the probabilistic notions and the algorithmic ones: (i) in both cases there is an ``information non-increase'' law; (ii) it is shown that a function is a probabilistic sufficient statistic iff it is with high probability (in an appropriate sense) an algorithmic sufficient statistic.

J. Reimann

One of the main problems of the frequency approach to randomness is the definition of an admissible selection rule. It turned out that the algorithmic approaches by Church, Kolmogorov-Loveland, and others could not capture the whole strength of Martin-Löf-randomness. One might ask now which classes of binary sequences do have characterizations as Kollektivs in the sense of von Mises. If one for example considers the Borel-normal sequences as a Kollektiv, one can show that selection rules defined via finite automata preserve normality. For another kind of selection rules, "apriori" selection rules in the sense that they select terms for the subsequence independent of what has been selected or examined before, Kamae in a famous paper gave a complete characterization of admissible apriori selection rules, by a criteria called "completely deterministic" (based on a special entropy notion for individual sequences). These questions studied by Kamae and others in the context of ergodic theory and dynamical systems have recursion theoretic counterparts: What kind of sequences do not have any information about Martin-Löf random sequences? Kucera and Terwijn showed that there are nonrecursive sequences being in this sense "low" for the random sequences. But not much more is known yet about the possible complexity of those sequences. In this talk we intend to give a survey on the methods stemming from ergodic theory used to study the above questions, basically invariant measures and entropy, before presenting some new results on normality preservation as well as on the recursion theoretic counterpart, using an effective version of Hausdorff dimension.

J. Schmidhuber

The traditional theory of Kolmogorov complexity and algorithmic probability focuses on monotone Turing machines with one-way write-only output tape. This naturally leads to the universal enumerable Solomonoff-Levin measure. Here we introduce more general, nonenumerable but cumulatively enumerable measures (CEMs) derived from Turing machines with lexicographically nondecreasing output and random input, and even more general approximable measures and distributions computable in the limit. We obtain a natural hierarchy of generalizations of algorithmic probability and Kolmogorov complexity. Among other things we show that there are objects computable in the limit yet more random than Chaitin's ``number of wisdom'' Omega, that any approximable measure of x is small for any x lacking a short description, that there is no universal approximable distribution, that there is a universal CEM, and that any nonenumerable CEM of $x$ is small for any $x$ lacking a short enumerating program. We briefly mention consequences for universes sampled from such priors.

An. Muchnik, A. Shen, N. Vereshagin (speaker), M. Vyugin and M. Ushakov

For certain information transmission curcuits we estimate the minimal capacity of its channels in terms of Kolmogorov complexity of its inputs and outputs.

W. Merkle (speaker) and T. Ebert

A set A\subseteq{0,1} is called i.o. autoreducible (with respect to some concept of reducibility) if A is reducible to itself via a reduciton computed by a machine that never queries its oracle at the input, computes A(x) correctly for infinitely many input words, and, for some inputs x, may output a don't-know symbol instead of computing A(x). We obtain the somewhat counterintuitive result that every p-random set, hence every Martin-Löf random set, is polynomial-time i.o. autoreducible. Furthermore, we consider upper and lower bounds on the frequency of correct guesses that may be achieved when i.o. autoreducing random sets.

J.-C. Dubacq

Comma-free prefix machines are a simple extension of prefix machines. After a brief recall on prefix machines, I will show that comma-free prefix machines have no additively optimal machines.

F. Blanchard, J. Cervelle (speaker) and E. Formenti

Not communicated yet.

L. Antunes

We introduce Computational Depth, a measure for the amount of ``nonrandom'' or ``useful'' information in a string by considering the difference of various Kolmogorov complexity measures. We investigate three instantiations of Computational Depth: - Basic Computational Depth, a clean notion capturing the spirit of Bennett's Logical Depth. - Time- t Computational Depth and the resulting concept of Shallow Sets, a generalization of sparse and random sets based on low depth properties of their characteristic sequences. We show that every computable set that is reducible to a shallow set has polynomial-size circuits. - Distinguishing Computational Depth, measuring when strings are easier to recognize than to produce. We show that if a Boolean formula has a nonnegligible fraction of its satisfying assignments with low depth, then we can find a satisfying assignment efficiently.

J. Schmidhuber

Solomonoff's optimal but noncomputable strategy for inductive inference assumes the observations are drawn from a recursive prior. Here we make the additional assumption that the process computing the data is optimally efficient, and that the cumulative prior probability of all data whose computation costs at least O(n) time is inversely proportional to n. Since in fact there exists a very simple, general, asymptotically optimal algorithm for all computable data, we can explicitly extract the corresponding speed prior, and derive a computable strategy for optimal inductive reasoning.

M. Hutter

The provably asymptotically fastest algorithm within a factor of 5 for formally described problems will be constructed. The main idea is to enumerate all programs provably equivalent to the original problem by enumerating all proofs. The algorithm could be interpreted as a generalization and improvement of Levin search, which is, within a multiplicative constant, the fastest algorithm for inverting functions. Blum's speed-up theorem is avoided by taking into account only programs for which a correctness proof exists. Furthermore, it is shown that the fastest program that computes a certain function is also one of the shortest programs provably computing this function. To quantify this statement, the definition of Kolmogorov complexity is extended, and two new natural measures for the complexity of a function are defined.