# Tagged Questions

The Kolmogorov complexity of a string s is equal to the length of the shortest program computing s and halting. Measures the lack of structure in a string.

36 views

### What is the shortest description of a universal computational structure that includes a meta-circular evaluator?

I am wondering whether there is a minimal (or the shortest known) way of specifying a universal computational structure that includes a specification of a meta-circular evaluator within that structure....
35 views

### Maximum entropy definition of universal distribution

Kolmogorov complexity and the "universal distribution" $m$, defined e.g. here and discussed in detail in the book of Li and Vitanyi, are defined with respect to a universal Turing machine (UTM). ...
306 views

### Fastest Turing Machine

Recently I have been reading about Kolmogorov Complexity. As such I started thinking about the "fastest turing machine". In particular I am not interested in finding such a machine, I am only ...
97 views

### How to quantify the complexity of vectors whose components are real numbers?

I started to study Kolmogorov complexity today, and this question came to mind. Is there any way to use LZW to do this? I'm looking for a guidance to my studies
76 views

### “Checking equality for Kolmogorov complexity of two sequences” is computable?

It is a known result that Kolmogorov complexity is not computable for every arbitrary sequence. I wonder whether the following problem is computable or not: "Given $x$ and $y$ as two sequences, ...
89 views

### Are nearly all natural numbers compressible? [closed]

There are numerous proofs that most strings are incompressible. I am interested in strings that represent natural numbers. Assume the Kolmogorov complexity of a natural number, $K(n)$, is the smallest ...
76 views

### What is the problem of finding a largest subset of smallest Kolmogorov complexity?

What do you call the problem of finding a largest possible subset of strings with smallest possible information content? I'm studying a particular instantiation of this problem in a different setting ...
72 views

### Is joint Kolmogorov Complexity order invariant?

Due to the symmetry of information, it follows up to an additive constant that K(X,Y) = K(Y,X) Does this hold for more than two data objects as well?
97 views

### What is the Kolmogorov complexity of arithmetic?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(n) > L$ where $K(n)$ is the Kolmogorov complexity of the number $n$ and $L$ is a sufficiently large ...
960 views

### Can we not output the Kolmogorov complexity?

Let us fix a prefix-free encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ (encoded as the prefix-free code of $T$ followed by $x$) outputs whatever $T$ outputs on ...
479 views

### Proof for Kolmogorov complexity is uncomputable using reductions

I am looking for a proof that Kolmogorov complexity is uncomputable using a reduction from another uncomputable problem. The common proof is a formalization of Berry's paradox rather than a reduction, ...
129 views

### Comparing the Kolmogorov complexity of theories - Part 2

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
372 views

### Comparing the Kolmogorov complexity of theories

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(s) > L$ where $K(s)$ is the Kolmogorov complexity of string $s$ and $L$ is a sufficiently large ...
149 views

### Is Kolmogorov complexity quasi-surjective?

For Kolmogorov complexities $\hspace{.02 in}K$ induced by essentially-optimal description languages, does there exist an integer $c$ such that for all positive integers $n$, there exists a string $x$...
162 views

### Kolmogorov Complexity vs Running Time (Edited)

Let $U$ be a universal Turing Machine. Suppose I have a Kolmogorov incompressible string $s$ of length $n$. Let $A:\{1,...,n\} \to \{0,1\}$ be an algorithm such that $A(i) = s_i$. I believe that the ...
92 views

### The concept of binary description by Ray Solomonoff

In this article, http://world.std.com/~rjs/rayfeb60.pdf in page 7 of the PDF, Solomonoff gives an a-priori probability for a string which is $pr(S)=2^{-|S|}$. My question - why are shorter strings ...
281 views

### Is Kolmogorov complexity a surjective function?

Let us fix an encoding of Turing-machines and a universal Turing-machine, U, that on input (T,x) outputs whatever T outputs on input x (possibly both running forever). Define the Kolmogorov complexity ...
30 views

### Different definitions of optimal decompressors

Let $B^{<\omega}$ be the set of finite binary strings. I will only consider functions from $B^{<\omega}$ to $B^{<\omega}$. I recall the definition of the algorithmic complexity of a string ...
880 views

