Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Soviet license plate game and Kolmogorov complexity

johndcook.com

Post reply on HN
Print view View original

31–34 of 34 posts

Re: The Soviet license plate game and Kolmogorov complexity

#31

Post by daveFNbuck »

kryptiskt wrote: post #15
Simon_says wrote: post #9

> In theory you can enumerate all Turing machines of a given length, or all Python programs of a given length, and find the shortest one that does a given task, but the list grows exponentially with length. That works as long as you solve the halting problem first.

You don't have to do anything impossible, just something exceedingly impractical. Because we know that the function doesn't halt if its runtime exceeds the busy beaver number for that length. Now, we will obviously not know that for any non-trivial length, but in theory it's fine.

> Now, we will obviously not know that for any non-trivial length, but in theory it's fine.

It's not fine in theory because we can't know the busy beaver number for any Turing machine larger than the one doing the enumeration.

Re: The Soviet license plate game and Kolmogorov complexity

#33

Post by yters »

Annatar wrote: post #11

"In theory you can enumerate all Turing machines of a given length, or all Python programs of a given length, and find the shortest one that does a given task, but the list grows exponentially with length." Can it be proven that the shortest program is always the fastest? This is the problem I had when studying mathematics and still have with mathematics to this day: mathematics when stripped and laid bare is just cl…

In most cases the shortest program is the fastest, because most bitstrings are random, and the shortest program just prints the bitstring.

On the other hand, for compressible bitstrings, the shortest program is most likely not going to be the fastest, because you need at least one operation to output each final bit, so since the shortest program is going to be doing more than just printing the output, it's probably going to take longer than just printing the output.

Re: The Soviet license plate game and Kolmogorov complexity

#34

Post by Simon_says »

kryptiskt wrote: post #15
Simon_says wrote: post #9

> In theory you can enumerate all Turing machines of a given length, or all Python programs of a given length, and find the shortest one that does a given task, but the list grows exponentially with length. That works as long as you solve the halting problem first.

You don't have to do anything impossible, just something exceedingly impractical. Because we know that the function doesn't halt if its runtime exceeds the busy beaver number for that length. Now, we will obviously not know that for any non-trivial length, but in theory it's fine.

You can't know the busy beaver number without solving the halting problem.
Post reply on HN