Kolmogorov complexity with weak description languages

Question

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?

Answer 1

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 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.