Kolmogorov complexity concerns the size of the shortest program that generates a given string.

learn more… | top users | synonyms

1
vote
0answers
20 views

$K(xy)\leq K(x)+K(y) +c$?

Could anyone show that for any $c$, some strings $x$ and $y$ exist, where $K(xy)>K(x)+K(y)+c$? Here $K(x)$ is the Kolmogorov complexity. I already know that $K(xy) \leq 2K(x) + K(y) +c$ and $K(xy) ...
0
votes
0answers
12 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?
1
vote
1answer
71 views

What is the shortest LOOP program that outputs 2016? [closed]

Use a minor restriction of the LOOP language described under Wikipedia's "LOOP (Programming Language)". The restriction is to eliminate constants. So, the language contains increment: $x_i++$, ...
0
votes
0answers
45 views

nocomputable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
0
votes
1answer
52 views

not any computable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
1
vote
1answer
82 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 ...
3
votes
1answer
44 views

Abstract machines that compute primitive recursive functions

What it the simplest (least powerful) abstract machine that can compute primitive recursive sets, i.e. sets whose characteristic or indicator function is primitive recursive? ...
1
vote
0answers
38 views

Understanding AI through a complexity function

I've been trying to understand in light of a few apparent paradoxes for me. It appears reasonable that we could prove any mathematical problem that has a well defined answer can be solved by a ...
0
votes
0answers
15 views

How can the maximum complexity of a binary series be proven

