Questions tagged [kolmogorov-complexity]

Kolmogorov complexity concerns the size of the shortest program that generates a given string.

Filter by
Sorted by
Tagged with
0 votes
1 answer
66 views

What are a set of example of tasks or problems where the Kolmogorov Complexity is Known -- ideally numerical values can be obtained?

Is there a machine learning task (or any task/problem) that one can by construction know the Kolmogorov Complexity (or minimum description length)? I know the Kolmogorov Complexity is uncomputable but ...
Charlie Parker's user avatar
1 vote
1 answer
43 views

On the Kolmogorov complexity of integers with large prime factors

Any sufficiently large prime must be compressible, in the sense that $K(p)<\log_2{p}$ for any prime $p$ greater than some constant. It seems it is also implied that given any $d$, you can choose a ...
Trevor's user avatar
  • 5,982
0 votes
0 answers
44 views

Variational form of Kolmogorov backward equation

I was looking through research papers and found the one form of Kolmogorov backward equation is, $\frac{\partial \rho}{\partial t} = - \nabla V(x) \cdot \nabla \rho + \beta^{-1} \Delta \rho$ where ...
Charles Kim's user avatar
11 votes
1 answer
436 views

Why is incomputability weaker than Kolmogorov complexity?

Abbot et al. "Experimentally probing the algorithmic randomness and incomputability of quantum randomness" remark that "incomputability is a weaker property than Kolmogorov randomness&...
Mars's user avatar
  • 1,338
1 vote
0 answers
84 views

How to use Kolmogorov's law 0 or 1 here?

