Questions tagged [kolmogorov-complexity]

In Kikuchi's paper Kolmogorov complexity and the second incompleteness theorem the Kolmogorov Complexity (KC) of $x$ is defined as $$ K(x) = \mu e (\varphi_e(0) \simeq x) \, . $$ This seems to give ...

Motivation: Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...

What is the relationship between Kolmogorov $\epsilon$-entropy, Kolmogorov $n$-width, and Kolmogorov $\epsilon$-capacity of a set $M$ in a metric space $X$? (The $\epsilon$-capacity here is the ...

A two-coloring is done over the (infinite) set all incompressible strings (in some chosen alphabet); such that, an edge between two strings is blue if and only if, the strings are of equal lengths and ...

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