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

3
votes
1answer
26 views

Martin-Löf randomness characterization

In his 1973 paper On the notion of a random sequence, Levin states (without proving) a characterization of Martin-Löf randomness by writing Theorem 3. A sequence $\alpha$ is random w.r.t. the ...
3
votes
0answers
26 views

How approximable is time-bounded Kolmogorov Complexity?

Given a Turing Complete Language, the optimization problem would be: Given inputs x and S, where x is a finite binary string and S is a limit on steps, find the shortest program in that TC language ...
3
votes
0answers
58 views

Universal lower semicomputable semimeasure and Coding Theorem

I'm following Li and Vitanyi's book "An introduction to Kolmogorov complexity and its applications" 3ed. I'll rewrite here the definitions I need for my question. The authors define the reference ...
28
votes
2answers
4k views

What are very short programs with unknown halting status?

This 579-bit program in the Binary Lambda Calculus has unknown halting status: ...
2
votes
0answers
60 views

What are the simplest known algorithms to compute PI?

There are many algorithms that compute PI. Some are obviously complex, involving huge formulas and constants. Some formulas are not that complex, but involve operators such as ...
2
votes
1answer
37 views

Prove that the Kolmogorov complexity function cannot be approached from below

How would one go about proving that Kolmogorov function $K(x)$ cannot be approached from below by any computable function? After some research it seems I must show the function $K(x)$ is not lower ...
3
votes
1answer
56 views

Kolmogorov complexity vs purposefully inefficient Turing machines

It's a theorem that, although the Kolmogorov complexity of a string is relative to the Turing machine you're working with, it differs by at most a constant (basically the amount of space it takes to ...
2
votes
1answer
35 views

Does the Kolmogorov complexity of a program $p$ generating a string $x$ equal the complexity of $x$ up to constant?

If $U$ is a universal prefix Turing machine, $U(p)=x$ for some program $p$ and string $x$, is it true that $K(x)=K(p)+O(1)$, with $K$ being the prefix Kolmogorov complexity?
2
votes
1answer
123 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
42 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
133 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 Strings?...
1
vote
1answer
34 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
65 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 ...
4
votes
2answers
321 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 ...
2
votes
1answer
29 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
77 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
131 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 ...
8
votes
2answers
109 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
129 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 co-...
3
votes
1answer
43 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, ...
7
votes
3answers
310 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 ...
4
votes
3answers
360 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
111 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 ...
4
votes
1answer
147 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
115 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 ...
12
votes
2answers
436 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
157 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 ...
6
votes
1answer
120 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
97 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 ...
8
votes
0answers
68 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
143 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
276 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 ...
17
votes
3answers
665 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
94 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
174 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 $K(\sigma)\...
13
votes
3answers
347 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 self-...
14
votes
1answer
196 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 ...