8
$\begingroup$

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

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?

$\endgroup$
11
  • 3
    $\begingroup$ Can you explain the notation in the definition? I think it's "smallest $e$ such that the $e$th program (in some enumeration) outputs $x$ on input $0$." $\endgroup$
    – usul
    Sep 22, 2020 at 22:41
  • $\begingroup$ @usul That's how I read it as well, with the extra condition that this $e$th program should terminate, of course. Kikuchi doesn't say any more about it. $\endgroup$
    – Jori
    Sep 22, 2020 at 23:51
  • $\begingroup$ It does seem to me that Kikuchi is using an exponentiated version of regular Kolmogorov complexity. For example, he says things like "we say a number $x$ is random if $x \le K(x)$", which makes sense if we think of an encoding of a number as needing about $\log_2 n$ bits. I have not seen this version in other places, but since exponentiation is monotonic, I don't see how it would change things much. $\endgroup$
    – Artemy
    Sep 24, 2020 at 3:45
  • $\begingroup$ Can you specify which “usual theorems” you have in mind? This would make the question more precise and concrete. $\endgroup$
    – user76284
    Sep 24, 2020 at 4:13
  • 1
    $\begingroup$ Kikuchi mentions Odifreddi's Classical Recursion Theory (North-Holland, 1989) as the source of that particular definition, and that's also the earliest occurrence I know of. Another paper using the same definition, also citing Odifreddi's book, is P. Raatikainen's On interpreting Chaitin's incompleteness theorem (JPL 27:569-586, 1998). $\endgroup$
    – user103227
    Sep 29, 2020 at 14:54

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.