Simulation Complexity

• Autorzy: Hay N.J.
• Języki publikacji: EN

Abstrakty

EN

In Algorithmic Information Theory, the algorithmic complexity of a sequence is the length of the shortest program which generates it. Is there a measure of the complexity of a computer? We define the simulation complexity of a computer to be the least cost of simulating that computer on a fixed universal computer. We generalise this to processes, computers which can have potentially infinite output (e.g. monotone Turing machines). This measure has monotone complexity as a special case. Simulation complexity has applications to sequence prediction, leading to a clarification of a central prediction error inequality and a stronger form of dominance. Enumerable semimeasures are functions which represent sequence predictors. These semimeasures can be in turn represented by processes. A universal process generates a universal semimeasure: one that outperforms any other predictor but for a cost depending on how complex that predictor is. This extra cost is exactly the simulation complexity of the predictor.

Słowa kluczowe

EN

simulation; algorithmic Information theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 1-2
• Strony: 117--140
• Opis fizyczny: bibliogr. 8 poz.

Twórcy

autor

Hay N.J.

• Centre for Discrete Mathematics and Computer Science, University of Auckland, New Zeland,

Bibliografia

• [1] Robert B. Ash. Real analysis and probability. Academic Press, New York, 1972. Probability and Mathematical Statistics, No. 11.
• [2] Jose-M. Bernardo. Expected information as expected utility. Ann. Statist, 7(3):686-690,1979.
• [3] Cristian S. Calude. Information and randomness. Texts in Theoretical Computer Science. An EATCS Series. Springer-Veriag, Berlin, second edition, 2002. An algorithmic perspective, With forewords by Gregory J. Chaitin and Arto Salomaa.
• [4] Nicholas Hay. Error in enumerable sequence prediction. In Marcus Hutter, Wolfgang Merkle, and Paul M.B. Vitanyi, editors, Kolmogorov Complexity and Applications, number 06051 in Dagstuhl Seminar Proceedings. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2006.
• [5] Nicholas Hay. Universal semimeasures: An introduction. Technical Report 300, Centre for Discrete Mathematics and Computer Science, University of Auckland, February 2007. Masters Thesis.
• [6] Marcus Hutter. Universal artificial intelligence. Texts in Theoretical Computer Science. An EATCS Series. Springer-Veriag, Berlin, 2005. Sequential decisions based on algorithmic probability.
• [7] Donald E. Knuth. Two notes on notation. Amer. Math. Monthly, 99(5):403-422,1992.
• [8] Ming Li and Paul Vitanyi. An introduction to Kolmogorov complexity and its applications. Graduate Texts in Computer Science. Springer-Veriag, New York, second edition, 1997