Questions tagged [kolmogorov-complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5
votes
3answers
348 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 ...
1
vote
0answers
84 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,...
8
votes
0answers
375 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 ...
9
votes
2answers
500 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. ...
5
votes
1answer
277 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 ...
4
votes
1answer
185 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
1answer
244 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 ...
5
votes
0answers
268 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
votes
1answer
520 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 ...