Questions tagged [kolmogorov-complexity]
Kolmogorov complexity concerns the size of the shortest program that generates a given string.
1
vote
0answers
22 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
25 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
94 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
78 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 ...
0
votes
1answer
48 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
62 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 ...
0
votes
0answers
14 views
Is it possible to compute the Kolmogorov complexity of a polynomial over ℚ?
For the sake of making the above well-defined, let's suppose our description language is arithmetic expressions in Polish notation with symbols 0 1 x + - * / ^. If ...
1
vote
0answers
26 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
76 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 ...
1
vote
0answers
55 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
59 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
58 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
40 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
39 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
105 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
96 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
60 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
318 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
0answers
57 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
44 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
50 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
109 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 ...
2
votes
1answer
150 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
106 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
228 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
105 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
69 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
137 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
102 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
51 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
32 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
766 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
31 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
98 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
67 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
40 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 $...
2
votes
0answers
37 views
Kolmogorov complexity of substring if string is divided according to rule
Denote the plain Kolmogorov complexity of a string $u$ by $C(u)$. Now let $u$ be a string of length $n$ with $C(u) \ge n - O(1)$ and suppose $u = u_1 \cdots u_{\log n}$, a subdivision of the string. ...
1
vote
0answers
46 views
On Kolmogorov complexity of first and last half of a string
Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy
$C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$.
Any ideas how to ...
1
vote
0answers
48 views
Kolmogorov complexity, no description mechanism can improve on additively optimal/universal one infinitely often
In An Introduction to Kolmogorov Complexity and Its Applications explaining the notion of additively optimal or universal it is written:
The key point is not that the universal description method ...
4
votes
0answers
72 views
Is there any research on Diophantine Approximation with computable numbers
I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
0
votes
0answers
31 views
How to prove equality $K(x, K(x)) = K(x) + O(1) $?
It is needed to prove that $K(x, K(x))=K(x) + O(1)$ where $K$ means Kolmogorov complexity.
I think the equality is true because when we find Kolmogorov complexity of $x$ we already knows $K(x)$ and ...
0
votes
1answer
85 views
Proof of an inequality about Kolmogorov complexity of two words.
It is needed to prove an existing of such constant C that for any words $x$,$y$
$K(x,y) \le K(x) + K(y) + log(|x|+|y|) + C$
(K is Kolmogorov complexity)
I tried to prove it by using next true ...
2
votes
0answers
42 views
Kolmogorov complexity inequality
Prove, that KP (x) ≤ KS (x) + log KS(x) + 2 log log KS (x) + O(1).
Please tell me in which direction to think.
1
vote
0answers
34 views
Optimal Kolmogorov complexity
Let computable function U is the best way to describe to Kolmogorov complexity. Prove that the mapping V, determined crucial for any word p as V (p) = U (U (p)), is also optimal
way to describe the.
...
1
vote
0answers
89 views
Kolmogorov complexity of a computer?
Warning: Vague, unclear question ahead. Proceed at your own risk.
The Shannon entropy and Kolmogorov complexity give you in broad informal terms how unpredictable a string is and to what degree the ...
2
votes
0answers
108 views
Does a random binary sequence almost always have a finite number of prime prefixes?
Does a random binary sequence almost always have a finite number of prime prefixes?
Specifically, let $x = \sum_{1 \le i}{2^{-i} \cdot x_i}$ with $x_i \in \{0,1\}$ be a random real in $[0,1)$, $X_i = ...
5
votes
1answer
1k views
Relationship between compression, shannon entropy and kolmogorov complexity
I have read that the Shannon Entropy is used as a bound for the compressibility of a message, for example here 1 it says "In other words, the best possible lossless compression rate is the entropy ...
0
votes
1answer
128 views
Kolmogorov complexity of an algorithm?
I've read that Kolmogorov comlexity is about calculating the least number of bits needed to describe a string or other mathematical objects.
Does 'other mathematical objects' include algorithms too?
...
5
votes
1answer
190 views
Prove that bitstrings with 1/0-ratio different from 50/50 are compressable
I'm looking for a proof, that
$$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$
with $n>0$, $0 \le \lambda \le 1/2$ and $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] ...
