Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

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

3 Post author: MinibearRex 26 July 2012 05:39AM

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

Article Navigation

Comments (15)
Tags: sequence_reruns

Comments (15)

You are viewing a single comment's thread.

Comment author: shokwave 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: STL 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: shokwave 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: wedrifid 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: STL 27 July 2012 05:24:21AM 0 points [-]

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

Powered by Reddit Powered by Reddit