# shokwave comments on [SEQ RERUN] Sorting Pebbles Into Correct Heaps - Less Wrong Discussion

3 26 July 2012 05:39AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Sort By: Best

You are viewing a single comment's thread.

Comment author: 26 July 2012 07:26:40AM *  1 point [-]

the Pebblesorters will never forget the Great War of 1957, fought between Y'ha-nthlei and Y'not'ha-nthlei, over heaps of size 1957. That war finally ended when the Y'not'ha-nthleian philosopher At'gra'len'ley exhibited a heap of 103 pebbles and a heap of 19 pebbles side-by-side. So persuasive was this argument that even Y'not'ha-nthlei reluctantly conceded that it was best to stop building heaps of 1957 pebbles, at least for the time being.

Interesting potential-parallels: the argument of 103 and 19 is easy to check (multiplication) but hard to formulate (prime factorisation). Evaluating the statement by itself is in between (primality test).

Comment author: 27 July 2012 04:49:00AM 2 points [-]

Primality testing is easy in the sense that if someone discovered that factorization was that easy, they would win the Nobel Prize in Math. Which doesn't even exist.

Comment author: 27 July 2012 05:02:11AM *  1 point [-]

Right, a primality test is not hard like factorisation, but it's harder than multiplication. Our pebblesorters are clearly somewhere between multiplication and prime testing. If a pebblesorter proved something like the AKS algorithm, they would win more than the GĂ¶del prize!

Comment author: 27 July 2012 04:56:14AM 0 points [-]

they would win the Nobel Prize in Math. Which doesn't even exist.

Have you been watching Teen Wolf?

Comment author: 27 July 2012 05:24:21AM 0 points [-]

Nope - didn't even know that was a TV series until I wikipediaed it just now.