11 ms·
I consider those the Brownian ratchets [1] of computing. Interesting to model and see what's going on! Here's another variation: arrange the sticks in a line.
by darkmighty 11y ago
I consider those the Brownian ratchets [1] of computing. Interesting to model and see what's going on!
Here's another variation: arrange the sticks in a line. Have a pole scan the sticks from the top, and when the pole is impeded, record it's height. You've just computed max(a1,...,aN) in O(1) time?! (disproving is left as an exercise -- note you can even assume the pole is weightless and infinite!)
[1] https://en.wikipedia.org/wiki/Brownian_ratchet https://en.wikipedia.org/wiki/Brownian_ratchet
- mikeash 11y agoAll too easy! Relativity tells us that disturbances in the pole cannot move faster than the speed of light. Therefore the time it takes to find out that your pole hit something is O(n), since the location of the tallest element will be on average halfway down your line. Of course, there's the much more obvious problem that "arrange the sticks in a line" requires manipulating each stick, and is thus O(n)!
- darkmighty 11y agoCorrect, of course :) Maybe it's not that good example... I was trying to come up with a way to obfuscate the speed of light limitation (one usually thinks of poles as rigid). A thing I like about those is even if they're really simple they highlight limits like the Bekenstein bound: you can make your experiment arbitrarily large, but if you allow it to shrink arbitrarily (as a function of n), you get unexpected results (essentially BSS machines[1] versus Turing machines?) -- in your example you could actually sort the numbers in O(n). [1] https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smal...