%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% 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--------------------%