Let $f$ be a Borel function of the coordinates $x_1,\dots,x_n,\dots$ such that for all $i\in\mathbb{N}$, $$f(x_1,\ldots,x_{i-1},x_i,x_{i+1},x_{i+2},\ldots) = f(x_1,\ldots,x_{i-1},x_{i+1},x_i,x_{i+2},\...
Jacob Walker's user avatar
4 votes
1 answer
98 views

How does one prove that a programming language can calculate every (computable) real number?

Inspired from my previous question, Are there measurements of how much "information" is required to construct given (real) numbers?, I've written a very simple programming language to ...
Graviton's user avatar
  • 4,480
3 votes
0 answers
40 views

Do all Turing-complete systems converge on a single universal function w.r.t. description redundancy?

Let $L$ be any Turing-complete language. Let $d_L(n)$ be the number of distinct algorithms expressible in $L$ using at most $n$ bits. I'm not sure how to properly define "distinct algorithm",...
Trevor's user avatar
  • 5,982
0 votes
0 answers
32 views

Is there a lower bound on the rate of growth of distinct algorithms (vs. description size) in a Turing-complete system?

...where a "distinct algorithm" is approximately defined as an algorithm that returns a value distinct from all others thus far. I would think not, because you can always construct some ...
Trevor's user avatar
  • 5,982
4 votes
1 answer
108 views

Kolmogorov complexity of primes vs. composites in the limit?

If we take two natural numbers of roughly equivalent magnitude where one is prime and the other is composite, will the Kolmogorov complexity of one or the other tend to be higher as we approach ...
Trevor's user avatar
  • 5,982
3 votes
1 answer
213 views

Kolmogorov Complexity and Compression Schemes

My question concerns strings with low Kolmogorov Complexities and if there is a single compression scheme that can be used to compress them I have been introduced to Kolmogorov Complexity through ...
Anwar's user avatar
  • 256
-1 votes
1 answer
59 views

How many bitstrings of length n are there with c adjacent 1s somewhere? [closed]

I am self-studying Kolmogorov complexity, and for its purposes, (Sipser exercise 6.26) I am trying to prove that for constant c, as n approaches infinity, the ratio of bitstrings of length n that ...
master bob's user avatar
1 vote
0 answers
74 views

How to square frequentist with algorithmic complexity definition of randomness?

The algorithmic (Kolmogorov) complexity definition of randomness states that a random string is incompressible, yet 11111111 would not be considered random because ...
vonjd's user avatar
  • 8,770
4 votes
0 answers
101 views

Why do almost all points in the unit interval have Kolmogorov complexity 1?

I am reading Jin-yi Cai, Juris Hartmanis, On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, Journal of Computer and System Sciences, Volume 49, Issue 3, December ...
i like math's user avatar
  • 1,043
3 votes
0 answers
35 views

Are there measurements of how much "information" is required to construct given (real) numbers?

I have noticed that among the many mathematical constants (particularly irrational or transcendental), some require more comprehensive equations and descriptions than others, in order to specify their ...
Graviton's user avatar
  • 4,480
1 vote
1 answer
91 views

Prove that there are at most finitely many random (Kolmogorov random) prime numbers [closed]

Prove that there are at most finitely many random (Kolmogorov random) prime numbers. A number is Kolmogorov random if $$K(n) ≥ K(\operatorname{bin}(n)) ≥ \lceil \log_2(n+1)\rceil - 1.$$ Hint: You can ...
Stephen Brown's user avatar
0 votes
1 answer
86 views

What does an optimal Turing Machine mean?

Let $M$ be a TM, and let $x \in \sum^*$. The plain Kolmogorov complexity of x with respect to m is - $C_{M}(x) = min\{|\pi|:\pi \in \sum^* \land M(\pi) = x \}$ A TM U is optimal if, for all TM M there ...
desert_ranger's user avatar
1 vote
1 answer
219 views

What is the relationship between Kolmogorov Complexity and Turing Machines?

I am trying to understand the following definition - Let M be a TM, and let $x \in \sum^*$. The plain Kolmogorov complexity of x with respect to M is - $C_{M}(x) = min\{|\pi|:\pi \in \sum^* \land M(\...
desert_ranger's user avatar
0 votes
1 answer
100 views

How do I quantify the amount of information in the following expression?

Suppose that $N = \mbox{factorial}(9999999999)$. The number $N$ is mindbogglingly huge and, yet, can be represented very neatly and compactly as $\mbox{factorial}(9999999999)$. I have two questions: ...
st0n3r's user avatar
  • 3
3 votes
1 answer
40 views

Name for real that requires infinite bits to specify?

Kolmogorov complexity defines the complexity of things in terms of how many bits it takes to specify them. All integers can be specified using a finite number of bits, proportional to their logarithm. ...
Yair Halberstadt's user avatar
1 vote
0 answers
59 views

How is Kolmogorov complexity calculated?

In lectures, my professor discussed Kolmogorov complexity for 10 minutes but I have too many questions opened. My professor claimed (and I was able to prove it myself) that $|K(X)| \leq |x|+1$. But ...
David's user avatar
  • 21
2 votes
3 answers
129 views

Is the Kolmogorov complexity of any string equally low?

I'm learning just now about this topic so this might be the most naive of the questions. So, if I understand it correctly, the string: ...
Swike's user avatar
  • 261
1 vote
1 answer
89 views

Is this kolmogorov complexity inequality true?

We note $K(X)$ the kolmogorov complexity of the word X and $K(X|Y)$ the kolmogorov complexity of $X$ knowing $Y$. Let $M$ an universal turing machine. Let $A$ and $B$ two words, and $P(A)$ a word of ...
Guill Guill's user avatar
2 votes
1 answer
159 views

Problem of finding shortest proof - how complex is it? [closed]

For first order theories, is it correct that there is a brute force algorithm that tells us the shortest proof length for any given theorem ('length' means the sum of the lengths of the formulas that ...
Shawn W's user avatar
  • 59
0 votes
0 answers
52 views

Can a theorem determine its own complexity?

Much how Gödel spoke of the Incompleteness Theorems, can a theorem determine its own complexity? Namely, I haven't seen a concise proof of the following that is not possible to determine in the ...
Shawn W.'s user avatar
0 votes
0 answers
90 views

Conditional Kolmogorov complexity of an array of continuous variables

I know that conditional complexity is a measure that can only be applied to strings of discrete characters, but I'm curious if there's an analogue for continuous variables. For example, it's easy to ...
virtuolie's user avatar
  • 161
1 vote
1 answer
72 views

Does the uncomputability of Kolmogorov complexity follows from Rice Theorem?

I was reading the proof of uncomputability of Kolmogorov complexity by Li and Vitányi book and thinking if there isn't another way to do this simpler using Rice theorem. I came up with this argument. ...
Lost definition's user avatar
0 votes
1 answer
52 views

Is the Kolmogorov Complexity of 11…1 with even length L less than for the string 1010…10 of the same length?

We define the Kolmogorov Complexity to be independent of any particular programming language for bit string x as the length of the shortest string <M,w> where TM M on input w halts with x on its ...
Arthur Lubocce's user avatar
3 votes
0 answers
247 views

Formalization in PA in the Kritchman-Raz proof

In their paper Kritchman and Raz present a proof of Gödel's second theorem using Kolmogorov complexity. To make it work, they operate in some (weak) formal theory $T$ that incorporates some arithmetic,...
Jori's user avatar
  • 1,698
6 votes
1 answer
197 views

Recursion theoretic definition of Kolmogorov complexity

In Kikuchi's paper Kolmogorov complexity and the second incompleteness theorem the Kolmogorov Complexity (KC) of $x$ is defined s $$ K(x) = \mu e (\varphi_e(0) \simeq x) \, . $$ This seems to give ...
Jori's user avatar
  • 1,698
3 votes
2 answers
172 views

How to universalize $\text{Prov}(\ulcorner y < K(x)\urcorner) \to y < K(x)$ in a paper of Kikuchi

In Kikuchi's paper Kolmogorov complexity and the second incompleteness theorem he defines for $\Sigma_1$ binary predicates $R(x, y)$ the condition $$ \Gamma_{1}(R) \Leftrightarrow \forall x\forall y(R(...
Jori's user avatar
  • 1,698
5 votes
0 answers
407 views

The philosophical significance of Chaitin's Theorem

In a book review of Torkel Franzén's "Gödel’s Theorem: An Incomplete Guide to Its Use and Abuse" in the Notices the reviewer (Raatikainen) writes: Franzén also devotes a brief chapter to ...
Jori's user avatar
  • 1,698
3 votes
1 answer
240 views

The connection between Kolmogorov complexity and mathematical logic

We know that Kolmogorov complexity has connections to mathematical logic since it can be used to prove the Gödel incompleteness results (Chaitin's Theorem and Kritchman-Raz). Are there any other ...
Jori's user avatar
  • 1,698
1 vote
2 answers
60 views

question related to Kolmorogov Smirnov statistic.

Question related to Kolmogorov Smirnov statistics: If $F_n$ is the empirical distribution function for $n$ IID random variables with an unknown distribution function $F$, what does the random function ...
Math_Is_Fun's user avatar
1 vote
1 answer
115 views

The use of soundness in the Kritchman-Raz proof and Berry's paradox

In the Kritchman-Raz paper the authors recall Chaitin's proof of a version of the first incompleteness theorem (italics are mine): Chaitin’s incompleteness theorem states that for any rich enough ...
Jori's user avatar
  • 1,698
2 votes
1 answer
279 views

Kolmogorov complexity of a product of two numbers

In his book "Theoretical Computer Science", Juraj Hromkovic informally defines the Kolmogorov complexity $K(x)$ of a word $x$ consisting of zeros and ones as the binary length of the shortest Pascal ...
Frunobulax's user avatar
  • 6,589
1 vote
1 answer
128 views

A consequence of Chaitin's incompleteness theorem

According to Wikipedia due to Chaitin's incompleteness theorem, the output of any program computing a lower bound of the Kolmogorov complexity cannot exceed some fixed limit, which is independent of ...
Jori's user avatar
  • 1,698
0 votes
1 answer
46 views

Proving two different universal machine types give equivalent results in original Solomonoff induction paper

Solomonoff's original paper about Solomonoff induction contains the following (p. 18): Suppose $M$ to be a universal machine with binary input alphabet, and an output alphabet that is the same as ...
IssaRice's user avatar
  • 1,155
0 votes
0 answers
131 views

Martin-Löf randomness tests relative to conditional probability?

Background: Martin-Löf's way of defining randomness of finite strings (over a finite alphabet such as $\{0,1\}$) and infinite sequences uses a generalized notion of a statistical test. Often, when ...
Mars's user avatar
  • 1,338
0 votes
2 answers
52 views

Is there an algorithmic complexity measure that strikes a balance between regularity and randomness of a string?

If my understanding is correct, Kolmogorov complexity would assign the highest value (description length) to a totally random string, such as: abewdwflkweoasfksalsfnlka the lowest value to a ...
Alex Kinman's user avatar
4 votes
2 answers
193 views

Any examples of exact calculation of Kolmogorov Complexity??

First question: It is known that Kolmogorov Complexity (KC) is not computable (systematically). I would like to know if there are any "real-world" examples-applications where the KC has been computed ...
Robert_Lewis's user avatar
1 vote
0 answers
102 views

Bound on the Kolmogorov complexity of integers

I am reading Elements of Information Theory (Thomas M. Cover, Joy A. Thomas, 2nd edition) in which the following theorems are given (page 475--476): For any integer $n$ $$ K(n) \leq \log^* n + c. $$...
Holt's user avatar
  • 123
0 votes
1 answer
62 views

Probability distributions based on Kolmogorov complexity?

Suppose a human being randomly chooses a real number $x$ with $0<x<1$. It seems the probability of choosing $x$ is closely related to the Kolmogorov complexity of $x$. That is, a number like $0....
user avatar
2 votes
1 answer
251 views

Application of (Solomonoff) Algorithmic Probability formula?

Ray Solomonoff gives the Algorithmic Probability formula as, $$ P_M(x)=\sum_{i=1}^{\infty}2^{-|s_{i}(x)|} \tag{1} $$ ​​​If I understand the formula correctly, $M$ is a Turing machine ...
litmus's user avatar
  • 671
1 vote
2 answers
315 views

Proving a binary string of length i is less than or equal to $2^i$?

This is a problem I've gotten on my Graph Theory Homework, and I'm I'm not quite sure how to start off with proving it. The question is as follows: Let $\mathcal S$ be a finite collection of binary ...
Davyd Rickmann's user avatar
0 votes
1 answer
131 views

Motivation for Algorithmic Randomness Definition

Wikipedia gives this definition for algorithmic randomness in terms of Kolmogorov complexity: "Given a natural number c and a sequence w, we say that w is c-incompressible if $K(w) \geq |w|-c$. An ...
Halley's user avatar
  • 3
4 votes
2 answers
453 views

Uncomputability of Kolmogorov complexity

I have read different proofs of Kolmogorov Complexity Uncomputability but I fail to understand why the example below does not work. Certainly there is something important that I don't get. Could you ...
Benichon's user avatar
1 vote
0 answers
131 views

Deriving Probability Theory from Information Theory

In the paper "A Philosophical Treatise of Universal Induction" section 3 on Probability describes three different interpretations of probability theory: frequentist, objectivist, and subjectivist. I ...
arachnivore's user avatar
2 votes
0 answers
103 views

Average Kolmogorov complexity of an integer factorization

The other day I discovered the Hardy-Ramanujan theorem, which suggested to me that the Kolmogorov complexity of any factorization of some $n$, given $n$, is negligible, a claim I am looking to verify. ...
Dumaiu's user avatar
  • 89
3 votes
1 answer
78 views

What if the random variable are not IID, and we sum them?

Let $a_n > 0$ be decreasing with $\sum a_n^2=1$. Starting at the origin we do drunken random walk on the real line, with step size $a_1,a_2...$, so the total deviation is $\sum a_n^2=1$. If our ...
Dave's user avatar
  • 814
0 votes
0 answers
70 views

Normal number and Kolmogorov complexity

For real number $r$, infinite sequence of its digits in base 10, (I mean 1/9=>1,1,1,1,1,1,1,1,1,1,1,1.....) I heard that if this sequence is the random sequence in the sense of kolmogorov complexity ...
Lee.HW's user avatar
  • 148