The Soviet license plate game and Kolmogorov complexity • Hacker News Board

Re: The Soviet license plate game and Kolmogorov complexity

#21

Post by huhtenberg » Sun, Feb 03, 2019, 1:18 PM UTC

pqhwan wrote: post #4

Huh, I thought I was the only one playing this weird game in my head. I used to live in a country where license plates are all numeric digits. But with 4 digits and my limited knowledge of math operations (I was a child), it was hard to find plates that "had solutions". So I gave myself a little wiggle room by imagining the numbers were written as they were on digital alarm clocks, where certain numbers (like {2,3,5}…

Trying to understand if a plate number is a prime also works quite well :) Though local congestions are rarely large enough to allow checking for factors over 11 or 13.

Re: The Soviet license plate game and Kolmogorov complexity

#22

Post by algorias » Sun, Feb 03, 2019, 1:43 PM UTC

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.

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

Sorry, but this is a non-sequitur. In order to find (by enumeration) the shortest program producing a certain output, you absolutely do need to know when you're done, and thus you do need to solve the halting problem.

Re: The Soviet license plate game and Kolmogorov complexity

#23

Post by madcaptenor » Sun, Feb 03, 2019, 2:20 PM UTC

aboutruby wrote: post #16

SamReidHughes wrote: post #13

Earlier quoted context omitted.

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).

You could argue that the degree operator is just another name for multiplication by the constant pi/180.

Re: The Soviet license plate game and Kolmogorov complexity

#24

Post by [deleted] » Sun, Feb 03, 2019, 2:56 PM UTC

gpm wrote: post #20

Hendrikto wrote: post #18

Earlier quoted context omitted.

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

[deleted]

Re: The Soviet license plate game and Kolmogorov complexity

#25

Post by gpm » Sun, Feb 03, 2019, 3:36 PM UTC

algorias wrote: post #22

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.

> The definition of enumeration commonly used in computability does not require that you know when you are done enumerating. Sorry, but this is a non-sequitur. In order to find (by enumeration) the shortest program producing a certain output, you absolutely do need to know when you're done, and thus you do need to solve the halting problem.

Ah, you're right. I was focusing too much on the statement itself and not the context of it.

Re: The Soviet license plate game and Kolmogorov complexity

#26

Post by darkhorn » Sun, Feb 03, 2019, 3:36 PM UTC

I'm reading a 5 page paper from “German Aerospace Center Aviation and Space Psychology” titled “DLR - Basic Knowledge”. Under “Training Mathematics” section it says “Try to quickly first add, then multiply the digits of the licence plates of the cars in front of you when waiting at a traffic light”. So, I guess they wrote this because of Lev Landau.

Re: The Soviet license plate game and Kolmogorov complexity

#27

Post by umlautae » Sun, Feb 03, 2019, 3:47 PM UTC

An interesting application of the Kolmogorov complexity to measure the similarity of various languages etc.

"Abstract—A new class of distances appropriate for measuring similarity relations between sequences, say one type of similarity per distance, is studied. We propose a new “normalized information distance,” based on the non computable notion of Kolmogorov complexity, and show that it is in this class and it minorizes every computable distance in the class (that is, it is universal in that it covers all computable similarities). We demonstrate that it is a metric and call it the similarity metric. This theory forms the foundation for a new practical tool. ..."

https://homepages.cwi.nl/~paulv/papers/similarity.pdf

Re: The Soviet license plate game and Kolmogorov complexity

#28

Post by murbard2 » Sun, Feb 03, 2019, 4:16 PM UTC

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.

For that, you can replace Kolmogorov complexity with Levin complexity, which penalizes the Kolmogorov complexity by adding the log of the execution time.

Since sufficiently advanced Turing machines are all equivalent up to a multiplicative factor, Levin complexity is defined up to a constant, as is Kolmogorov complexity.

Re: The Soviet license plate game and Kolmogorov complexity

#29

Post by ddxxdd » Sun, Feb 03, 2019, 4:29 PM UTC

Y_Y wrote: post #6

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...

Doesn't this just kick the problem down the road? Now you've introduced the optimisation of the compiler abd the expressiveness of your processor's machine language. The problem of knowing you have the "best" solution remains. I think if you are trying to come up with a canonical languahe to measure kolmogorov complexity in you can do better, like Binary Lambda Calculus. https://tromp.github.io/cl/LC.pdf

The same mathematical problem or operation can have several different Kolmogorov complexities, depending on how efficient an algorithm is when solving the problem.

I don't think there's any way around it. If I create a Turing Machine that calculates 1+1 by counting all the atoms in the universe, it's going to have a high complexity.

Re: The Soviet license plate game and Kolmogorov complexity

#30

Post by sn41 » Sun, Feb 03, 2019, 5:21 PM UTC

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…

It is rarely the case that the shortest program is the fastest.

To see a simple such phenomenon (very roughly) in the case of Kolmogorov complexity, consider two programs to print a sequence of 0x1000000 zeros.

Program 1:

   for i = 1 to 0x10000000:
     print 0

Program 2:

  i = 0x1


(I may be off by a constant, but you get the idea). Program 2 is shorter, since it takes about log 28 bits (the other code has basically constant length), while Program 1 takes about 32 bits (the remaining code being of a different constant length). They both produce the same string. Program 1 is longer, but "faster", since it does not have the left-shift loop.Philosophically: Program 1 has identified that the string to be printed is a very simple one. Program 2 has exploited the additional fact that the length of the string to be printed, itself is a very simple number, and has a short description. But then it needs additional time to figure out how many zeroes to print, since it needs to decode the length first.
This effect can be amplified with larger constants involved.
Kolmogorov complexity is a "well-defined" notion, hence mathematically nice, it is just that it is not computable. That's bad, but not catastrophic. The halting problem is undecidable, C++ compilation with templates is undecidable [1] - that does not make coding useless.
About the larger problem of dry mathematical textbooks, I agree with you. Some of it just boils down to the fact that the pure and the applied side are often tightly segregated, and very few mathematicians care about both. When you talk to practising mathematicians, you often get a livelier picture.
[1] https://stackoverflow.com/questions/794015/what-do-people-me...


    
      Permalink
      View on HN
      Reply on HN
      Top