The Kolmogorov complexity of a string s is equal to the length of the shortest program computing s and halting. Measures the lack of structure in a string.

learn more… | top users | synonyms

2
votes
1answer
120 views

Should Kolmogorov complexity include all resources or just program size?

I've been thinking about pi and Kolmogorov complexity (Kc). As the digits of pi are randomly distributed (and infinite) , they can't be compressed with a typical compression program. Through the ...
0
votes
0answers
33 views

Without fancy math, how does the MC-AIXI algorithm work?

How does the MC-AIXI algorithm work? I tried to read the paper, but I got lost in the math. I understand the concept of AIXI very well, but I don't get two things: 1) Where does MC-AIXI get its ...
3
votes
2answers
121 views

set of Kolmogorov-random strings is co-re

given RC = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings. How can I show that RC is co-re I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random ...
1
vote
1answer
23 views

Prove $\forall c \in \mathbb{N} \, \exists x,y \in \Sigma^* \, [K(xy) > K(x) + K(y) + c]$

I am trying to prove a theorem (title) given in a starred problem in Sipser's book. I have absolutely no idea how I would go about showing it, and after trying a few different approaches came here ...
2
votes
1answer
61 views

Kolmogorov complexity of strings in a given language

Consider the language $$L = \{1^i 0^j 1^k \mid i + j = 2k, k ≥ 1\}\,,$$ and let $x_n$ be the canonical $n$'th word in $L$. My problem involves proving that the Kolmogorov complexity of $x_n$ can be ...
3
votes
2answers
284 views

Are nearly all natural numbers compressible?

A simple counting argument shows most strings can't be compressed to shorter strings. But, compression is usually defined using Kolmogorov complexity. A string is compressible if its Kolmogorov ...
1
vote
1answer
27 views

(operationalizable) Cost measure for small problems

For what I know of complexity measures in CS, they are aimed at rather large problems. With today's computing power, most people don't care about comparing the complexity of simple problems as they ...
3
votes
1answer
76 views

Optimization in multivalued logic. Optimal strings with given patterns

This question comes from an application in multivalued logic. Suppose, we are given an alphabet of three letters $A, B, C$ and a set of indices $1,2,3,4,5$. Consider items formed by subscripting the ...
3
votes
1answer
124 views

How does this proof show that sequences of $O(1)$ polynomially bounded Kolmogorov complexity are NOT the polynomial computable ones?

I'm trying to understand a proof from the paper: Balcázar, José L.; Gavaldà, Ricard; Hermo, Montserrat: Compressiblity of infinite binary sequences, Published in: Complexity, Logic, and Recursion ...
6
votes
2answers
98 views

Average case algorithm analysis using Kolmogorov Incompressibility Method

The Incompressibility Method is said to simplify the analysis of algorithms for the average case. From what I understand, this is because there is no need to compute all of the possible combinations ...
3
votes
3answers
124 views

Termination in infinite-time

Does it make sense to speak of algorithms that take an infinite amount of time to terminate? In particular, suppose we have a loop with a bound function that is initially positive and is decreased ...
3
votes
1answer
59 views

Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

Define the language $\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$ where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$. Prove that $R$ is ...
3
votes
1answer
32 views

Why can't we search lexicographicaly ordered programs to compute Kolmogrov complexity?

Kolmogrov complexity is known to be uncomputable. Why can't we enumerate all programs of size i = 0 in lexicographical order - if any produce string s, that is the Kolmogrov complexity; if not, ...
6
votes
3answers
275 views

What problem cannot be solved by a short program?

BACKGROUND: Recently I tried to solve a certain difficult problem that gets as input an array of $n$ numbers. For $n=3$, the only solution I could find was to have a different treatment for each of ...
3
votes
3answers
312 views

Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers. An ...
2
votes
1answer
95 views

Is the length of the shortest quine in a programming language computable?

The length of the shortest program in a given (fixed) programming language that produces a given output is that output's Kolmogorov complexity, which is not a computable function on the set of ...
3
votes
1answer
134 views

What determines the entropy of a program's source code?

a few days ago I asked a question about the limits of compression: Can PRNGs be used to magically compress-stuff? The idea common to all the answers was that if you consider all programs of length ...
5
votes
2answers
110 views

What is an estimation of the Kolmogorov Complexity for the first N integers?

I'm aware some ints have higher or lower Kolmogorov Complexities. For example, the number 5.41126806512 has a very low complexity as it can be expressed by ...
10
votes
2answers
426 views

Kolmogorov Complexity: Why would you need more bytes than the string itself?

I was reading Wikipedia's entry on Kolmogorov Complexity (thanks to this question), which states: It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes ...
4
votes
1answer
154 views

Proving a string is random

I am reading Kolmogorov Complexity by Li and Vitányi: "Let $x$ be a finite binary string. We write '$x$ is random' if the shortest binary description of $x$ with respect to the optimal specification ...
5
votes
1answer
114 views

Computability of Kolmogorov Complexity

Fix a universal Turing machine $M$. Let $A^*=\{0,1\}^n$ be the set of all binary string of length $n$. Determine the Kolmorogov complexity $K(x)$ of each $x\in A$, w.r.t. $M$. Just for a matter of ...
2
votes
1answer
90 views

The choice of programming language and the length of a program

I wonder how it's possible that: it can be shown that all reasonable choices of programming languages lead to quantification of the amount of absolute information in individual objects that is ...
7
votes
0answers
66 views

Interval density of time bounded Kolmogorov complexity

The Kolmogorov complexity of a string $x$ is the size of the smallest Turing machine $M$ that started on empty tape produces $x$. To make it computable, we can add a bound on the time used by $M$ to ...
3
votes
3answers
129 views

What is an example of complex random string, in the Kolmogorov-Chatin sense?

Any string generated from a PRNG clearly has a very short description. You need the code for the random number generator, the seed, and then the number of times to iterate. So, it seems that all ...
5
votes
1answer
256 views

Kolmogorov complexity of string concatenation

If $K(s)$ is the Kolmogorov complexity of the string $s \in \{0,1\}^*$, Can we prove (or disprove) the following statement: "Every string $s$ is a prefix of an incompressible string; i.e. for every ...
15
votes
3answers
618 views

Approximating the Kolmogorov complexity

I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors ...
4
votes
2answers
90 views

Kolmogorov complexity of a decision problem

What's the definition of Kolmogorov complexity for a decision problem? For example, how to define the length of the shortest program that solves the 3SAT problem? Is it the "smallest" Turing machine ...
3
votes
1answer
170 views

When does the function mapping a string to its prefix-free Kolmogorov complexity halt?

In Algorithmic Randomness and Complexity from Downey and Hirschfeldt, it is stated on page 129 that $\qquad \displaystyle \sum_{K(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$, where ...
12
votes
3answers
336 views

Difference between “information” and “useful information” in algorithmic information theory

According to Wikipedia: Informally, from the point of view of algorithmic information theory, the information content of a string is equivalent to the length of the shortest possible ...
12
votes
1answer
186 views

Equivalence of Kolmogorov-Complexity definitions

There are many ways to define the Kolmogorov-Complexity, and usually, all these definitions they are equivalent up to an additive constant. That is if $K_1$ and $K_2$ are kolmogorov complexity ...