4 ms·
What you're describing is generally accepted to be physically unrealizable. In fact, the sentence that follows your quoted sentence cites two commonly known phy
by mgraczyk 9y ago
What 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.