#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!!!

Leave a Reply

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