<p>In Kikuchi's paper <a href="http://www.kurims.kyoto-u.ac.jp/%7Ekyodo/kokyuroku/contents/pdf/0912-3.pdf" rel="nofollow noreferrer">Kolmogorov complexity and the second incompleteness theorem</a> the Kolmogorov Complexity (KC) of <span class="math-container">$x$</span> is defined as</p>
<p><span class="math-container">$$ K(x) = \mu e (\varphi_e(0) \simeq x) \, , $$</span></p>
<p>the smallest <span class="math-container">$e$</span> such that the <span class="math-container">$e$</span>-th program (in some enumeration) outputs <span class="math-container">$x$</span> on input <span class="math-container">$0$</span>. This seems to give exponentially larger outcomes then the more common (rough) definition of <span class="math-container">$K(x)$</span> as &quot;the length of the smallest computer program running on some fixed universal TM that returns <span class="math-container">$x$</span>&quot;. 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?</p>
<p><sub>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.</sub></p>

CC BY-SA 4.0
2020-09-30T19:53:26.450Z
Would you mind editing the post to explain the notation ($\mu$, $e$, $\phi_e(0)$)?
Neal Young
CC BY-SA 4.0
2020-09-30T22:51:39.803Z
@Neal I've edited the question. Is it OK like this?
Jori
CC BY-SA 4.0
2020-10-01T12:44:09.130Z
Thanks, yes.  [I find the notation is still confusing, but the added comment makes clear what it means.]
Neal Young
CC BY-SA 4.0
2020-10-01T13:11:27.760Z
@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".
Jori
CC BY-SA 4.0
2020-10-07T19:05:25.580Z
@Jori NOTE Please, I can't access the paper,  "Forbidden"
William Martens
CC BY-SA 4.0
2020-10-08T11:18:00.377Z
I can't access the paper you provided, http://www.kurims.kyoto-u.ac.jp/%7Ekyodo/kokyuroku/contents/pdf/0912-3.pdf
William Martens
CC BY-SA 4.0
2020-10-08T11:20:46.663Z
@William I have no idea why. The link works fine for me. You can find it here as well: https://link.springer.com/article/10.1007/s001530050074. If you have university access.
Jori
CC BY-SA 4.0
2020-10-08T11:21:28.790Z
No worries, Ill find it another way;  Sorry for being confusing - Then It must be just me, But no worries thanks anyway :)
William Martens
<lo.logic><kolmogorov-complexity>
Alternative exponential definition of Kolmogorov complexity
Jori
# Alternative exponential definition of Kolmogorov complexity

(Asked by: username_0 on 2020-09-28)

In Kikuchi's paper [Kolmogorov complexity and the second incompleteness theorem](http://www.kurims.kyoto-u.ac.jp/%7Ekyodo/kokyuroku/contents/pdf/0912-3.pdf) 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.

**Tags:** lo.logic, kolmogorov-complexity

> **Comments:**
> **username_1**: Would you mind editing the post to explain the notation ($\mu$, $e$, $\phi_e(0)$)?  
> **username_0**: @Neal I've edited the question. Is it OK like this?  
> **username_1**: Thanks, yes.  [I find the notation is still confusing, but the added comment makes clear what it means.]  
> **username_0**: @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".  
> **username_2**: @username_0 NOTE Please, I can't access the paper,  "Forbidden"  
> **username_2**: I can't access the paper you provided, http://www.kurims.kyoto-u.ac.jp/%7Ekyodo/kokyuroku/contents/pdf/0912-3.pdf  
> **username_0**: @William I have no idea why. The link works fine for me. You can find it here as well: https://link.springer.com/article/10.1007/s001530050074. If you have university access.  
> **username_2**: No worries, Ill find it another way;  Sorry for being confusing - Then It must be just me, But no worries thanks anyway :)  

---

## 0 answers

