# Questions tagged [kolmogorov-complexity]

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

88 questions
Filter by
Sorted by
Tagged with
6 views

### Is the Kolmogorov Complexity of 11…1 with even length L less than for the string 1010…10 of the same length?

We define the Kolmogorov Complexity to be independent of any particular programming language for bit string x as the length of the shortest string <M,w> where TM M on input w halts with x on its ...
13 views

### Limiting probabilities for a markovian process

I'm studying the markov chain and markovian process. Right now I've completed the explanation of the Chapmann-Kolmogorov equation and I'm studing the queue process. The book I'm using just says that ...
19 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. ...
106 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,...
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 ...
181 views

### The philosophical significance of Chaitin's Theorem

In a book review of Torkel Franzén's "Gödel’s Theorem: An Incomplete Guide to Its Use and Abuse" in the Notices the reviewer (Raatikainen) writes: Franzén also devotes a brief chapter to ...
136 views

110 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++$, ...
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?...
72 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 ...
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 ...
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, ...