4 ms·
I would caution against equating the computational capacity of a physical entity like this with what a single Turing machine or equivalent can do. The classic e
by lainga 8y ago
I would caution against equating the computational capacity of a physical entity like this with what a single Turing machine or equivalent can do. The classic example is that I can sort a bunch of arbitrary-precision real numbers in O(n) time using spaghetti: cut a piece to length for each number, then push the ends flat against a table and sweep your hand down along them while you repeatedly remove the first piece to touch your hand [0]. The pieces of spaghetti are able to do this because they're acting like a parallel computer; the thousands or millions of chemical reactions taking place inside the amoeba are probably doing the same thing.
[0] https://en.wikipedia.org/wiki/Spaghetti_sort https://en.wikipedia.org/wiki/Spaghetti_sort
- JoshuaDavid 8y agowouldn't that be O(N^2) because it takes longer to sweep your hand over the spaghetti if there is more spaghetti?
- lainga 8y agoWell, really, it's more like O(n) cutting, O(m) sweeping (rather than O(1)) in the largest value m we are trying to sort, and thus the time it takes for your hand to go from the highest spaghetti to the table, and O(n) picking spaghetti out. In that sense it's like radix sort, but you could make a similar point for comparison-based sorts as well, e.g. sorting 1024-bit numbers on a certain-width architecture will take longer, because you need more operations per comparison. I think the point of the example is that lining the pieces up so that they can be picked out is constant-time, because they are physical objects and all either being pushed or falling under their own gravity. That's a good point, though, it assumes arbitrarily large (Andre the Giant?) hands.
- whatshisface 8y agoIf a Turing machine can have an infinite tape then a spaghetti pusher can have infinite palms.
- aasasd 8y agoRather idiosyncratically, this algorithm is prone to breaking the items being sorted.
- TheOtherHobbes 8y agoOften a problem for spaghetti code techniques.
- quickthrower2 8y agoAre we still talking pasta, or badly written OO code!
- sorokod 8y ago"arbitrary-precision real numbers"? You can tell apart two different pieces with |spaghetti1 - spaghetti2| < epsilon for arbitrary small epsilon?
- lainga 8y agoWe also assume access to arbitrarily long spaghetti and ignore concerns like relativistic effects or free breaking length.
- adrianN 8y agoThis won't work in linear time, since you need time proportional to the square root of the number of spaghetti to move your picker from the position of the longest spaghetti to your output list.