Questions tagged [kolmogorov-complexity]
Kolmogorov complexity concerns the size of the shortest program that generates a given string.
101
questions
0
votes
0
answers
7
views
Measurement for complexity of a deterministic binary sequence
Consider binary sequences with length $n$, is there any natural complexity measure of a class of such sequences, besides the kolmogorov complexity?
A sequence with all 0 or all 1 definitely has low ...
- 1
1
vote
1
answer
41
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 ...
- 239
1
vote
1
answer
53
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(\...
- 239
0
votes
1
answer
70
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:
...
- 3
0
votes
0
answers
17
views
How to measure Kolmogorov complexity?
I need a function/algorithm which can measure and and order numbers in a hierarchical way, e.g. 32-bit numbers, from the highest to the lowest Kolmogorov complexity.
Is it possible to do it somehow ...
- 149
3
votes
1
answer
29
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.
...
- 151
1
vote
0
answers
31
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 ...
- 21
2
votes
3
answers
57
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:
...
- 218
0
votes
0
answers
14
views
Do there exist any known translations between tag systems with coprime deletion numbers?
Tag systems are often used in the study of computation and as a relatively accessible tool for proving the universality of small computational models. A tag system with deletion number $v=2$ (also ...
- 4,941
1
vote
1
answer
65
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 ...
- 21
0
votes
0
answers
13
views
Kernel density estimation and kolmogorov complexity
Recently, I decided to revisit Cover and Thomas, and yesterday I encountered a very interesting passage in the chapter on Kolmogorov complexity:
What does this "different procedure" look ...
- 1,025
2
votes
1
answer
125
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 ...
- 57
0
votes
0
answers
51
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 ...
- 13
0
votes
0
answers
47
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 ...
- 51
1
vote
1
answer
52
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. ...
- 756
0
votes
1
answer
42
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 ...
3
votes
0
answers
219
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,...
- 1,558
6
votes
1
answer
137
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 ...
- 1,558
3
votes
2
answers
153
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(...
- 1,558
5
votes
0
answers
254
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 ...
- 1,558
2
votes
1
answer
180
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,558
1
vote
2
answers
40
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 ...
- 674
1
vote
1
answer
94
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
...
- 1,558
2
votes
1
answer
121
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 ...
- 6,228
1
vote
1
answer
81
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 ...
- 1,558
0
votes
1
answer
40
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 ...
- 963
0
votes
0
answers
50
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 ...
- 1,124
0
votes
2
answers
41
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 ...
- 103
4
votes
2
answers
138
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 ...
- 43
1
vote
0
answers
48
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. $$...
- 123
0
votes
1
answer
40
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....
user485260
2
votes
1
answer
177
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 ...
- 641
1
vote
2
answers
215
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
1
answer
101
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 ...
- 3
2
votes
2
answers
334
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 ...
- 23
1
vote
0
answers
40
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 ...
- 143
1
vote
0
answers
111
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 ...
- 11
2
votes
0
answers
87
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. ...
- 89
3
votes
1
answer
73
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 ...
- 784
0
votes
0
answers
67
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 ...
- 138
0
votes
1
answer
60
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 ...
- 416
0
votes
0
answers
92
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 ...
- 416
5
votes
1
answer
237
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 "...
user361949
2
votes
1
answer
105
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 ...
- 35
0
votes
2
answers
117
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 ...
- 17.2k
11
votes
0
answers
359
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 ...
- 17.2k
2
votes
1
answer
158
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 ...
- 17k
0
votes
1
answer
63
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 ...
- 303
1
vote
0
answers
64
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 ...
- 267
2
votes
0
answers
153
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 ...
- 320