# Questions tagged [kolmogorov-complexity]

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

86 questions
Filter by
Sorted by
Tagged with
17 views

### Intuition of Kolmogorov dimension in metric space

What is the intuition of Kolmogorov dimension as defined below? Let $N(\mathcal{F}, \alpha, \|\cdot\|_2)$ be the $\alpha$-covering number of $\mathcal{F}$ with respect to the $\|\cdot\|_2$-norm. ...
94 views

### Formalization in PA in the Kritchman-Raz proof

In their paper Kritchman and Raz present a proof of Gödel's second theorem using Kolmogorov complexity. To make it work, they operate in some (weak) formal theory $T$ that incorporates some arithmetic,...
106 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 ...
128 views

52 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 ...
36 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 ...
926 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 (...
34 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, ...
112 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?
89 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 ...
### 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$ ...
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 \$...