Open Access. Powered by Scholars. Published by Universities.®

Computer Engineering Commons

Open Access. Powered by Scholars. Published by Universities.®

University of Texas at El Paso

Kolmogorov complexity

Publication Year

Articles 1 - 4 of 4

Full-Text Articles in Computer Engineering

I-Complexity And Discrete Derivative Of Logarithms: A Symmetry-Based Explanation, Vladik Kreinovich, Jaime Nava Aug 2011

I-Complexity And Discrete Derivative Of Logarithms: A Symmetry-Based Explanation, Vladik Kreinovich, Jaime Nava

Departmental Technical Reports (CS)

In many practical applications, it is useful to consider Kolmogorov complexity K(s) of a given string s, i.e., the shortest length of a program that generates this string. Since Kolmogorov complexity is, in general, not computable, it is necessary to use computable approximations K~(s) to K(s). Usually, to describe such an approximations, we take a compression algorithm and use the length of the compressed string as K~(s). This approximation, however, is not perfect: e.g., for most compression algorithms, adding a single bit to the string $s$ can drastically change the value K~(s) -- while ...


Expanding Algorithmic Randomness To The Algebraic Approach To Quantum Physics: Kolmogorov Complexity And Quantum Logics, Vladik Kreinovich Oct 2010

Expanding Algorithmic Randomness To The Algebraic Approach To Quantum Physics: Kolmogorov Complexity And Quantum Logics, Vladik Kreinovich

Departmental Technical Reports (CS)

Physicists usually assume that events with a very small probability cannot occur. Kolmogorov complexity formalizes this idea for non-quantum events. We show how this formalization can be extended to quantum events as well.


Kolmogorov Complexity, Statistical Regularization Of Inverse Problems, And Birkhoff's Formalization Of Beauty, Vladik Kreinovich, Luc Longpre, Misha Kosheleva Jun 1998

Kolmogorov Complexity, Statistical Regularization Of Inverse Problems, And Birkhoff's Formalization Of Beauty, Vladik Kreinovich, Luc Longpre, Misha Kosheleva

Departmental Technical Reports (CS)

Most practical applications of statistical methods are based on the implicit assumption that if an event has a very small probability, then it cannot occur. For example, the probability that a kettle placed on a cold stove would start boiling by itself is not 0, it is positive, but it is so small, that physicists conclude that such an event is simply impossible.

This assumption is difficult to formalize in traditional probability theory, because this theory only describes measures on sets (e.g., for an inverse problem, on the set of all functions) and does not allow us to divide ...


We Must Choose The Simplest Physical Theory: Levin-Li-Vitanyi Theorem And Its Potential Physical Applications, Dirk Fox, Martin Schmidt, Misha Kosheleva, Vladik Kreinovich, Luc Longpre, Jeff Kuhn Sep 1997

We Must Choose The Simplest Physical Theory: Levin-Li-Vitanyi Theorem And Its Potential Physical Applications, Dirk Fox, Martin Schmidt, Misha Kosheleva, Vladik Kreinovich, Luc Longpre, Jeff Kuhn

Departmental Technical Reports (CS)

If several physical theories are consistent with the same experimental data, which theory should we choose? Physicists often choose the simplest theory; this principle (explicitly formulated by Occam) is one of the basic principles of physical reasoning. However, until recently, this principle was mainly a heuristic because it uses the informal notion of simplicity.

With the explicit notion of simplicity coming from the Algorithmic Information theory, it is possible not only to formalize this principle in a way that is consistent with its traditional usage in physics, but also to prove this principle, or, to be more precise, deduce it ...