Tag Info

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 $$... 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. ... 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^...

8

For channel capacity, it seems difficult to replace Shannon entropy by Kolmogorov complexity. The definition of channel capacity does not contain any mention of entropy. Using the Shannon entropy gives the right formula for channel capacity (this is Shannon's theorem). If you replaced the formula with Shannon entropy by a formula with Kolmogorov complexity, ...

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

The ideas the question expresses are interesting but maybe insufficiently fleshed out. I can see a couple of points that deserve further refinement. It is difficult to "code the exact same functionality". In part that is because what counts as "the exact same functionality" depends on the chosen notion of program equivalence. For terminating programs in ...

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

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

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

A string $x$ is $c$-compressible if $K(x) \leq |x| + c$. If $x$ is not compressible by $1$, $x$ is said to be incompressible (or random, if you will). There are $2^n$ bit strings of length $n$, and there are $\sum_{i=0}^{n-1} 2^i = 2^n-1$ descriptions that are of length less than $n$. Because each description describes at most one string, there is at least ...

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 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 here is a project Rosetta Code somewhat similar or adaptable to some of your goals [which as others point out are not very specific/objective/concise/clearcut yet], a database involving quantification of languages on the same task for comparison. the post "Code Length Measured in 14 Languages" is an example of the quantitative analysis possible with this ... 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 ... 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 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 ... 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

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

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

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

Every integer has an associated Kolmogorov complexity; the shortest program that prints that integer. There are $\approx {x \over ln(x)}$ primes up to $x$ so primes have lower Kolmogrov complexity than composites on average; $\approx ln({x \over ln(x)})$ vs $\approx ln(x)$. As a side effect you have to have some large gaps between primes; otherwise you ...

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