In an article in the scientific American (https://www.cs.auckland.ac.nz/~chaitin/sciamer.html), Chaitin mentions a way to determine the maximum complexity of the minimal program of a sequence of ones ...
0
votes
1answer
17 views

Kolmogorov complexity when no language is specified

The statement of theorem 3 in "A frequentist understanding of sets of measures" by Fierens, Rêgo, and Fine (pdf available here) requires that the Kolmogorov complexity of a certain function be less ...
2
votes
0answers
56 views

chinese reminder theorem (CRT) time complexity

Let p1,...pk be the k first prime numbers. Denote p1*...*pk by n. We want to find x mod n, for that asume we found x mod pi for i in {1,...,k} , then use CRT to observe x mod n. What is the lowest ...
0
votes
1answer
16 views

Computability for equality in Kolmogorov complexity?

It is a known result that Kolmogorov complexity is not computable for every arbitrary sequence. I wonder whether the following problem is computable or not: "Given $x$ and $y$ as two sequences, ...
0
votes
1answer
58 views

Is the Kolmogorov complexity of a number always its logarithm?

if I have a natural number $a(n,m)$ that depends on some $n$ and $m$, where $m$ is fixed, isn't then the Kolmogorov complexity of it simply its logarithm?
1
vote
1answer
49 views

Proof of a classical Theorem of Martin-Löf on complexity dips for Kolmogorov complexity,

I have a question on the first Theorem from the article Complexity of Oscillations in Infinite Binary Sequences by P. Martin-Löf, which could be downloaded from the publisher or from here. Theorem ...
1
vote
1answer
29 views

Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity

Denote by $C(n)$ the plain Kolmogorov complexity of $n$ and the length of a binary encoding of $n$ by $l(n)$, why do we have $$ C(n\mid l(n)) \ge C(n) - C(l(n))? $$ If I have a shortest program $p$ ...
1
vote
0answers
16 views

Each recursive approximating sequence for Kolmogorov complexity is not uniform

Denote the plain Kolmogorov complexity by $C(x)$. Let $\phi(t,x)$ be a recursive function and $\lim_{t\to\infty} \phi(t,x) = C(x)$ for all $x$. For each $t$ define $\psi_t(x) := \phi(t,x)$ for all ...
2
votes
0answers
20 views

Kolmogorov complexity of substring if string is divided according to rule

Denote the plain Kolmogorov complexity of a string $u$ by $C(u)$. Now let $u$ be a string of length $n$ with $C(u) \ge n - O(1)$ and suppose $u = u_1 \cdots u_{\log n}$, a subdivision of the ...
1
vote
0answers
32 views

On Kolmogorov complexity of first and last half of a string

Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy $C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$. Any ideas how to ...
1
vote
0answers
31 views

Kolmogorov complexity, no description mechanism can improve on additively optimal/universal one infinitely often

In An Introduction to Kolmogorov Complexity and Its Applications explaining the notion of additively optimal or universal it is written: The key point is not that the universal description method ...
2
votes
0answers
44 views

Is there any research on Diophantine Approximation with computable numbers

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
0
votes
0answers
29 views

How to prove equality $K(x, K(x)) = K(x) + O(1) $?

It is needed to prove that $K(x, K(x))=K(x) + O(1)$ where $K$ means Kolmogorov complexity. I think the equality is true because when we find Kolmogorov complexity of $x$ we already knows $K(x)$ and ...
0
votes
1answer
49 views

Proof of an inequality about Kolmogorov complexity of two words.

It is needed to prove an existing of such constant C that for any words $x$,$y$ $K(x,y) \le K(x) + K(y) + log(|x|+|y|) + C$ (K is Kolmogorov complexity) I tried to prove it by using next true ...
2
votes
0answers
29 views

Kolmogorov complexity inequality

Prove, that KP (x) ≤ KS (x) + log KS(x) + 2 log log KS (x) + O(1). Please tell me in which direction to think.
1
vote
0answers
24 views

Optimal Kolmogorov complexity

Let computable function U is the best way to describe to Kolmogorov complexity. Prove that the mapping V, determined crucial for any word p as V (p) = U (U (p)), is also optimal way to describe the. ...
-4
votes
1answer
62 views

Must an uncountable set contain elements having infinite information? [closed]

For example, a number constructed by Cantor's diagonal argument has infinite information/Kolmogorov complexity. Does there exist an uncountable set whose elements each have a finite description ...
1
vote
0answers
54 views

Kolmogorov complexity of a computer?

Warning: Vague, unclear question ahead. Proceed at your own risk. The Shannon entropy and Kolmogorov complexity give you in broad informal terms how unpredictable a string is and to what degree the ...
2
votes
0answers
39 views

Does a random binary sequence almost always have a finite number of prime prefixes?

Does a random binary sequence almost always have a finite number of prime prefixes? Specifically, let $x = \sum_{1 \le i}{2^{-i} \cdot x_i}$ with $x_i \in \{0,1\}$ be a random real in $[0,1)$, $X_i = ...
3
votes
1answer
384 views

Relationship between compression, shannon entropy and kolmogorov complexity

I have read that the Shannon Entropy is used as a bound for the compressibility of a message, for example here 1 it says "In other words, the best possible lossless compression rate is the entropy ...
0
votes
1answer
41 views

Kolmogorov complexity of an algorithm?

I've read that Kolmogorov comlexity is about calculating the least number of bits needed to describe a string or other mathematical objects. Does 'other mathematical objects' include algorithms too? ...
5
votes
1answer
96 views

Prove that bitstrings with 1/0-ratio different from 50/50 are compressable

I'm looking for a proof, that $$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$ with $n>0$, $0 \le \lambda \le 1/2$ and $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] ...
2
votes
1answer
78 views

Prove that these Sets Containing Infinitely Many Incompressible Strings Exist

We define a set $A$ to be special if: $$\liminf_{n \to \infty} \frac{|A^{\leq n}|}{n} = 0$$ I want to prove that there are special recursive sets that contain infinitely many incompressible strings. ...
1
vote
0answers
71 views

Solomonoff induction , Shannon Entropy, Kolmogorov Complexity.

If Expected Kolmogorov Complexity equals Shannon Entropy why can't Shannon Entropy be used as an approximation of Kolmogorov Complexity in Solomonoff Induction? Regarding Kolmogorov Complexity and ...
3
votes
1answer
61 views

How much information is in the question “How much information is in this question?”?

I'm actually not sure where to pose this question, but we do have an Information Theory tag so this must be the place. The "simple" question is in the title: how do I know how many bits of information ...
1
vote
1answer
101 views

Kolmogorov complexity for infinite strings

I'm struggling with a problem that I believe I've managed to reduce to a question of Kolmogorov complexity for infinite strings, but since I'm not an expert in this field, I'm not sure about the ...
1
vote
1answer
72 views

A question on Kolmogorov Complexity

Is it true that for all strings of a given length at least one has its Kolmogorov complexity equal to its length ? Is there a proof if the answer is in affirmative? (For any alphabet with more than ...
1
vote
1answer
51 views

Kolmogorov (Kolmogoroff- ) Complexity of infinite sequences, Request for Proof

Let $\xi \in X^{\omega}$ be an infinite sequence and denote by $\xi[1\ldots n]$ its length $n$ initial segment. Then (due to Martin-Löf) the following holds: For every $\xi \in X^{\omega}$ there ...
0
votes
1answer
54 views

Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$ K(w) := \mbox{length of a shortest program producing $w$}. $$ Now fix some ...
3
votes
3answers
233 views

Is it possible to create a string with known Kolmogorov Complexity?

I wish to compare compressors using strings with known Kolmogorov Complexity, but I haven't got the theoretical background and tools to understand how to do that. I'm just starting in this area and ...
1
vote
0answers
49 views

Kolmogorov complexity proof of Lovasz local lemma

Roughly speaking, Kolmogorv Complexity proof of lovasz local lemma states that for any $k$-CNF $S$ on $n$ variables and $m$ clauses, where the dependency of every clause is bounded by $2^{k-c}$, for ...
2
votes
1answer
105 views

Definability of Kolmogorov Complexity?

This paper claims to have a proof of Godel's Second Incompleteness Theorem using Kolmogorov Complexity: http://www.ams.org/notices/201011/rtx101101454p.pdf As far as I can tell, it seems to assume ...
0
votes
2answers
88 views

Regularity of balanced binary strings

How can one tell which number of propositional variables is necessary to express a Boolean function given as a sequence of 0s and 1s (a binary string) of length $2^n$ as a Boolean formula? ...
8
votes
3answers
221 views

Measure of how much information is lost in an implication

In an implication like $p \implies q$, is there some measure of how much information is lost in the implication? For example, consider the following implications, where $x \in \{0,1,\ldots,9\}$: ...
1
vote
1answer
59 views

Respective complexities of a string and its substring

If $s$ is a substring so that $s \subset S$, can Kolmogorov complexity of the whole string $S$ be lower than that of the given substring, $K(S) < K(s)$?
1
vote
1answer
64 views

Kolmogorov complexity of sequence and its fragment

Is it possible that part of sequence is more complex than all sequence because the best way to encode it is to use the complete sequence and starting and ending positions of the fragment. Maybe, for ...
1
vote
0answers
34 views

Is it really true that $K(x|y) = K(x,y) - K(y)$?

Denote by $y^*$ the shortest program computing the string $y$. In the main textbook and various papers of Li & Vitanyi, I have seen the following statements. The first is well established: the ...
2
votes
2answers
128 views

Solovay Randomness

Say that an $x\in 2^{\omega}$ is Solovay random if for all computably enumerable collections of intervals $\{I_n\}$ such that $\sum_n\mu(I_n)<\infty$, then $x\in I_n$ for at most finitely many $n$. ...
4
votes
2answers
330 views

Does the $k$th forward difference of Radó's $\Sigma$ eventually dominate every computable function?

Let $\Sigma$ be Radó's Busy Beaver function, and let $\Delta[\Sigma]$ denote the forward difference of $\Sigma$, such that $\Delta[\Sigma] \ (n) = \Sigma(n+1) - \Sigma(n)$ for all $n \in \mathbb{N}$. ...
2
votes
0answers
284 views

The minimal number of states required to run Goldbach's Conjecture

It is well known that being able to compute Busy Beaver numbers would allow one to solve (in theory) such open problems as Goldbach's conjecture. Simply run a Turing machine with $n$ states to check ...
7
votes
2answers
2k views

Question about the definition of “Prefix free”

I am trying to understand the definition of "Prefix free", but I do not understand the definition nor the example that wikipedia provides. I was hoping for clarification. Below is an excerpt from ...
3
votes
1answer
2k views

Proof that the set of incompressible strings is undecidable

I would like to see a proof or a sketch of a proof that the set of incompressible strings is undecidable. Definition: Let x be a string, we say that x is c-compressible if K(x) $\leq$ |x|-c. If x is ...