14
votes
Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem?
EDIT: Adding the caveat that Roger's fixed-point theorem may not be a special case of Lawvere's.
Here is a proof that may be "close"... It uses Roger's fixed-point theorem instead of Lawvere's ...
- 9,545
11
votes
Accepted
Proof for Kolmogorov complexity is uncomputable using reductions
You can find two different proofs in:
Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Program-size Complexity Computes the Halting Problem. Bulletin of the EATCS 57 (1995)
In Li, Ming, Vitányi, ...
- 22.5k
7
votes
Accepted
Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?
Chaitin in his 1976 paper
Chaitin, Gregory J., Information-theoretic characterizations of recursive infinite strings, Theor. Comput. Sci. 2, 45-48 (1976). ZBL0328.02029.
studied sets such that ...
- 4,445
7
votes
Proof for Kolmogorov complexity is uncomputable using reductions
This was a fun question to think about. As described in the other answer and the comments below, there is a Turing reduction from the Halting problem to computing Kolmogorov complexity, but notably ...
- 2,295
7
votes
Can we not output the Kolmogorov complexity?
The question can be rephrased as whether or not $\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} = 0$, and as Denis points out in the comments this is false for some encodings. ...
- 548
7
votes
Expected Kolmogorov complexity under Kolmogorov complexity distribution
If $\alpha$ is the answer to the 1st question then $\alpha=\infty$. Namely, for any $c $ there is an $n $ such that all strings $w $ of length at least $n $ have $K (w) \ge c$. In particular the ...
- 4,445
6
votes
Accepted
Where does the "intuitive" understanding of Kolmogorov complexity fails
The issue in play here is whether you use a self-terminating encoding (like your C example) or not. If you use a self-terminating encoding, then the subadditivity property does hold. If you don't (as ...
- 14.2k
5
votes
Accepted
Is joint Kolmogorov Complexity order invariant?
You don't need symmetry of information. The invariance theorem does the trick. Let $p$ the smallest program such that $U(p) = \langle x, y\rangle$. One way of producing $(y, x)$ is to take make a ...
- 459
5
votes
Efficiently computable variants of Kolmogorov complexity
Basically, almost any machine learning or compression method is an approximation to Kolmogorov complexity:
If you have any computable probability distribution which assigns your data probability $p(x)...
- 459
5
votes
"Checking equality for Kolmogorov complexity of two sequences" is computable?
I think of the following argument: if we can check whether two sequences have equal Kolmogorov complexity we can write a program that enumerates all sequences of length $\le N$ and divides them into ...
- 251
5
votes
Accepted
Do we know a specific $L_{ZFC}$ such that $K(s) \ge L_{ZFC}$ is unprovable in ZFC for all strings $s$?
(Note: This answer works for most any consistient theory, not just $ZFC$.)
We will define a machine $p$ based on the universal algorithm. $p$ does a search, looking for a string that represents a ...
- 471
5
votes
Kolmogorov Complexity of a Decidable Language
Yes, depending on what kinds of inputs you consider (see below). $KC(x) =^* KCDL(L_x)$, where $L_x$ is the language which consists only of the string $x$, and $=^*$ means equals up to an additive ...
- 36.4k
4
votes
Accepted
How to quantify the complexity of vectors whose components are real numbers?
You can use LZW or other standard compression methods to approximate the Kolmogorov complexity. In some real-world cases this works well. However, it is dangerous, as it can also be a pretty bad ...
- 36.4k
3
votes
Are nearly all natural numbers compressible?
I think there is confusion here based on binary vs unary representation. The statement 'most strings are incompressible' means that the Kolmogorov complexity $K(n)$ is approximately $|n|$ (that is, ...
- 2,295
3
votes
Can we not output the Kolmogorov complexity?
I think the following works. I'll use $C(x)$ for the Kolmogorov complexity
Give $U$ a time bound $t$ (say, some exponential function of the length of the input program), and call the result $U^t$. ...
- 459
3
votes
Difference between time-bounded and memory-bounded Kolmogorov complexity
Assume that there exists a sparse set $L \in \mathbf{NP} -\mathbf{P}$, this is equivalent to $\mathbf{EXP}\not= \mathbf{NEXP}$.
Then we can construct such a sequence. Indeed, consider $L_n = \{l_1,\...
- 1,881
3
votes
Accepted
Fastest Turing Machine
Probably the best one can say at this level of generality is that $T_U(L,n)$ and $T_V(L,n)$ are computably related (if $U$ and $V$ are both universal), i.e. there are computable functions $f,g$ such ...
- 36.4k
3
votes
Fastest Turing Machine
The statement $T_U(L,n) \le c_{UV} \cdot T_V(L,n)$ is not true for all choices of $U$. It's easy to think of a Universal Turing Machine that is simply inefficient. For example choose $U$ as the ...
- 131
3
votes
Accepted
Compression algorithms for low-complexity strings?
No, at least not in the TM model, i.e., for Kolmogorov complexity. Given $g(x) \leq f(x) \leq |x|$ for all $x$ where $g$ is monotonic and unbounded and $f$ is recursive, it is not possible to ...
- 13.9k
3
votes
Accepted
Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic
EDIT 2: Updated the answer for the updated definition of typical.
I may be misunderstanding your definition of $P^*_{B'}$. With that caveat, though, I believe your conjecture does not hold. The ...
- 9,545
3
votes
Accepted
Upper bound on the expected number of correct bits via a "lossy compression"
Let $f(n,s)$ denote the answer.
Claim: We have $f(n,s) = \frac{n}{2}+\Theta(\sqrt{sn})$ for any fixed $s$ as $n \to \infty$. More precisely, $\lim_{n \to \infty} \frac{f(n,s)-\frac{n}{2}}{\sqrt{n}} = \...
- 320
2
votes
Accepted
Commonality of minimal Kolmogorov structure functions
Lemma 1 below shows that with a standard TM encoding, the fraction of strings that are MKSSs is bounded away from both 0 and 1. This answered a question posed in the original post.
Lemma 2 shows that ...
- 9,545
2
votes
Reasonable estimate of an asymptotic limit notion of Kolmogorov complexity
As commenters @Lwins and @SashaNikolov have already stated, it is non-computably hard to compute a function as slow-growing as $f$. (So no really humanly comprehensible rate can be given.)
Namely, ...
- 4,445
2
votes
Relation between different "complexity theories" and complex systems theory
For the relation between first and second look up descriptive complexity theory and finite model theory. This is a established branch of complexity theory and logic.
- 21.4k
2
votes
Accepted
What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?
They are equivalent. For any $x$, let $g_x$ be a permutation with just two cycles: one consisting of $\{i \in [n] : x_i = 0\}$ (say, in ascending order) and one consisting of $\{i \in [n] : x_i = 1\}$ ...
- 36.4k
2
votes
Does there exist an ontology for algorithms?
[More of an extended comment.]
I think I disagree with the premise of your first paragraph... That being said, while I don't know of a database, there has been some work systematically studying ...
- 36.4k
2
votes
Accepted
how to define "correlation" between languages?
Your idea only works on languages with finite descriptions; here is an approach that's well defined for all languages, but it requires choosing some probability distribution $\mu$ on the set of all ...
- 10.2k
2
votes
Accepted
Kolmogorov Complexity of the composition of two computable functions
Your bound is correct, for exactly the reasons you give. It is also unimprovable in general. Suppose that each function is multiplication by a large constant, where both constants are subwords of some ...
- 10.2k
2
votes
Accepted
Prime factorisation of decidable problems
I think a candidate for such a set $\mathbb{B}$, or something very much like it, could be produced by considering an infinite sequence of singleton languages: $L_1=\{w_1\},L_2=\{w_2\},\ldots$ --- ...
- 10.2k
1
vote
Accepted
Inferring the Kolmogorov complexity of a string from its substrings' complexity
A simple bound is that we could use a program generating $x$, a starting index $1 \leq i \leq n$ and length $m$ to get a program generating any choice of $v$, and thus $C(v)$ is bounded as
$$\forall v:...
- 690
Only top scored, non community-wiki answers of a minimum length are eligible