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

11–20 of 34 posts

Re: The Soviet license plate game and Kolmogorov complexity

#11

Post by Annatar »

"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 clever transformations, "pouring from hollow into empty", as the old folks' saying goes. What is or are the practical applications of Kolmogorov complexity, how might I be able to turn this to my advantage?

Re: The Soviet license plate game and Kolmogorov complexity

#12

Post by aboutruby »

> √74 = sec arctan sec arctan … √44.

He meant "sec arctan sec arctan … √74 = √44." (sent him a message)

Also why not just applying the power 0 (assuming numbers are different than 0) both sides. Would be a school-level operation and very likely the shortest.

Re: The Soviet license plate game and Kolmogorov complexity

#13

Post by SamReidHughes »

aboutruby wrote: post #12

> √74 = sec arctan sec arctan … √44. He meant "sec arctan sec arctan … √74 = √44." (sent him a message) Also why not just applying the power 0 (assuming numbers are different than 0) both sides. Would be a school-level operation and very likely the shortest.

You can't write down new numbers in the formula.

Re: The Soviet license plate game and Kolmogorov complexity

#14

Post by gpm »

FartyMcFarter wrote: post #7

> 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. Another problem with this strategy is that it generally requires solving the halting problem: you can only know whether a program "does a given task" when you know whether it halts or not.

That's only true if you care about knowing when you are done enumerating.

The definition of enumeration commonly used in computability does not require that you know when you are done enumerating.

Re: The Soviet license plate game and Kolmogorov complexity

#15

Post by kryptiskt »

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.

Re: The Soviet license plate game and Kolmogorov complexity

#16

Post by aboutruby »

SamReidHughes wrote: post #13
aboutruby wrote: post #12

> √74 = sec arctan sec arctan … √44. He meant "sec arctan sec arctan … √74 = √44." (sent him a message) Also why not just applying the power 0 (assuming numbers are different than 0) both sides. Would be a school-level operation and very likely the shortest.

You can't write down new numbers in the formula.

Oh, I read too quickly, the ° is uses is the degree "operator" (it really isn't an operator IMHO).

Re: The Soviet license plate game and Kolmogorov complexity

#17

Post by empath75 »

luc4sdreyer wrote: post #5

One solution to the problem of measuring the length of the Python program is to turn it into machine code and measure that instead: https://stackoverflow.com/questions/138521/is-it-feasible-to...

The compiler might optimize out the entire calculation because it won’t change at runtime.

Re: The Soviet license plate game and Kolmogorov complexity

#18

Post by Hendrikto »

gpm wrote: post #14
FartyMcFarter wrote: post #7

> 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. Another problem with this strategy is that it generally requires solving the halting problem: you can only know whether a program "does a given task" when you know whether it halts or not.

That's only true if you care about knowing when you are done enumerating. The definition of enumeration commonly used in computability does not require that you know when you are done enumerating.

How can you make progress if your first generated program does not halt?

Re: The Soviet license plate game and Kolmogorov complexity

#20

Post by gpm »

Hendrikto wrote: post #18
gpm wrote: post #14

Earlier quoted context omitted.

That's only true if you care about knowing when you are done enumerating. The definition of enumeration commonly used in computability does not require that you know when you are done enumerating.

How can you make progress if your first generated program does not halt?

Run things in parallel.

The idea behind most enumeration algorithms looks like this:

    machines = {}
    next_program = 0
    loop forever:
        machines.insert(new_turing_machine(next_program))
        next_program++
        for machine in machines:
            machine.step()
            if machine.halted():
                machines.remove(machine)
                if machine has output we want:
                    yield machine
Post reply on HN