Timeline for Kolmogorov complexity of a random string conditioned on another random string
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2017 at 23:40 | comment | added | user12859 | Well, your K-equality is definitely not independent of additive O(1) changes in K, and I don't see any argument for why such changes in K can't infinitely-often change the probability by more than, for example, 1/9. | |
| May 8, 2017 at 23:37 | comment | added | P. Trinli | Sorry!! $O(1)$ was what I meant. | |
| May 8, 2017 at 23:31 | comment | added | user12859 | Do you have a citation or argument for "re-defining the universal machine changes $K$ by an additive constant" ? I thought nothing significantly better was known than "changes $K$ by an additive O(1)" . | |
| May 8, 2017 at 20:31 | comment | added | P. Trinli | Ricky, I don't think this matters. I suspect the probability is zero in the limit of large n (this is not clear to me however). Since re-defining the universal machine changes $K$ by an additive constant, the asymptotics will stay the same. It's really the asymptotics I am after, and I would be surprised if it depended on the reference machine. Not sure how to show this though... | |
| May 8, 2017 at 20:10 | comment | added | user12859 | What description language does your K use? | |
| May 8, 2017 at 17:13 | history | asked | P. Trinli | CC BY-SA 3.0 |