Kolmogorov complexity with weak description languages 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?
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))$.

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

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

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