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

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ Would you mind editing the post to explain the notation ($\mu$, $e$, $\phi_e(0)$)? $\endgroup$
    – Neal Young
    Sep 30, 2020 at 19:53
  • $\begingroup$ @Neal I've edited the question. Is it OK like this? $\endgroup$
    – Jori
    Sep 30, 2020 at 22:51
  • 1
    $\begingroup$ Thanks, yes. [I find the notation is still confusing, but the added comment makes clear what it means.] $\endgroup$
    – Neal Young
    Oct 1, 2020 at 12:44
  • 1
    $\begingroup$ @Neal I think that's because it's (standard) recursion theoretic notation (for logicians), but not standard for theoretical computer scientists (right?). One thing to note is that someone over at MO pointed out that the definition originates from Odifreddi's Classical Recursion Theory. The notation is also used in P. Raatikainen's "On interpreting Chaitin's incompleteness theorem". $\endgroup$
    – Jori
    Oct 1, 2020 at 13:11
  • $\begingroup$ @Jori NOTE Please, I can't access the paper, "Forbidden" $\endgroup$
    – William Martens
    Oct 7, 2020 at 19:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.