Questions tagged [kolmogorov-complexity]

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

Filter by
Sorted by
Tagged with
5
votes
1answer
238 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)] ...
5
votes
1answer
133 views

Kolmogorov complexity vs. intuitive notion of simplicity

Consider the infinite sequence $1,2,4,8,16,...$ If one were asked how the sequence continues the answer would likely be $32,64,..,2^k,..$ and one would implicitly assume the question to be about the "...
11
votes
0answers
345 views

Does Chaitin's constant have infinitely many prime prefixes?

Define $f(n) = \lfloor 2^n \cdot \Omega \rfloor$, that is, $f(n)$ is the first $n$ bits of Chaitin's constant interpreted as a number written in binary. I am trying to figure out if $f(n)$ can have ...
5
votes
3answers
472 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}$. ...
1
vote
1answer
83 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 ...
5
votes
1answer
4k 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 ...
5
votes
0answers
109 views

Recursion theoretic definition of Kolmogorov complexity

In Kikuchi's paper Kolmogorov complexity and the second incompleteness theorem the Kolmogorov Complexity (KC) of $x$ is defined s $$ K(x) = \mu e (\varphi_e(0) \simeq x) \, . $$ This seems to give ...
2
votes
0answers
113 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 = ...
2
votes
1answer
154 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?...