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
0answers
17 views

Intuition of Kolmogorov dimension in metric space

What is the intuition of Kolmogorov dimension as defined below? Let $N(\mathcal{F}, \alpha, \|\cdot\|_2)$ be the $\alpha$-covering number of $\mathcal{F}$ with respect to the $\|\cdot\|_2$-norm. ...
3
votes
0answers
94 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,...
5
votes
0answers
106 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 ...
3
votes
2answers
128 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(...
5
votes
0answers
168 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 ...
2
votes
1answer
155 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 ...
1
vote
2answers
29 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 ...
1
vote
1answer
76 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 ...
2
votes
1answer
50 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 ...
1
vote
1answer
65 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 ...
0
votes
1answer
23 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 ...
0
votes
0answers
27 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 ...
0
votes
2answers
35 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 ...
3
votes
2answers
75 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 ...
1
vote
0answers
28 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. $$...
0
votes
1answer
32 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....
1
vote
1answer
122 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 ...
1
vote
2answers
137 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 ...
0
votes
1answer
83 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 ...
1
vote
2answers
142 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 ...
1
vote
0answers
32 views

Is there an analogue of Kolmogorov Complexity for Strongly Normalizing Languages?

The definition of Kolmogorov Complexity relies upon the definition of Turing Complete description languages. Famously, Kolmogorov Complexity is uncomputable and akin to the halting problem. I have two ...
1
vote
0answers
93 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 ...
2
votes
0answers
70 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. ...
3
votes
1answer
65 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 ...
0
votes
0answers
64 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 ...
0
votes
1answer
47 views

Showing that $3/4$ of all words over $\{0,1\}^n$ have $K(w) \geq n-2$

$K(n)$ is the kolmogorov-complexity of a word n. I know that for every $n$, there's at least one word $w_{n}$ of length $n$, such that $k(w_{n}) \geq n$. There's $2^n$ words in $\{0,1\}^n$, how can I ...
0
votes
0answers
44 views

Proving that at least half of all words with length bigger than $n$ are not compressible.

We say that a word is not compressible, if it's Kolmogorov-Complexity is bigger than the length of the word. We know that for every natural number $n$, we have at least one word which is not ...
5
votes
1answer
130 views

Kolmogorov complexity vs. intuitive notion of simplicity

Consider the infinite sequence $1,2,4,8,16,...$ If one were asked how the sequence continues the answer would likely be $32,64,..,2^k,..$ and one would implicitly assume the question to be about the "...
2
votes
1answer
100 views

Is it impossible to prove one very large integer is bigger than another?

We have two integers $i$ and $j$, and the difference between them is large enough such that $(i >j) \rightarrow (K(i) > K(j))$. $K$ is the Kolmogorov complexity function. We have a set of ...
0
votes
2answers
91 views

Terminology for the Kolmogorov complexity of computable functions, sets, reals?

The Kolmogorov complexity of a binary string can be defined in terms of a prefix-free binary encoding of Turing machines that operate on a binary tape. Then if $x$ is a binary string, $K(x)$ is the ...
11
votes
0answers
344 views

Does Chaitin's constant have infinitely many prime prefixes?

Define $f(n) = \lfloor 2^n \cdot \Omega \rfloor$, that is, $f(n)$ is the first $n$ bits of Chaitin's constant interpreted as a number written in binary. I am trying to figure out if $f(n)$ can have ...
2
votes
1answer
102 views

The problem $K(x) \le K(y)$ is not decidable for Kolmogorov complexity $K$

Let $X$ be some finite alphabet. Given $(x,y) \in X^{\ast}\times X^{\ast}$, how to show that $K(x) \le K(y)$ is not decidable? I know that $K(x) \le k$ for some fixed $k$ is not decidable, so I tried ...
0
votes
1answer
53 views

Strong Law of Large Numbers with different n

In this problem, we want to show that $\frac{X_1+...+X_n}{\sqrt{n}(log(n))^{\frac{1}{2}+\epsilon}}$ converges to 0 almost surely as n approaches infinity. We know mean = 0 and variance = 1 and that ...
1
vote
0answers
55 views

Kolmogorov complexity measure of a formal system

Each formal system can be encoded in a binary string. For instance, you can use the input string that a pre-specified Turing machine needs in order to enumerate all the theorems in a theory in the ...
2
votes
0answers
131 views

Simplest Possible Universal Turing Machine

Consider the Game of Life. Given an infinite two-dimensional plane to run the Game on, and an infinite amount of "matter" so that one can give the automata any initial conditions one wishes, it is ...
3
votes
1answer
191 views

Are there strings with known Kolmogorov complexity?

I just looked into Kolmogorov complexity today and it appears to me that for a binary string of length $1$ (ex. '$0$') the Kolmogorov complexity must be $0$. It follows that Kolmogorov complexity ...
0
votes
1answer
113 views

Is it meaningful to search for “elegant” representations of mathematical objects?

For centuries we struggled with the concept of spatial rotations. We used to represent them in many different ways: mostly, Euler Angles and matrices. Those all had drawbacks and failed in specific ...
2
votes
0answers
361 views

$K(xy)\leq K(x)+K(y) +c$?

Could anyone show that for any $c$, some strings $x$ and $y$ exist, where $K(xy)>K(x)+K(y)+c$? Here $K(x)$ is the Kolmogorov complexity. I already know that $K(xy) \leq 2K(x) + K(y) +c$ and $K(xy) \...
1
vote
1answer
110 views

What is the shortest LOOP program that outputs 2016? [closed]

Use a minor restriction of the LOOP language described under Wikipedia's "LOOP (Programming Language)". The restriction is to eliminate constants. So, the language contains increment: $x_i++$, ...
0
votes
1answer
72 views

not any computable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
2
votes
1answer
152 views

set of Kolmogorov-random strings is co-re

given RC = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings. How can I show that RC is co-re I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random Strings?...
3
votes
1answer
155 views

Abstract machines that compute primitive recursive functions

What it the simplest (least powerful) abstract machine that can compute primitive recursive sets, i.e. sets whose characteristic or indicator function is primitive recursive? $$f:\mathbb{N}\...
1
vote
0answers
52 views

Understanding AI through a complexity function

I've been trying to understand in light of a few apparent paradoxes for me. It appears reasonable that we could prove any mathematical problem that has a well defined answer can be solved by a ...
0
votes
1answer
36 views

Kolmogorov complexity when no language is specified

The statement of theorem 3 in "A frequentist understanding of sets of measures" by Fierens, Rêgo, and Fine (pdf available here) requires that the Kolmogorov complexity of a certain function be less ...
3
votes
0answers
926 views

chinese reminder theorem (CRT) time complexity

Let p1,...pk be the k first prime numbers. Denote p1*...*pk by n. We want to find x mod n, for that asume we found x mod pi for i in {1,...,k} , then use CRT to observe x mod n. What is the lowest (...
0
votes
1answer
34 views

Computability for equality in Kolmogorov complexity?

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, ...
0
votes
1answer
112 views

Is the Kolmogorov complexity of a number always its logarithm?

if I have a natural number $a(n,m)$ that depends on some $n$ and $m$, where $m$ is fixed, isn't then the Kolmogorov complexity of it simply its logarithm?
1
vote
1answer
89 views

Proof of a classical Theorem of Martin-Löf on complexity dips for Kolmogorov complexity,

I have a question on the first Theorem from the article Complexity of Oscillations in Infinite Binary Sequences by P. Martin-Löf, which could be downloaded from the publisher or from here. Theorem ...
1
vote
1answer
45 views

Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity

Denote by $C(n)$ the plain Kolmogorov complexity of $n$ and the length of a binary encoding of $n$ by $l(n)$, why do we have $$ C(n\mid l(n)) \ge C(n) - C(l(n))? $$ If I have a shortest program $p$ ...
2
votes
0answers
23 views

Each recursive approximating sequence for Kolmogorov complexity is not uniform

Denote the plain Kolmogorov complexity by $C(x)$. Let $\phi(t,x)$ be a recursive function and $\lim_{t\to\infty} \phi(t,x) = C(x)$ for all $x$. For each $t$ define $\psi_t(x) := \phi(t,x)$ for all $...