Questions tagged [kolmogorov-complexity]
The kolmogorov-complexity tag has no usage guidance.
17
questions
1
vote
0
answers
94
views
A two-colouring of a complete graph over the set of incompressible strings
A two-coloring is done over the (infinite) set all incompressible strings (in some chosen alphabet); such that, an edge between two strings is blue if and only if, the strings are of equal lengths and ...
- 841
2
votes
2
answers
910
views
Using Kolmogorov complexity to measure difficulty of problems?
We call the natural number $n$ a partition number $\iff$
$$
\exists d | n: \gcd\left(d,\frac{n}{d}\right)=1 \text{ and } \Omega(d) = \Omega\left(\frac{n}{d}\right)\;,
$$
where $\Omega$ counts the ...
- 2,102
9
votes
2
answers
2k
views
Why do almost all points in the unit interval have Kolmogorov complexity 1?
Re-posted from math.stackexchange as I did not get any answers there.
I am reading
Jin-yi Cai, Juris Hartmanis, On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, ...
- 297
2
votes
0
answers
66
views
Kolmogorov $\epsilon$-entropy, $n$-width, and $\epsilon$-capacity and applications
What is the relationship between Kolmogorov $\epsilon$-entropy, Kolmogorov $n$-width, and Kolmogorov $\epsilon$-capacity of a set $M$ in a metric space $X$? (The $\epsilon$-capacity here is the ...
- 131
5
votes
2
answers
700
views
Kolmogorov's approach to probability theory
Question:
Did Kolmogorov develop a set of axioms for probability theory motivated by Algorithmic Information Theory in the 1960s?
Context:
In 1965, Andrey Kolmogorov considered three approaches to ...
- 3,777
4
votes
1
answer
209
views
What journal(s) do you recommend for submitting a paper on a topic that spans information theory and estimation theory?
I've written a paper that a) demonstrates an equivalence between conditional complexity $K$($Y$|$X$) in information theory and the random component of an effect size estimate $r_{xy}$, and then b) ...
- 139
5
votes
2
answers
216
views
Examples of different levels of the ergodic hierachy (specifically: weakly mixing & merely ergodic)
I am interested in generalizing some aspects of the ergodic hierarchy (of classical dynamical systems) to quantum theory. However, while I understand the definitions of the different levels of the ...
- 649
5
votes
2
answers
295
views
Relative Kolmogorov complexity
Given a natural number $n$ denote by $K(n)$ its Kolmogorov complexity.
Let $m, n$ be two natural numbers. The relative Kolmogorov complexity $K_m(n)$ of $n$ with respect to $m$ is the minimum length ...
- 59
5
votes
3
answers
451
views
Is there a quantum analog of Kolmogorov Complexity?
Kolmogorov Complexity (interpreted in terms of shortest program computing a string) and Shannon Entropy are quite similar.
Since there is a quantum entropy is it reasonable to ask if there is quantum ...
- 13.5k
1
vote
0
answers
101
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,...
- 179
8
votes
0
answers
428
views
Alternative definition of Kolmogorov complexity
In Kikuchi's paper Kolmogorov complexity and the second incompleteness theorem the Kolmogorov Complexity (KC) of $x$ is defined as
$$ K(x) = \mu e (\varphi_e(0) \simeq x) \, . $$
This seems to give ...
- 179
11
votes
3
answers
685
views
natural metrics for proof length
I am trying to make my way into Homotopy Type Theory(HoTT) where a mathematician may view proofs as paths. Intuitively, this leads me to the idea of a metric on the space of mathematical propositions. ...
- 3,777
6
votes
1
answer
441
views
The connections between Kolmogorov complexity and mathematical logic
We know that Kolmogorov Cmplexity (KC) 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 ...
- 179
5
votes
1
answer
720
views
Books to develop a deep understanding of Algorithmic Information Theory?
I'm mathematical physicist working with hydrodynamics modelling. Recently, I had to turn to modelling of flows with particles and some questions I have I think are related to Algorithmic Information ...
2
votes
1
answer
310
views
The fastest growing function of given complexity
Let $f$ be a computable function $\mathbb{N} \to \mathbb{N}$
be a computable function. Since a program of a computable function is a finite object we can define plain Kolmogorov complexity of $f$ (we ...
- 2,663
5
votes
0
answers
294
views
The expressiveness of functions computable on trees
Motivation:
Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...
- 3,777
4
votes
1
answer
659
views
Proof that dynamical systems with bounded Kolmogorov complexity can't emulate all Turing machines
Motivation:
During a discussion with neuroscientists the question arose as to whether the human brain may emulate any Turing machine. If we assume that animal brains may be modelled as deterministic ...
- 3,777