3 ms·
I'm hoping that analog computing will come back in the form of photonic analog computing. This would be more powerful than quantum digital computing (you know t
by adamnemecek 9y ago
I'm hoping that analog computing will come back in the form of photonic analog computing. This would be more powerful than quantum digital computing (you know the things that people are wasting time on).
Fun fact, with analog computing, one could imagine achieving Real Computation (https://en.wikipedia.org/wiki/Real_computation https://en.wikipedia.org/wiki/Real_computation) which is above and beyond Turing. completeness.
Note the fun sentence "If real computation were physically realizable, one could use it to solve NP-complete problems, and even #P-complete problems, in polynomial time. ".
We are on a wrong evolutionary branch of computing. Bits are lame-o-rama, whereas differentiable signals are pure unadulterated flavortown.
- mgraczyk 9y agoWhat you're describing is generally accepted to be physically unrealizable. In fact, the sentence that follows your quoted sentence cites two commonly known physical limitations that prevent the existence of your "computational class above and beyond Turing". Whether or not there exist physically realizable computations that are not computable by a turing machine is an open question, but most physicists and computational complexity theorists seem to believe there does not exist such a class. https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
- adamnemecek 9y agoRead unlimited as arbitrary precision. I'm familiar with the Turing thesis but he's wrong.
- alanbernstein 9y agoCare to elaborate?
- shmageggy 9y ago> I'm familiar with the Turing thesis but he's wrong. You're going to have to back up a statement like that with a whole lot of supporting evidence if you want to be taken seriously.
- deleted 9y ago[deleted]
- adamnemecek 9y agoLook into work of Lenora Blum. She wrote a book "Complexity and Real computation".
- moyix 9y agoHave you read Scott Aaronson's NP-Complete Problems and Physical Reality [1] ? He goes into some detail about why analog computing is not thought to be physically realizable (Section 6). [1] http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/npcomplete.pdf
- adamnemecek 9y agoI'm passingly familiar. I'm not convinced. I can't really explain to you why. I feel like makes many assumptions about the architecture and workings of such a machine. I know Scott Aaronson and all, but I won't believe it until someone tries to build one and fails.
- rdtsc 9y ago> I'm familiar with the Turing thesis but he's wrong. Could you at least explain in what way you think he is wrong. Surely you must guess how participants on a programming forum will react to a statement like that.
- adamnemecek 9y agoThe extended Turing-Church thesis states that an analog computer can be simulated on a Turing machine. It can but not efficiently. Look into the work of Lenora Blum. She wrote a book "Complexity and Real computation".
- ramgorur 9y ago>"computational class above and beyond Turing" what does it mean?
- vortico 9y agoRoughly, a computer that can solve problems in polynomial time which do not have a polynomial time algorithm on a Turing machine, which is the same class of computers we use today.