14

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 theorem. (See comment section below for further discussion.) Let $K(x)$ be the Kolmogorov complexity of string $x$. lemma. $K$ is not computable. Proof. ...


14

Consider the parity function (or any other function that depends on all/most bits of the input). For the parity function, $T(w) = \Theta(|w|)$. So $$f_n = \Theta(n).$$ On the other hand, $$f_n^K = \Theta\left(\frac{1}{|I^K(n)|} \sum_{w:K(w) = n} |w|\right) \geq \Omega\left(\frac{1}{2^n} \max_{w:K(w) = n} |w|\right).$$ Note that $K(2^{2^n}) = O(n)$. Thus $$...


11

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, Paul M.B.; An Introduction to Kolmogorov Complexity and Its Applications it is presented as an exercise (with a hint on how to solve it that is credited to P. ...


9

Given the interest in this question, I thought it might be helpful to point out more explicitly the reason we should not be at all surprised by the answer and try to give some direction for refinements of the question. This collects and expands on some comments. I apologize if this is "obvious"! Consider the set of strings of Kolmogorov complexity $n$: $$J^...


7

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 there is no such many-one reduction, at least for one definition of 'computing Kolmogorov complexity'. Let's formally define what we're talking about. Let $HALT$ ...


7

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. Here is a weaker statement and an attempted proof of it that doesn't depend on any details of the encoding, but I'll assume a binary language for simplicity: ...


7

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 expectation of $K (w) $ with respect to any distribution on strings of length $n $ is $\ge c $. Similarly if $\beta$ is the answer to the 2nd question then $0\le\...


7

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 there exists b ∈ℕ with $$\forall n\quad C(A\upharpoonright n)\leq C(n)+b.$$ where $C$ denotes the plain Kolmogorov complexity. These sets are known as C-trivial ...


6

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 in the common definition), then you need to expend bits on delimiting encodings. Self-terminating encodings have other advantages, and even though real ...


6

Suppose $L_0$ is an essentially-optimal description language, and consider the identity function, which is a computable partial function from $\{0,1\}^*$ to itself. According to the definition, there is a computable function $f$ and a constant $C$ such that $|f(x)| \leq |x| + C$ and $L_0(f(x)) = x$. Take now a Kolmogorov random string $x$ of length $n$. On ...


5

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 equivalence classes. We know that $K(x) \le |x|$. So, we have at most $N$ equivalence classes of sequences. One of this classes should be of size at least $2^{...


5

I'll try and give an answer to this question, and try to clear up some confusion as to the exact form of the question. The first point I want to make: the $L$ in the statement of Chaitin's constant is indeed a function of $T$. In the absolute sense, it is monotonic in the expressiveness of $T$: if $L(T)$ is the smallest natural number for which $$T\not\...


5

It really depends on your computation model. Suppose for example a model which allows random "seek" instructions, say the RAM machine. The algorithm $A$ can just include a description of the string, and on input $i$ you output the $i$th bit of the string. Conceivably, a universal Turing machine (running on a RAM machine) can execute this algorithm in time $O(...


5

(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 proof of a statement of the form "not ($p$ halts and outputs $n$)" (note that this requires quining, since it is self-referential), for some numeral $n$, such that ...


5

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 program $q$ that runs whatever program it is given as input, interprets the output as a pair, and flips the two parts. This gives you a program $\overline{q}p$ to ...


5

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 constant. The reverse is probably not possible (I think I proved this at one point but can't find it right now). The idea is that Kolmogorov complexity can be ...


4

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 approximation to the true Kolmogorov complexity, viz. http://bactra.org/notebooks/cep-gzip.html. Another option is to seek the smallest Boolean circuit that outputs ...


4

An easy case seems to be where the language $S$ contains only padded instances. When $S$ is obtained from a language $L$ by padding each instance of size $n$ with $2^n-n$ symbols, $f^K_{n}$ can be in the region of $2^{f_n}$.


4

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)$ then, by the Kraft inequality, you have a compressor which compresses your data in $- \log p(x)$ bits. If you have any computable compressor C which ...


3

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, approximately $\log_2 n$) for most $n$. Of course, every natural number $n < 2^k$ has a $k$-bit binary representation. It is only in the unary representation ...


3

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$. If a program exceeds the timebound, $U^t$ enters an infinite loop. Let $C^t(x)$ be the shortest program for $x$ on $t$. Note that $C^t$ is computable. Let $T(x)$ ...


3

Just an extended comment with no deep insights: perhaps you can cheat on the encoding of a Turing machine, and build an artificial encoding that leads to a surjective Kolmogorov complexity: $0$ represents the Turing machine that outputs $0$ (1 state TM); $0p$ represents the Turing machine that outputs $p+1$ (the number represented by the binary string $p$ ...


3

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 enumerate an infinite subset of $\{ x : K(x) > f(x)\}$. Suppose for the sake of contradiction there exists a recursive function $h$, the low-complexity compression ...


3

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,\ldots, l_k\} = L \cap \{0,1\}^n$. Denote by $s_i$ the lexicographically first certificate for $l_i$. Define $x_n$ as the list of pairs: $ x_n:= \{ (l_1, s_1), ...


3

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 that $T_U(L,n) \leq f(T_V(L,n))$ and $T_V(L,n) \leq g(T_U(L, n))$. The proof is exactly as you suggest, using an interpreter for one universal TM in the other ...


3

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 Machine that is equivalent to $V$ but does a useless iteration over the input tape between any two steps of $V$. This would result in a slowdown linear in $n$ ...


3

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 proof is in two steps. Lemma 1. For some $c_0>0$, for all $n>0$, there are strings $B$ and $B'$ such that $K(P^*_{B'} | B) \le c_0$ and $K(P^*_{B'}) = \ell(...


3

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}} = \Theta(\sqrt{s})$ for $s \ge 1$. Proof: For the lower bound, have the compressor divide into $s$ (nearly) equal pieces and output the (string of length $s$ ...


2

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\}$ (also in ascending order). Then the "GC" description is just $01enc(g)$, whose length is $2 + K(g)$. But $K(g) \leq K(x) + O(1)$, since the above description ...


2

[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 small Turing machines. See Small universal monotone Turing machines, https://cstheory.stackexchange.com/a/20980/129, https://cstheory.stackexchange.com/a/11614/129. ...


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