# 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.

85 questions
Filter by
Sorted by
Tagged with
31 views

### program search with optimization methods for (resource bounded) Kolmogorov complexity

Are there fields of research that look at finding short programs for generating strings (therefore trying to find the (resource bounded) Kolmogorov complexity of the string), but using optimization ...
44 views

### sophistication or logical depth to detect intelligent extra-terrestrial species

From my understanding, Algorithmic information theory (AIT) gives some ways to define the amount of « structure » in a string: for example sophistication or logical depth (see for instance [1]), can ...
133 views

### The concept of binary description by Ray Solomonoff

In this article, http://world.std.com/~rjs/rayfeb60.pdf in page 7 of the PDF, Solomonoff gives an a-priori probability for a string which is $pr(S)=2^{-|S|}$. My question - why are shorter strings ...
96 views

480 views

### Does there exist an ontology for algorithms?

It appears that algorithmic complexity theory has already figured out Kolmogorov complexity, when applied to representations of programs themselves, can already serve as a solid theoretical metric of ...
397 views

### Do we know a specific $L_{ZFC}$ such that $K(s) \ge L_{ZFC}$ is unprovable in ZFC for all strings $s$?

Chaitin's incompleteness theorem states for any formal system $F$ (which satisfies various criteria), there is a $L$ such that for any $s$ the statement $$K(s) \ge L_F$$ is unprovable in that formal ...
96 views

390 views

399 views

### Difference between time-bounded and memory-bounded Kolmogorov complexity

Let $x$ be a finite string of length $n$. Denote by $C^t(x)$ the Kolmogorov complexity of $x$ bounded by time $t$ (i.e. the length of a minimal program that outputs $x$ and running at most $t$ steps)....
100 views

### Why primitive rotation is $53.13^\circ$ in the quantum Turing machine used by Vitanyi for Quantum Kolmogrov Complexity?

Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi. In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have ...
85 views

### Computational depth and p-time hard instances

After reading the nice results of the paper: "Worst-Case Running Times for Average-Case Algorithms" by Antunes and Fortnow, I was wondering about the existence of further results linking basic ...
196 views

### Is joint Kolmogorov Complexity order invariant?

Due to the symmetry of information, it follows up to an additive constant that K(X,Y) = K(Y,X) Does this hold for more than two data objects as well?
67 views

### What is the shortest description of a universal computational structure that includes a meta-circular evaluator?

I am wondering whether there is a minimal (or the shortest known) way of specifying a universal computational structure that includes a specification of a meta-circular evaluator within that structure....
1k views

### Can we not output the Kolmogorov complexity?

Let us fix a prefix-free encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ (encoded as the prefix-free code of $T$ followed by $x$) outputs whatever $T$ outputs on ...
482 views

### Fastest Turing Machine

Recently I have been reading about Kolmogorov Complexity. As such I started thinking about the "fastest turing machine". In particular I am not interested in finding such a machine, I am only ...
105 views

### How to quantify the complexity of vectors whose components are real numbers?

I started to study Kolmogorov complexity today, and this question came to mind. Is there any way to use LZW to do this? I'm looking for a guidance to my studies
111 views

### “Checking equality for Kolmogorov complexity of two sequences” is computable?

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, ...
303 views

### Are nearly all natural numbers compressible? [closed]

There are numerous proofs that most strings are incompressible. I am interested in strings that represent natural numbers. Assume the Kolmogorov complexity of a natural number, $K(n)$, is the smallest ...