2
votes
1answer
48 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. ...
3
votes
1answer
52 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
37 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
36 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
122 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 ...
0
votes
0answers
28 views

Positive Arithmetic Complexity

Define the binary operator $[k]$ as an operator that takes an integer $k$ and operates between two integers $a,b$ such that: $$a[k]b = (...((((a)[k-1]a)[k-1]a)[k-1]...a)[k-1]a$$ (b times) And: ...
1
vote
0answers
33 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
108 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
304 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}$. ...
3
votes
1answer
896 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 ...
3
votes
1answer
388 views

Questions about the proof that minimal Turing machines are not recursively enumerable & proof that Kolmogorov complexity is uncomputable

This thread can be broken up into two questions. First I am trying to understand the proof that $MIN_{TM}$ is not recursively enumerable. If M is a Turing machine, then we say that the length of ...
6
votes
1answer
335 views

Is there an infinite set of strings whose Kolmogorov complexities are computable?

Is there an infinite set of strings whose Kolmogorov complexities are computable?