Suppose you had a function K(x) that took an arbitrarily string x as input and returned the length of the shortest program that outputs that string. That number is called the Kolmogorov complexity.
Suppose the length of the source code for K is n bytes. I write the following program: while (K(x) < n+1000) ++x; print(x); where ++x interprets the string as a binary number and adds 1. The loop exits with the first x with Kolmogorov complexity of at least n + 1000. Except it was output by a program of length n + 36 bytes. -- Matt Mahoney, [email protected] On Thu, Nov 20, 2025, 4:37 PM John Rose via AGI <[email protected]> wrote: > On Thursday, November 20, 2025, at 3:52 PM, Matt Mahoney wrote: > > Are you claiming to have solved Kolmogorov complexity? > > > There are some serious quantum breakthroughs on prime numbers lately... > kinda makes you wonder... > *Artificial General Intelligence List <https://agi.topicbox.com/latest>* > / AGI / see discussions <https://agi.topicbox.com/groups/agi> + > participants <https://agi.topicbox.com/groups/agi/members> + > delivery options <https://agi.topicbox.com/groups/agi/subscription> > Permalink > <https://agi.topicbox.com/groups/agi/T7ff992c51cca9e36-M3c39c237d3108724392c0538> > ------------------------------------------ Artificial General Intelligence List: AGI Permalink: https://agi.topicbox.com/groups/agi/T7ff992c51cca9e36-M0cd901e5e7e5ea944717f520 Delivery options: https://agi.topicbox.com/groups/agi/subscription
