<p>Let's assume there exists some "decidable" complexity $D(s)$ differs from Kolmogorov complexity $K(s)$ by shift, by factor or, more generally, by any decidable monotonic unbounded numerical function $f(n)$ such that $K(s) &gt; f(D(s))$.</p>

<p>As $D(s)$ is decidable, it is possible to choose (effectively) a sequence of strings $s_n$ such  that $f(D(s_n))&gt; \mathrm{vff}(n)$ where $\mathrm{vff}$ is some "very very fast growing function" such as $\exp(\exp(\exp(n)))$. </p>

<p>Suppose that we have $K(s_n) &gt; \mathrm{vff}(n)$, i.e. Kolmogorov complexity of string $s(n)$ grows fast with $n$. But index $n$ also identifies the string $s(n)$ and, therefore, may be treated as upper bound of $K(s_n)$ (with some const shift). Any number $n$ needs only $\log(n)$ bits to represent it, and this contradicts with fast growing of complexity of $K(s_n)$. </p>

<p>Thus for any decidable monotonic unbounded numerical function $f$, there exists strings $s$ such that $K(s) \not&gt; f(D(s))$.</p>

CC BY-SA 3.0
2011-07-06T19:39:39.353Z
2013-11-07T16:03:07.807Z
2013-11-07T16:03:07.807Z
user396672
<p>Uncomputability of general KC is a consequence of undecidability of halting problem over the class of machines used for KC. If we can decide the halting problem over the class of the machines then we can compute the KC of a given string according to them. Just run all machine and input pairs that halt up to the first one that outputs $x$, and then pick the shortest one.</p>

CC BY-SA 3.0
2011-07-06T21:47:34.900Z
2011-07-06T21:47:34.900Z
Kaveh
<p>We can think of Kolmogorov complexity of a string $x$ as the length of the shortest program $P$ and input $y$ such that $x = P(y)$. Usually these programs are drawn from some Turing-complete set (like $P$ might be the description of a Turing machine, or it could be a program in LISP or C). Even when we look at resource-bounded Kolmogorov complexity, we still look at Turing machines but with some bounds on their runtime or space usage. One of the consequences of this, is that the complexity of a string is undecidable. This seems like an awkward feature.</p>

<blockquote>
  <p>What happens if we use non-Turing complete models of computation to define Kolmogorov complexity?</p>
</blockquote>

<p>If we pick a restrictive enough model (say our model can only implement the identity), then the complexity of a string becomes decidable, although we also lose the invariance theorem. Is it possible to have a model strong enough to have complexity equal (upto a constant offset, or even a multiplicative factor) to the Turing-complete model, but weak enough to still allow the complexity of a string to be decidable? Is there a standard name for Kolmogorov complexity with non-Turing complete models of computation? Where could I read more about this?</p>

CC BY-SA 3.0
2011-07-06T20:19:20.153Z
a note: both time bounded and space bounded Kolmogorov complexities are computable
Marzio De Biasi
<reference-request><computability><kolmogorov-complexity>
Kolmogorov complexity with weak description languages
Artem Kaznatcheev
# Kolmogorov complexity with weak description languages

(Asked by: username_0 on 2011-07-06)

We can think of Kolmogorov complexity of a string $x$ as the length of the shortest program $P$ and input $y$ such that $x = P(y)$. Usually these programs are drawn from some Turing-complete set (like $P$ might be the description of a Turing machine, or it could be a program in LISP or C). Even when we look at resource-bounded Kolmogorov complexity, we still look at Turing machines but with some bounds on their runtime or space usage. One of the consequences of this, is that the complexity of a string is undecidable. This seems like an awkward feature.

> What happens if we use non-Turing complete models of computation to define Kolmogorov complexity?

If we pick a restrictive enough model (say our model can only implement the identity), then the complexity of a string becomes decidable, although we also lose the invariance theorem. Is it possible to have a model strong enough to have complexity equal (upto a constant offset, or even a multiplicative factor) to the Turing-complete model, but weak enough to still allow the complexity of a string to be decidable? Is there a standard name for Kolmogorov complexity with non-Turing complete models of computation? Where could I read more about this?

**Tags:** reference-request, computability, kolmogorov-complexity
> **Comments:**
> **username_1**: a note: both time bounded and space bounded Kolmogorov complexities are computable  

---

## 2 answers

### Answer by username_2 on 2011-07-06. Score: 5 | Accepted answer

Let's assume there exists some "decidable" complexity $D(s)$ differs from Kolmogorov complexity $K(s)$ by shift, by factor or, more generally, by any decidable monotonic unbounded numerical function $f(n)$ such that $K(s) > f(D(s))$.

As $D(s)$ is decidable, it is possible to choose (effectively) a sequence of strings $s\_n$ such that $f(D(s\_n))> \mathrm{vff}(n)$ where $\mathrm{vff}$ is some "very very fast growing function" such as $\exp(\exp(\exp(n)))$.

Suppose that we have $K(s\_n) > \mathrm{vff}(n)$, i.e. Kolmogorov complexity of string $s(n)$ grows fast with $n$. But index $n$ also identifies the string $s(n)$ and, therefore, may be treated as upper bound of $K(s\_n)$ (with some const shift). Any number $n$ needs only $\log(n)$ bits to represent it, and this contradicts with fast growing of complexity of $K(s\_n)$.

Thus for any decidable monotonic unbounded numerical function $f$, there exists strings $s$ such that $K(s) \not> f(D(s))$.


---

### Answer by username_3 on 2011-07-06. Score: 2

Uncomputability of general KC is a consequence of undecidability of halting problem over the class of machines used for KC. If we can decide the halting problem over the class of the machines then we can compute the KC of a given string according to them. Just run all machine and input pairs that halt up to the first one that outputs $x$, and then pick the shortest one.


---

