Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [kolmogorov-complexity]

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.

30
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: ...
21
votes
3answers
1k 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 (...
19
votes
1answer
288 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 ...
16
votes
3answers
403 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-contained ...
13
votes
2answers
507 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 larger ...
9
votes
0answers
81 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 ...
8
votes
2answers
1k views

Proof of non-regularity, based on the Kolmogorov complexity

In class our professor showed us 3 methods for proving non-regularity: Myhill–Nerode theorem Pumping Lemma for regular languages Proof of non-regularity, based on the Kolmogorov complexity Now the ...
8
votes
2answers
149 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 ...
7
votes
3answers
363 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 ...
7
votes
1answer
507 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 ...
6
votes
1answer
61 views

Generate string with large Kolmogrov complexity

Given $c$, can you generate a string $s$ with $K(s) \ge c$, along with a proof of that fact? I think the answer is no except for small $c$, but I'm not sure.
6
votes
2answers
328 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 ...
6
votes
1answer
167 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 ...
5
votes
2answers
80 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-...
5
votes
1answer
214 views

What's relation between Kolmogorov complexity and pseudorandomness?

In a comment on this question, @Kaveh wondered whether the questioner really wanted to ask "is there a relation between strings with high Kolmogorov complexity and pseudorandomness?" This is not the ...
5
votes
1answer
273 views

What is static complexity?

Definition : Kolmogorov complexity is a static complexity measure that captures the difficulty of describing a string. For example, the string consisting of three million zeroes can be described with ...
5
votes
1answer
72 views

Solomonoff's theory of induction, Kolmogorov complexity and Bayesian Inference

My motivations for asking this question are philosophical in nature. I'm by no means a computer scientist though, and I feel as though this question should be answered by someone who is since it's one ...
4
votes
4answers
416 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 ...
4
votes
3answers
699 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 ...
4
votes
3answers
227 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 ...
4
votes
2answers
418 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 ...
4
votes
2answers
145 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 ...
4
votes
1answer
183 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 ...
4
votes
1answer
225 views

Kolmogorov complexity of a sequence of prime numbers

Let's say $p_1, p_2, p_3, \ldots $ is the increasing sorted sequence of all prime numbers. Prove that there exists a constant $n_0 \in \mathbb{N}$, so that for all $n \ge n_0$: $$K(p_n) < \log_2(...
4
votes
1answer
204 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)\...
3
votes
2answers
298 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?...
3
votes
1answer
250 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
1answer
232 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 &...
3
votes
1answer
85 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 ...
3
votes
1answer
46 views

Gate/transistor number and program length measures of computational complexity?

Are there scaling concepts regarding the number of components needed and minimum program length needed to solve a problem of some complexity? For example, problems are characterized by O(.) measures ...
3
votes
1answer
189 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 ...
3
votes
1answer
50 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, ...
3
votes
2answers
319 views

What Good Is Kolmogorov Complexity Since It Is Relative?

Kolmogorov complexity is relative to a choice of Universal Turing Machine. Because of the Invariance Theorem, the difference in complexity assigned by two Universal Turing Machines is bounded by a ...
3
votes
1answer
52 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
1answer
100 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
28 views

Range of values for Kolmogorov complexity

Let $n$ be a positive integer. Is it true that for all $1\leq i \leq n$ there exists a length $n$ binary string $w$ such that $K(w) = i$. Where $K(w)$ is the Kolmogorov complexity of $w$. For each ...
3
votes
0answers
42 views

Computability of Kolmogorov complexity in total languages

It is well known that the Kolmogorov complexity is uncomputable in Turing-complete programming languages. However, what about total programming languages? For example, is the Kolmogorov complexity of ...
3
votes
0answers
31 views

How do you resolve this paradox with the invariance theorem?

The invariance theorem of kolmogorov complexity states that for two different languages with complexity functions $K_1$ and $K_2$, we have $$\exists c.\forall s. K_1(s) \le K_2(s) + c$$ Here is an ...
2
votes
1answer
149 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 ...
2
votes
1answer
95 views

Is Kolmogorov-random nonsensical for small numbers?

The Wikipedia definition of Kolmogorov-random defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string. Aren't nearly1 ...
2
votes
1answer
103 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 ...
2
votes
1answer
89 views

Number of $1$'s in a Kolmogorov-random number

The problem I'm trying to tackle is to show that for a Kolmogorov-random number of length $n$, the amount of $1$'s in its binary representation is greater than $n/4$. My only idea so far, is to use a ...
2
votes
1answer
145 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 ...
2
votes
1answer
154 views

Kolmogorov Complexity proving there exists a constant for when if two strings are equal length

When talking about kolmogorov complexity, I understand that it describes true randomness of given (for now) a string $x$, if we can describe x in less than the $|x|$ then its complexity is said to be ...
2
votes
1answer
285 views

Proof: Kolmogorov complexity of string concatenation

Does there exist a universal constant $c$ such that for any strings $x, y$, we have: $$K(xy)\leq K(x) + K(y) + c$$ where $K(\cdot)$ denotes the Kolmogorov Complexity of a binary string and $xy$ means ...
2
votes
1answer
191 views

Computing the Kolmogorov complexity of a string

What would be the implications for complexity theory if you could compute the Kolmogorov complexity of a string generated by a psuedorandom generator?
2
votes
1answer
81 views

An infinite subsequence of random numbers in Kolmogorov sense

Is it possible to construct an infinite increasing sequence of random naturals (in Kolmogorov sense) that is a subsequence of another sequence? Ok, in general I suppose not, e.g. for prime numbers. ...
2
votes
1answer
47 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 ...
2
votes
1answer
193 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 ...
2
votes
1answer
63 views

What doest it mean: “computer is an intelligence amplifier”?

There is one example in Kolmogorov complexity books and related articles: Consider we have a monkey at a typewriter and a monkey at a computer keyboard. If the monkey types at random on a typewriter,...