### Using Kolmogorov complexity as input “size”

Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$. Normally in the analysis of algorithms or computational complexity theory, we have some ...
59 views

### Entropy criterion of efficiency for (comparison using hashing)

I understand that hash is effective iff the "domain" size is smaller than the size of the "general set" - set of all possible objects. E.g., "domain" is the set of valid english phrases with length ...
100 views

### Is there an $\mathcal{L}$-theory and a formula $\phi$ for which Kolmogorov(proof($\phi$)) $<$ Kolmogorov($\phi$)?

Are there a complete decidable $\mathcal{L}$-theory, a formula $\phi$ and a proof of $\phi$ for which the Kolmogorov complexity of the proof of $\phi$ is less than the Kolmogorov complexity of $\phi$? ...
185 views

### Kolmogorov Complexity of an arbitrary string

For an arbitrary string sampled from $\{0,1\}^n$, what would be the probability that the string has a Kolmogorov Complexity $\geq$ length of the string, $n$. In other words, how many strings are ...
595 views

### Kolmogorov Complexity applications in Number Theory

What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.) One of ...
103 views

### What information can a program give about the Kolmogorov Complexity of its accepting Language

Suppose we have a program(algorithm) that solves some decision problem $(\Sigma,L)$. Given the program, can we always say something about the Kolmogorov complexity of the words in $L$ ?
818 views

### How to measure programming language succinctness?

I want to explore the notion of quantifying the amount of succinctness a programming language provides. That is, the amount a high-level language reduces the complex. This idea of "simplification" ...
46 views

### Boltzmann sampling software

I'm looking for an implementation of Boltzmann sampling for combinatorial structures. Recent paper in the area for context: http://hal.inria.fr/docs/00/74/77/09/PDF/NonRedundantGeneration-TCS-2010....
123 views

### Complexity of Roman numeral evaluation

I came up with a result the other day that arbitrary length Roman numeral evaluation can be modeled as a monoid: https://gist.github.com/4542999 1) Is this a known result? 2) If not, any ...
199 views

849 views

### Definition of a prefix-free Turing machine

A prefix-free function is one whose domain is prefix-free. Similarly, a prefix-free (Turing) machine is one whose domain is prefix-free. It is usual to consider such a machine as being self-...
218 views

### Non-computable=>normal?

If we have an infinite string of 0's and 1's, such that no finite Turing-machine can output it. What can we say about the string? Must it be normal, ie. must every finite sequence appear infinite ...
1k views

### Efficiently computable variants of Kolmogorov complexity

Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features: It corresponds to an intuition of giving strings with patters or ...
292 views

### Channel coding results using Kolmogorov complexity

Usually Shannon entropy is used to prove channel coding results. Even for source-channel separation results shannon entropy is used. Given the equivalence between Shannon (global) vs Kolmogorov (local)...
472 views

### Expected values of Kolmogorov complexity in a random sample

Kolmogorov complexity of a string is not computable. However, in a random subset of size $M$ of binary strings of length $n$, how many are expected to have complexity less than some integer $n_{0}$ ...
319 views

### Kolmogorov complexity with weak description languages

We can think of Kolmogorov complexity of a string $x$ as the length of the shortest program $P$ and input $y$ such that $x = P(y)$. Usually these programs are drawn from some Turing-complete set (like ...
307 views

### Average-case analysis of algorithms using the incompressibility method

I recently became very interested in Kolmogorov complexity and the incompressibility method especially in the context of average-case analysis. The "standard" book by Li & Vitanyi showcases many ...
233 views

### Time-bounded Kolmogorov complexity and non-random strings

If $t$ is a time constructible function then we can define the time-bounded Kolmogorov complexity of a string $x$ as: $C^t(x)$ = the size of the smallest program p that generates $x$ in $t(|x|)$ ...
999 views

### Is there a theory to answer “the simplest program to solve a problem”?

To answer "what problems can be solved by computing", we developed the theory of computability. For the problems that are computable, is there a theory to answer the question "is the program I get the ...