%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Algorithmic Randomness as Foundation of %%
%% Inductive Reasoning and Artificial Intelligence %%
%% Answers to 5 Questions in Computability & Randomness %%
%% Marcus Hutter, Start: November 2008 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newenvironment{keywords}{\centerline{\bf\small
Keywords}\begin{quote}\small}{\par\end{quote}\vskip 1ex}
\documentclass[12pt,twoside]{article}
\topmargin=-10mm \oddsidemargin=5mm \evensidemargin=5mm
\textwidth=15cm \textheight=22cm
\sloppy\lineskip=0pt
\begin{document}
\title{\vspace{-4ex}
\vskip 2mm\bf\Large\hrule height5pt \vskip 4mm
Algorithmic Randomness as Foundation of Inductive Reasoning and Artificial Intelligence
\vskip 4mm \hrule height2pt}
\author{{\bf Marcus Hutter}\\[3mm]
\normalsize SoCS, RSISE, IAS, CECS \\[-0.5ex]
\normalsize Australian National University \\[-0.5ex]
\normalsize Canberra, ACT, 0200, Australia \\
}
\date{5 May 2010}
\maketitle
\begin{abstract}
This article is a brief personal account of the past, present, and future
of algorithmic randomness, emphasizing its role in inductive
inference and artificial intelligence. It is written for a general
audience interested in science and philosophy.
%
Intuitively, randomness is a lack of order or predictability. If
randomness is the opposite of determinism, then algorithmic
randomness is the opposite of computability. Besides many other
things, these concepts have been used to quantify Ockham's razor,
solve the induction problem, and define intelligence.
%
\def\contentsname{\centering\normalsize Contents}
{\parskip=-2.7ex\tableofcontents}
\end{abstract}
\begin{keywords}\vspace*{-1ex}
algorithmic information theory;
individual randomness;
Ockham's razor;
inductive reasoning;
artificial intelligence.
\end{keywords}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Why were you initially drawn to the study of computation and randomness?} % Question 1:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Causal chain
Some sequences of events follow a long causal ``computable'' path,
while others are so ``random'' that the coherent causal path is
quite short. I am able to trace back quite far my personal causal
chain of events that eventually led me to computability and
randomness (C\&R), although the path looks warped and random.
% Length of my chain
At about 8 years of age, I got increasingly annoyed at always having to tidy
up my room. It took me more than 20 years to see that
computation and randomness was the solution to my problem
(well -- sort of). Here's a summary of the relevant events:
% Robots for cleaning up my room
First, my science fiction education came in handy. I was well-aware that
robots were perfectly suitable for all kinds of boring jobs, so they
should be good for tidying up my room too. Within a couple of years
I had built a series of five increasingly sophisticated robots. The
``5th generation'' one was humanoid-shaped, about 40cm high, had two
arms and hands, and one broad roller leg. The frame was metal and
the guts cannibalized from my remote controlled car and other toys.
% Brainless Robots aren't useful.
With enough patience I was able to maneuver Robbie5 with the remote
control to the messy regions of my room, have it pick up some Lego pieces
and place them in the box they belonged to. It worked! And it was
lots of fun. But it didn't really solve my problem. Picking up a block
with the robot took at least 10 times longer than doing it by hand,
and even if the throughput was the same, I felt I hadn't gained much.
% From robots to computers and AI
Robbie5 was born abound a year before my father brought home one of
the first programmable pocket calculators in 1978, a HP-19C. With
its 200 bytes of RAM or so it was not quite on par with Colossus (a
super computer which develops a mind of its own in the homonymous
movie), but HP-19C was enough for me to realize that a computer
allows programming of a robot to perform a sequence of steps
autonomously.
%
Over the following 15 years, I went through a sequence of
calculators and computers, wrote increasingly sophisticated
software, and studied computer science with a Masters degree in
Artificial Intelligence (AI). My motivation in AI of course changed
many times over the years, from the dream of a robot tidying up my
room to more intellectual, philosophical, economic, and social
motivations.
% Loss in confidence in existing AI approaches
Around 1992 I lost confidence in any of the existing approaches
towards AI, and despite considerable effort for years, didn't have
a ground-breaking idea myself.
% Key idea: Simplicity and Compression
While working in a start-up company on a difficult image
interpolation problem, I realized one day in 1997
that simplicity and compression are key, not only for solving my
problem at hand, but also for the grand AI problem.
It took me quite a number of weekends to work out the details.
Relatively soon I concluded that the theory I had developed was too
beautiful to be novel. I had rediscovered aspects of Kolmogorov
complexity and Solomonoff induction. Indeed, I had done more. My
system generalized Solomonoff induction to a universally optimal
general-purpose reinforcement learning agent.
In order to prove some of my claims it was necessary to become more
deeply and broadly acquainted with Algorithmic Information Theory
(AIT).
% Algorithmic Information Theory
AIT combines information theory and computation theory to an
objective and absolute notion of information in an individual
object, and gives rise to an objective and robust notion of
randomness of individual objects. Its major sub-disciplines are
Algorithmic ``Kolmogorov'' Complexity (AC), Algorithmic
``Solomonoff'' Probability (AP), Algorithmic ``Martin-L\"of''
Randomness (AR), and Universal ``Levin'' Search (UL)
\cite{Hutter:07ait}.
% Conclusion
This concludes my 25(!)\ year journey to C\&R. In the last 10 years,
I have contributed to all the 4 subfields. My primary driving force
when doing research in C\&R is still AI, so I've most to say about
AP, and my answers to the following questions are biased towards my
own personal interests.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What have we learned?} % Question 2:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Subordinate reasons for simplicity (elegance and tractability)
Let me begin with what {\em I} have learned: The most important
scientific insight I have had is the following: Many scientists have a
bias towards elegant or beautiful theories, which usually aligns
with some abstract notion of simplicity. Others have a bias towards
simple theories in the concrete sense of being analytically or
computationally tractable. By `theories' I essentially mean
mathematical models of some aspect of the real world, e.g.\ of a
physical system like an engine or the weather or stock market.
% The real reason for simple theories (they predict better)
Way too late in my life, at age 30 or so, I realized that the
most important reason for preferring simple theories is a quite
different one: Simple theories tend to be better for what they are
developed for in the first place, namely predicting in related but
different situations and using these predictions to improve
decisions and actions.
% Ockham's razor
Indeed, the principle to prefer simpler theories has been popularized
by William of Ockham (1285-1349) (``Entities should not be
multiplied unnecessarily'') but dates back at least to Aristotle
\cite{Franklin:02}.
% Kolmogorov, Solomonoff, Hutter
Kolmogorov complexity \cite{Kolmogorov:65} is a universal objective
measure of complexity and allows simplicity and hence Ockham's
``razor'' principle to be quantified. Solomonoff
\cite{Solomonoff:64} developed a formal theory of universal
prediction along this line, actually a few years before Kolmogorov
introduced his closely related complexity measure. My contribution
in the 200X \cite{Hutter:00kcunai,Hutter:07aixigentle} was to
generalize Solomonoff induction to a universally intelligent
learning agent \cite{Oates:06}.
% Ockham<->induction<->intelligence<->science
This shows that Ockham's razor, inductive reasoning, intelligence,
and the scientific inquiry itself are intimately related. I would
even go so far as to say that science {\em is} the application of
Ockham's razor: {\em Simple} explanations of observed real-world
phenomena have a higher chance of leading to correct predictions
\cite{Hutter:09ctoex}.
% Relation to randomness
What does all this have to do with C\&R? We cannot be certain about
{\em anything} in our world. It might even end or be completely
different tomorrow. Even if some proclaimed omniscient entity told
us the future, there is no scientific way to verify the premise of
its omniscience. So induction has to deal with uncertainty. Making
worst-case assumptions is not a generic solution; the generic
worst-case is ``anything can happen''. Considering restricted model
classes begs the question about the validity of the model class
itself, so is also not a solution. More powerful is to model
uncertainty by probabilities and the latter is obviously related to
randomness.
% Different notions of randomness
There have been many attempts to formalize probability and
randomness: Kolmogorov's axioms of probability theory
\cite{Kolmogorov:33} are the default characterization. Problems with
this notion are discussed in item (d) of Question 4. Early attempts
to define the notion of randomness of {\em individual}
objects/sequences by von Mises \cite{VonMises:19}, Wald
\cite{Wald:37}, and Church \cite{Church:40} failed, but finally
Martin-L\"of \cite{MartinLoef:66} succeeded. A sequence is
Martin-L\"of random if and only if it passes all effective
randomness tests or, as it turns out, if and only if it is
incompressible.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What don't we know (yet)?} % Question 3:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Lots of things, so I will restrict myself to open problems in the
intersection of AIT and AI. See \cite{Hutter:09aixiopen} for details.
(i) Universal Induction: The induction problem is a fundamental
problem in philosophy \cite{Hume:1739,Earman:93} and statistics
\cite{Jaynes:03} and science in general. The most important
fundamental philosophical and statistical problems around induction
are discussed in \cite{Hutter:07uspx}: Among others, they include
the problems of old evidence, ad-hoc hypotheses, updating, zero
prior, and invariance. The arguments in \cite{Hutter:07uspx} that
Solomonoff's universal theory $M$ overcomes these problems are
forceful but need to be elaborated on further to convince the
(scientific) world that the induction problem is essentially solved.
%
Besides these general induction problems, universal induction raises
many additional questions: for instance, it is unclear whether $M$
can predict all computable {\em sub}sequences of a sequence that is
itself not computable, how to formally identify ``natural'' Turing
machines \cite{Mueller:10}, Martin-L\"of convergence of $M$, and
whether AIXI (see below) reduces to $M$ for prediction.
(ii) Universal Artificial Intelligence (UAI): The AIXI model
integrates Solomonoff induction with sequential decision theory. As
a unification of two optimal theories in their own domains, it is
plausible that AIXI is optimal in the ``union'' of their domains.
This has been affirmed by positive pareto-optimality and
self-optimizingness results \cite{Hutter:04uaibook}. These results
support the claim that AIXI is a universally optimal generic
reinforcement learning agent, but unlike the induction case, the
results so far are not yet strong enough to allay all doubts.
%
Indeed, the major problem is not to {\em prove} optimality but to
{\em come up} with sufficiently strong but still satisfiable
optimality notions in the reinforcement learning case.
%
A more modest goal than proving optimality of AIXI is to ask for
additional reasonable convergence properties, like posterior
convergence for unbounded horizon.
%
The probably most important fundamental and hardest problem in game
theory is the grain-of-truth problem \cite{Kalai:93}. In our
context, the question is what happens if AIXI is used in a
multi-agent setup \cite{Shoham:08} interacting with other
instantiations of AIXI.
(iii) Defining Intelligence:
A fundamental and long standing difficultly in the field of AI is
that intelligence itself is not well defined.
%
Usually, formalizing and rigorously defining a previously vague
concept constitutes a quantum leap forward in the corresponding
field, and AI should be no exception.
%
AIT again suggested an extremely general, objective, fundamental,
and formal measure of machine intelligence
\cite{Hutter:00kcunai,Legg:08,Graham-Rowe:05,Fievet:05},
but the theory surrounding it has yet to be adequately explored.
%
A comprehensive collection, discussion and comparison of
verbal and formal intelligence tests, definitions, and measures
can be found in \cite{Hutter:07iorx}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What are the most important open problems in the field?} % Question 4:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
There are many important open technical problems in AIT. I have
discussed some of those that are related to AI in
\cite{Hutter:09aixiopen} and in the previous answer. Here I
concentrate on the most important open problems in C\&R which I am
able to describe in non-technical terms.
% The multitude of different randomness notions
(a) The development of notions of complexity and individual randomness
didn't end with Kolmogorov and Martin-L\"of.
%
Many variants of ``plain'' Kolmogorov complexity $C$ \cite{Kolmogorov:65} have been developed:
prefix complexity $K$ \cite{Levin:74,Gacs:74,Chaitin:75}, %
process complexity \cite{Schnorr:73}, %
monotone complexity $K\!m$ \cite{Levin:73random}, %
uniform complexity \cite{Loveland:69ic,Loveland:69acm}, %
Chaitin complexity $K\!c$ \cite{Chaitin:75}, %
Solomonoff's universal prior $M=2^{-K\!M}$ \cite{Solomonoff:64,Solomonoff:78}, %
extension semimeasure $M\!c$ \cite{Cover:74}, %
and some others \cite{Li:08}. %
They often differ only by $O(\log K)$,
but this can lead to important differences.
%
Variants of Martin-L\"of randomness are:
Schnorr randomness \cite{Schnorr:71},
Kurtz randomness \cite{Kurtz:81},
Kolmogorov-Loveland randomness \cite{Loveland:66}, %
and others \cite{Wang:96,Calude:02,Downey:07book}.
%
All these complexity and randomness classes can further be relativized to
some oracle, e.g.\ the halting oracle, leading to an arithmetic
hierarchy of classes.
%
Invoking resource-bounds moves in the other direction and leads to
the well-known complexity zoo \cite{Aaronson:05} and
pseudo-randomness \cite{Luby:96}.
%
% This zoo seems to be a big mess.
Which definition is the ``right'' or ``best'' one, and in which
sense?
%
Current research on algorithmic randomness is more concerned about
abstract properties and convenience, rather than practical usefulness. This is
in marked contrast to complexity theory, in which the classes also
sprout like mushrooms \cite{Aaronson:05}, but the majority of
classes delineate important practical problems.
% Exactly invariant notion of randomness
(b) The historically oldest, non-flawed, most popular, and default
notion of individual randomness is that of Martin-L\"of. Let us
assume that it is or turns out to be the ``best'' or single
``right'' definition of randomness. This would uniquely determine
which individual infinite sequences are random and which are not.
This unfortunately does not hold for finite sequences. This
non-uniqueness problem is equivalent to the problem that Kolmogorov
complexity depends on the choice of universal Turing machine. While
the choice is asymptotically, and hence for large-scale practical
applications, irrelevant, it seriously hinders applications to
``small'' problems. One can argue the problem away
\cite{Hutter:04uaibook}, but finding a unique ``best'' universal
Martin-L\"of test or universal Turing machine would be more
satisfactory and convincing. Besides other things, it would make
inductive inference absolutely objective.
% Practical invariant randomness notions
(c) Maybe randomness can, in principle, only be relative: What looks
random to me might be order to you. So randomness depends on the
power of the ``observer''. In this case, it is important to study
problem-specific randomness notions, and clearly describe and
separate the application domains of the different randomness
notions,
%
like classical sufficient statistics depends on the model class.
Algorithmic randomness usually includes all computable tests and
goes up the arithmetic hierarchy. For practical applications,
limited classes, like all efficiently computable tests, are more
relevant. This is the important domain of pseudo-random number
generation. Could every practically useful complexity class
correspond to a randomness class with practically relevant
properties?
% Comparison to classical probability theory
(d) It is also unclear whether algorithmic randomness or classical
probability theory has a more fundamental status.
% Classical probability theory
While measure theory is mathematically, and statistics is
practically very successful, Kolmogorov's probability axioms are
philosophically crippled and, strictly speaking, induce a purely
formal but meaningless measure theory exercise. The easygoing
frequentist interpretation is circular: The probability of head is
$p$, if the long-run relative frequency tends to $p$ almost surely
(with probability one). But what does `almost surely' mean?
Applied statistics implicitly invokes Cournot's somewhat forgotten
principle: An event with very small probability, singled out in
advance, will not happen. That is, a probability 1 event will
happen for sure in the real world.
% Randomness of individual sequences
Another problem is that it is not even possible to ask the question
of whether a particular single sequence of observations is random
(w.r.t.\ some measure). Algorithmic randomness makes this question
meaningful and answerable. A downside of algorithmic randomness
is that not every set of measure 1 will do, but only constructive
ones, which can be much harder to find and sometimes do not exist
\cite{Hutter:07mlconvxx}.
% Convincing AI researchers and philosophers
(e) Finally, to complete the circle, let's return to my original
motivation for entering this field: Ockham's razor (1) is the key
philosophical ingredient for solving the induction problem and
crucial in defining science and intelligence, and (2) can be
quantified in terms of algorithmic complexity which itself is
closely related to algorithmic randomness.
The formal theory of universal induction
\cite{Solomonoff:78,Hutter:07uspx} is already well-developed and the
foundations of universal AI have been laid \cite{Hutter:04uaibook}.
Besides solving specific problems like (i)-(iii) and (a)-(d) above,
it is also important to ``translate'' the results and make them
accessible to researchers in other disciplines: present the
philosophical insights in a less-mathematical way; stress that sound
mathematical foundations are crucial for advances in most field, and
induction and AI should be no exception; etc.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What are the prospects for progress?} % Question 5:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The prospects for the open problems (a)-(e) of Question 4 I believe
are as follows:
(a) I am not sure about the fate of the multitude of different
randomness notions. I can't see any practical relevance for those in
the arithmetic hierarchy. Possibly the acquired scientific knowledge
from studying the different classes and their relationship can be
used in a different field in an unexpected way. For instance, the
ones in the arithmetic hierarchy may be useful in the endeavor of
unifying probability and logic \cite{Gaifman:82}. Possibly the whole
idea of {\em objectively} identifying individually which strings
shall be regarded as random will be given up.
(b) All scientists, except some logicians studying logic,
essentially use the same classical logic and axioms, namely ZFC,
to do {\em deductive} reasoning. Why do not all scientists
use the same definition of probability to do {\em inductive}
reasoning?
%
Bayesian statistics and Martin-L\"of randomness are the most
promising candidates for becoming universally accepted for inductive
reasoning.
Maybe they will become universally accepted some time in the future,
for pragmatic reasons, or simply as a generally agreed upon
convention, since no one is interested in arguing over it anymore.
While Martin-L\"of uniquely determines infinite random sequences,
the randomness for finite sequences depends on the choice of
universal Turing machine. Finding a unique ``best'' one (if
possible) is, in my opinion, the most important open problem in
algorithmic randomness. A conceptual breakthrough would be needed to
make progress on this hard front. See \cite{Mueller:10} for a
remarkable but failed recent attempt.
(c) Maybe pursuing a single definition of randomness is illusory.
Noise might simply be that aspect of the data that is not useful for
the particular task or method at hand. For instance, sufficient
statistics and pseudo-random numbers have this task-dependence. Even
with a single fundamental notion of randomness (see b) there will be
many different practical approximations. I expect steady progress on
this front.
(d) Bayesian statistics based on classical probability theory is
incomplete, since it does not tell you how to choose the prior.
Solomonoff fixes the prior to a negative exponential in the model
complexity. Time and further research will convince classical
statisticians to accept this (for them now) exotic choice as a kind
of ``gold standard'' (as Solomonoff put it). All this is still
within the classical measure theoretic framework, which may be
combined with Cournot {\em or} with Martin-L\"of.
(e) Finally, convincing AI researchers and philosophers about the
importance of Ockham's razor, that algorithmic complexity is a
suitable quantification, and that this led to a formal (albeit
non-computable) conceptual solution to the induction and the AI problem should
be a matter of a decade or so.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Bibliography %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{small}
\begin{thebibliography}{ABCD}\parskip=-0.5ex\baselineskip=2.4ex
\bibitem[AKG05]{Aaronson:05}
S.~Aaronson, G.~Kuperberg, and C.~Granade.
\newblock Complexity zoo, 2005.
\newblock http://www.complexityzoo.com/.
\bibitem[Cal02]{Calude:02}
C.~S. Calude.
\newblock {\em Information and Randomness: An Algorithmic Perspective}.
\newblock Springer, Berlin, 2nd edition, 2002.
\bibitem[Cha75]{Chaitin:75}
G.~J. Chaitin.
\newblock A theory of program size formally identical to information theory.
\newblock {\em Journal of the ACM}, 22(3):329--340, 1975.
\bibitem[Chu40]{Church:40}
A.~Church.
\newblock On the concept of a random sequence.
\newblock {\em Bulletin of the American Mathematical Society}, 46:130--135,
1940.
\bibitem[Cov74]{Cover:74}
T.~M. Cover.
\newblock Universal gambling schemes and the complexity measures of
{K}olmogorov and {C}haitin.
\newblock Technical Report~12, Statistics Department, Stanford University,
Stanford, CA, 1974.
\bibitem[DH07]{Downey:07book}
R.~Downey and D.~R. Hirschfeldt.
\newblock {\em Algorithmic Randomness and Complexity}.
\newblock Springer, Berlin, 2007.
\bibitem[Ear93]{Earman:93}
J.~Earman.
\newblock {\em Bayes or Bust? A Critical Examination of {B}ayesian Confirmation
Theory}.
\newblock MIT Press, Cambridge, MA, 1993.
\bibitem[Fi{\'e}05]{Fievet:05}
C.~Fi{\'e}vet.
\newblock Mesurer l'intelligence d'une machine.
\newblock In {\em Le Monde de l'intelligence}, volume~1, pages 42--45, Paris,
November 2005. Mondeo publishing.
\bibitem[Fra02]{Franklin:02}
J.~Franklin.
\newblock {\em The Science of Conjecture: Evidence and Probability before
Pascal}.
\newblock Johns Hopkins University Press, 2002.
\bibitem[G{\'a}c74]{Gacs:74}
P.~G{\'a}cs.
\newblock On the symmetry of algorithmic information.
\newblock {\em Soviet Mathematics Doklady}, 15:1477--1480, 1974.
\bibitem[GR05]{Graham-Rowe:05}
D.~Graham-Rowe.
\newblock Spotting the bots with brains.
\newblock In {\em New Scientist magazine}, volume 2512, page~27, 13 August
2005.
\bibitem[GS82]{Gaifman:82}
H.~Gaifman and M.~Snir.
\newblock Probabilities over rich languages, testing and randomness.
\newblock {\em Journal of Symbolic Logic}, 47:495–--548, 1982.
\bibitem[HM07]{Hutter:07mlconvxx}
M.~Hutter and An.~A. Muchnik.
\newblock On semimeasures predicting {Martin-L{\"o}f} random sequences.
\newblock {\em Theoretical Computer Science}, 382(3):247--261, 2007.
\bibitem[Hum39]{Hume:1739}
D.~Hume.
\newblock {\em A Treatise of Human Nature, Book I}.
\newblock [Edited version by L. A. Selby-Bigge and P. H. Nidditch, Oxford
University Press, 1978], 1739.
\bibitem[Hut00]{Hutter:00kcunai}
M.~Hutter.
\newblock A theory of universal artificial intelligence based on algorithmic
complexity.
\newblock Technical Report arXiv:cs.AI/0004001, M{\"u}nchen, 62 pages, 2000.
\bibitem[Hut05]{Hutter:04uaibook}
M.~Hutter.
\newblock {\em Universal Artificial Intelligence: Sequential Decisions based on
Algorithmic Probability}.
\newblock Springer, Berlin, 2005.
\bibitem[Hut07a]{Hutter:07ait}
M.~Hutter.
\newblock Algorithmic information theory: a brief non-technical guide to the
field.
\newblock {\em Scholarpedia}, 2(3):2519, 2007.
\bibitem[Hut07b]{Hutter:07uspx}
M.~Hutter.
\newblock On universal prediction and {B}ayesian confirmation.
\newblock {\em Theoretical Computer Science}, 384(1):33--48, 2007.
\bibitem[Hut07c]{Hutter:07aixigentle}
M.~Hutter.
\newblock Universal algorithmic intelligence: A mathematical
top$\rightarrow$down approach.
\newblock In {\em Artificial General Intelligence}, pages 227--290. Springer,
Berlin, 2007.
\bibitem[Hut09a]{Hutter:09aixiopen}
M.~Hutter.
\newblock Open problems in universal induction \& intelligence.
\newblock {\em Algorithms}, 3(2):879--906, 2009.
\bibitem[Hut09b]{Hutter:09ctoex}
M.~Hutter.
\newblock A complete theory of everything (will be subjective).
\newblock 2009.
\newblock arXiv:0912.5434.
\bibitem[Jay03]{Jaynes:03}
E.~T. Jaynes.
\newblock {\em Probability Theory: The Logic of Science}.
\newblock Cambridge University Press, Cambridge, MA, 2003.
\bibitem[KL93]{Kalai:93}
E.~Kalai and E.~Lehrer.
\newblock Rational learning leads to {N}ash equilibrium.
\newblock {\em Econometrica}, 61(5):1019--1045, 1993.
\bibitem[Kol33]{Kolmogorov:33}
A.~N. Kolmogorov.
\newblock {\em Grundlagen der {W}ahrscheinlichkeitsrechnung}.
\newblock Springer, Berlin, 1933.
\newblock [English translation: {\it Foundations of the Theory of Probability}.
Chelsea, New York, 2nd edition, 1956].
\bibitem[Kol65]{Kolmogorov:65}
A.~N. Kolmogorov.
\newblock Three approaches to the quantitative definition of information.
\newblock {\em Problems of Information and Transmission}, 1(1):1--7, 1965.
\bibitem[Kur81]{Kurtz:81}
S.~A. Kurtz.
\newblock {\em Randomness and Genericity in the Degrees of Unsolvability}.
\newblock PhD thesis, University of Illinois, 1981.
\bibitem[Leg08]{Legg:08}
S.~Legg.
\newblock {\em Machine Super Intelligence}.
\newblock PhD thesis, IDSIA, Lugano, 2008.
\bibitem[Lev73]{Levin:73random}
L.~A. Levin.
\newblock On the notion of a random sequence.
\newblock {\em Soviet Mathematics Doklady}, 14(5):1413--1416, 1973.
\bibitem[Lev74]{Levin:74}
L.~A. Levin.
\newblock Laws of information conservation (non-growth) and aspects of the
foundation of probability theory.
\newblock {\em Problems of Information Transmission}, 10(3):206--210, 1974.
\bibitem[LH07]{Hutter:07iorx}
S.~Legg and M.~Hutter.
\newblock Universal intelligence: A definition of machine intelligence.
\newblock {\em Minds \& Machines}, 17(4):391--444, 2007.
\bibitem[Lov66]{Loveland:66}
D.~E. Loveland.
\newblock A new interpretation of von {M}ises' concept of a random sequence.
\newblock {\em Zeitschrift f{\"u}r Mathematische Logik und Grundlagen der
Mathematik}, 12:279--294, 1966.
\bibitem[Lov69a]{Loveland:69acm}
D.~W. Loveland.
\newblock On minimal-program complexity measures.
\newblock In {\em Proc. 1st {ACM} Symposium on Theory of Computing}, pages
61--78. ACM Press, New York, 1969.
\bibitem[Lov69b]{Loveland:69ic}
D.~W. Loveland.
\newblock A variant of the {Kolmogorov} concept of complexity.
\newblock {\em Information and Control}, 15(6):510--526, 1969.
\bibitem[Lub96]{Luby:96}
M.~Luby.
\newblock {\em Pseudorandomness and Cryptographic Applications}.
\newblock Princeton University Press, 1996.
\bibitem[LV08]{Li:08}
M.~Li and P.~M.~B. Vit\'anyi.
\newblock {\em An Introduction to {K}olmogorov Complexity and its
Applications}.
\newblock Springer, Berlin, 3rd edition, 2008.
\bibitem[Mis19]{VonMises:19}
{R. von} Mises.
\newblock {G}rundlagen der {W}ahrscheinlichkeitsrechnung.
\newblock {\em Mathematische Zeitschrift}, 5:52--99, 1919.
\newblock Correction, {\it Ibid.}, volume 6, 1920, [English translation in:
{\it Probability, Statistics, and Truth}, Macmillan, 1939].
\bibitem[ML66]{MartinLoef:66}
P.~Martin-L{\"o}f.
\newblock The definition of random sequences.
\newblock {\em Information and Control}, 9(6):602--619, 1966.
\bibitem[M{\"u}l10]{Mueller:10}
M.~M{\"u}ller.
\newblock Stationary algorithmic probability.
\newblock {\em Theoretical Computer Science}, 411(1):113--130, 2010.
\bibitem[OC06]{Oates:06}
T.~Oates and W.~Chong.
\newblock Book review: {M}arcus {H}utter, universal artificial intelligence,
{S}pringer (2004).
\newblock {\em Artificial Intelligence}, 170(18):1222--1226, 2006.
\bibitem[Sch71]{Schnorr:71}
C.~P. Schnorr.
\newblock {\em Zuf{\"a}lligkeit und Wahrscheinlichkeit}, volume 218 of {\em
Lecture Notes in Mathematics}.
\newblock Springer, Berlin, 1971.
\bibitem[Sch73]{Schnorr:73}
C.~P. Schnorr.
\newblock Process complexity and effective random tests.
\newblock {\em Journal of Computer and System Sciences}, 7(4):376--388, 1973.
\bibitem[SLB08]{Shoham:08}
Y.~Shoham and K.~Leyton-Brown.
\newblock {\em Multiagent Systems: Algorithmic, Game-Theoretic, and Logical
Foundations}.
\newblock Cambridge University Press, 2008.
\bibitem[Sol64]{Solomonoff:64}
R.~J. Solomonoff.
\newblock A formal theory of inductive inference: Parts 1 and 2.
\newblock {\em Information and Control}, 7:1--22 and 224--254, 1964.
\bibitem[Sol78]{Solomonoff:78}
R.~J. Solomonoff.
\newblock Complexity-based induction systems: Comparisons and convergence
theorems.
\newblock {\em IEEE Transactions on Information Theory}, IT-24:422--432, 1978.
\bibitem[Wal37]{Wald:37}
A.~Wald.
\newblock {D}ie {W}iderspruchsfreiheit des {K}ollektivbegriffs in der
{W}ahrscheinlichkeitsrechnung.
\newblock In {\em {E}rgebnisse eines {M}athematischen {K}olloquiums}, volume~8,
pages 38--72, 1937.
\bibitem[Wan96]{Wang:96}
Y.~Wang.
\newblock {\em Randomness and Complexity}.
\newblock PhD thesis, Universit{\"a}t Heidelberg, 1996.
\end{thebibliography}
\end{small}
\end{document}
%-------------------End-of-Comp&Rand5q.tex--------------------%