Skip to main content
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 ...
Neal Young's user avatar
  • 10.8k
10 votes

Does every computable function have infinitely many "non-padded" representations?

Given any computable function $f : \mathbb{N} \to \mathbb{N}$ the set of its indices $S_f = \{n \in \mathbb{N} \mid \phi_n = f\}$ is for all practical purposes "the set of all programs computing $...
Andrej Bauer's user avatar
  • 29.2k
8 votes
Accepted

Fast algorithms for time bounded Kolmogorov complexity

TL;DR: It is believed that no polynomial time algorithm exists for neither $K_t$, $K^{poly}$ nor $KT$. We have no idea about $K^{t^{\prime}}$ since it has never really been studied. No faster ...
Eric Allender's user avatar
7 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 ...
Yuval Filmus's user avatar
  • 14.5k
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 ...
Bjørn Kjos-Hanssen's user avatar
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 ...
Bjørn Kjos-Hanssen's user avatar
6 votes

Resource-bounded variant of Kolmogorov complexity

The question was revised (in the comments) to ask: Given x, output the shortest description d such that U(d) = x in time $|d|^2$. Yanyi Liu and Rafael Pass showed (in FOCS 2020) that this function is ...
Eric Allender's user avatar
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 ...
Christopher King's user avatar
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 ...
Peter's user avatar
  • 459
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 ...
Joshua Grochow's user avatar
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}} = \...
mathworker21's user avatar
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,\...
Alexey Milovanov's user avatar
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 ...
domotorp's user avatar
  • 14k
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 ...
Neal Young's user avatar
  • 10.8k
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 ...
Neal Young's user avatar
  • 10.8k
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, ...
Bjørn Kjos-Hanssen's user avatar
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.
Kaveh's user avatar
  • 21.7k
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\}$ ...
Joshua Grochow's user avatar
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 ...
Joshua Grochow's user avatar
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 ...
Aryeh's user avatar
  • 10.6k
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 ...
Aryeh's user avatar
  • 10.6k
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$ --- ...
Aryeh's user avatar
  • 10.6k
2 votes
Accepted

An invariance theorem for algorithmically random data in statistical learning

I think this is a similar approach to Shnor's Martingale characterisation of algorithmic randomness, I have sent you an email with more info, but it is a potential nice non-overfitting test and also ...
Hector Zenil's user avatar
1 vote
Accepted

Clarification sought re Li & Vitanyi's Proof of Godel Incompleteness in Formal System F

In this argument, we assume that the formal system F provides us with a way to check whether a proof of a mathematical statement is correct. Thus formally, we assume that there is a computable ...
Bruno Bauwens's user avatar
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:...
orlp's user avatar
  • 885
1 vote

How to extend Solomonoff Induction to continuous domain

The set of computable real functions is also recursively enumerable. Assume it is enumerated by $(f_i)_{i\in\omega}$. Then the Solomonoff prior of $f_i$ is $p(f_i)=2^{-K(i)}$. So there is no ...
Xi Li's user avatar
  • 21
1 vote

The concept of binary description by Ray Solomonoff

It is the consequence of the Occam's razor pinciple and maximum entropy principle, if we interpret Occam's razor as to minimize the expected codeword length of the model/program. Then we can either ...
Xi Li's user avatar
  • 21
1 vote

Definition of a prefix-free Turing machine

[Second major edit since first posting:] This is a supplement to @CarlMummert's answer, with some slight disagreement or clarification. (He surely knows more than I do in this area, though, so I may ...
Mars's user avatar
  • 111

Only top scored, non community-wiki answers of a minimum length are eligible