# #StackBounty: #lo.logic #kolmogorov-complexity Alternative exponential definition of Kolmogorov complexity

### Bounty: 50

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

the smallest $$e$$ such that the $$e$$-th program (in some enumeration) outputs $$x$$ on input $$0$$. This seems to give exponentially larger outcomes then the more common (rough) definition of $$K(x)$$ as "the length of the smallest computer program running on some fixed universal TM that returns $$x$$". How does Kikuchi’s definition match up with the usual KC definition? Is this a common alternative? Does any major result in KC change/not work under this new definition, or can we just move everything by an exponent and rely on its monotonicity?

This is a cross post from MO. Since it isn’t being answered there (even after setting a bounty), it was suggested I try asking it here.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.