4 ms·

It’s kind of hard to describe why we feel this is so irrefutable, but one of my favorite thought exercises is doing exactly that. My algorithms prof once took

by mxkopy 2y ago

It’s kind of hard to describe why we feel this is so irrefutable, but one of my favorite thought exercises is doing exactly that. My algorithms prof once took us on a fun journey describing the median-of-medians variation of the SELECT algorithm, and had us play around with different partition sizes to see its effect on asymptotic running time. Turns out if you choose any other value than 5, you get superlinear running time. This is probably the most random display of fatuousness I’ve encountered from mathematics. There should be absolutely no reason the number 5 - not 3, not 4 - has anything to do with recursively selecting a median, and yet here we are. It makes me wonder. Maybe there are computational rules similar to gravity or conservation of energy, but similar to physical machines, there seem to be computational ones that can be built defy them.

IIAOPSW 2y ago
You're asking one of the questions that was an early skepticism of quantum computing. Namely, until very recently there was a line of thought that while you could draw machines on paper which break certain computational limits by leveraging quantum mechanics (or other physics), just like with perpetual motion machines before them, all of these designs would be doomed to fail because they would violate a fundamental principle to how the universe works. In other, the line of thought was exactly like you said, that computational rules were similar to gravity or energy conservation and thus couldn't really be broken. Presently this line of thought is dead because quantum computers have demonstrated doing something that can't be done classically. So we know there's no theoretical reason not to have a quantum computer. But the thought that the laws of the universe might be underpinned by computation is still very much alive. Its just all qubits at the bottom rather than classical bits. There's a cliche in the field. "Information is physical". Roughly it means, information only exists encoded on some form of physical medium, and all physical systems are reducible to the information encoded as the state. Physical things are information, information is a physical thing. Information is physical.

by mxkopy 2y ago

IIAOPSW 2y ago

You're asking one of the questions that was an early skepticism of quantum computing. Namely, until very recently there was a line of thought that while you could draw machines on paper which break certain computational limits by leveraging quantum mechanics (or other physics), just like with perpetual motion machines before them, all of these designs would be doomed to fail because they would violate a fundamental principle to how the universe works. In other, the line of thought was exactly like you said, that computational rules were similar to gravity or energy conservation and thus couldn't really be broken. Presently this line of thought is dead because quantum computers have demonstrated doing something that can't be done classically. So we know there's no theoretical reason not to have a quantum computer. But the thought that the laws of the universe might be underpinned by computation is still very much alive. Its just all qubits at the bottom rather than classical bits. There's a cliche in the field. "Information is physical". Roughly it means, information only exists encoded on some form of physical medium, and all physical systems are reducible to the information encoded as the state. Physical things are information, information is a physical thing. Information is physical.