3 ms·

There are computation devices more powerful than the Turing machine, which is why we have complexity classes. (P, #P, #BQP are some examples described by differ

There are computation devices more powerful than the Turing machine, which is why we have complexity classes. (P, #P, #BQP are some examples described by different kinds of Turing-like machines.) So calling humans equivalent to standard Turing machine is ultimately wrong if you even start to assume quantum processes are important in our thinking. (which is actually unproven as of yet) Then you need to start with a more intricate parallel quantum Turing machine, high end mathematics required already. It is already non-deterministic. And no, quantum effects cannot be simulated efficiently classically. That is the difference between P and #P complexity classes. Add parallelism, you get #BQP. You would be able to tell something about the nature of reality by building physical instances of those problems and timing them. Timing attack on the structure of reality, structure of time itself, anyone? (Of course the required energies would be ridiculous.) To falsify any Turing model, you need to answer the question: what cannot be done by any given machine? Or by any machine? It is possible that there's a Goedel trap in this question. A parallel would be to find and answer to what cannot be computed efficiently by best human geniuses ever. Hard introspective question might I add. Answer probably requires building or finding something more than human.

drdeca 8y ago
#P is still decidable by Turing machines. And, I’m pretty sure that #BQP is too. (Just with a large slowdown.) Now, yes, there are models of computation which cannot be simulated by a Turing machine, but I don’t know of any substantial evidence that a physical process uncomputable. Any computation which has a finite number of possible inputs is computable, using a lookup table, and therefore using a Turing machine. So, for any physical process to be uncomputable, it must be such that there are infinitely many possible states of it, for it to proceed from. And, the Bekenstein bound, if correct, would seem to suggest that no structure like that can exist within a bounded region of space.
helen___keller 8y ago
>There are computation devices more powerful than the Turing machine, which is why we have complexity classes Equivalent meaning computability, not complexity. The two machines can simulate each other (even w/ exponential slowdown) then it's equivalent. > cannot be simulated efficiently classically Efficiency isn't really the point. The OP is suggesting there's a literal wall which makes something impossible to understand. This would require a computational behavior that cannot be programmed as a turing machine. > To falsify any Turing model, you need to answer the question: what cannot be done by any given machine? Correct. The answer is that a turing machine can't decide a turing-complete decision problem, so hypercomputation is achieved by equipping a turing machine with an oracle for a turing-complete problem. This actually leads to a hierarchy that is each strictly more powerful than the previous ones by using oracles for problems that are "more undecidable" so to speak (see https://en.wikipedia.org/wiki/Arithmetical_hierarchy https://en.wikipedia.org/wiki/Arithmetical_hierarchy ) Either way, we have no evidence that suggests theres a natural process that lives higher up on the arithmetical hierarchy. An example of a physical process that would fulfill this criteria: suppose there were a type of particle that only sometimes collide with each other, and it turns out that they only collide not just by running into each other but also when the sum of their velocities encode halting turing machines, otherwise the particles pass right through each other. A classical turing machine cannot decide the halting problem, so it's impossible to simulate a system with these particles because you never know if they will collide or not.

drdeca 8y ago

#P is still decidable by Turing machines. And, I’m pretty sure that #BQP is too. (Just with a large slowdown.) Now, yes, there are models of computation which cannot be simulated by a Turing machine, but I don’t know of any substantial evidence that a physical process uncomputable. Any computation which has a finite number of possible inputs is computable, using a lookup table, and therefore using a Turing machine. So, for any physical process to be uncomputable, it must be such that there are infinitely many possible states of it, for it to proceed from. And, the Bekenstein bound, if correct, would seem to suggest that no structure like that can exist within a bounded region of space.

helen___keller 8y ago

>There are computation devices more powerful than the Turing machine, which is why we have complexity classes Equivalent meaning computability, not complexity. The two machines can simulate each other (even w/ exponential slowdown) then it's equivalent. > cannot be simulated efficiently classically Efficiency isn't really the point. The OP is suggesting there's a literal wall which makes something impossible to understand. This would require a computational behavior that cannot be programmed as a turing machine. > To falsify any Turing model, you need to answer the question: what cannot be done by any given machine? Correct. The answer is that a turing machine can't decide a turing-complete decision problem, so hypercomputation is achieved by equipping a turing machine with an oracle for a turing-complete problem. This actually leads to a hierarchy that is each strictly more powerful than the previous ones by using oracles for problems that are "more undecidable" so to speak (see https://en.wikipedia.org/wiki/Arithmetical_hierarchy https://en.wikipedia.org/wiki/Arithmetical_hierarchy ) Either way, we have no evidence that suggests theres a natural process that lives higher up on the arithmetical hierarchy. An example of a physical process that would fulfill this criteria: suppose there were a type of particle that only sometimes collide with each other, and it turns out that they only collide not just by running into each other but also when the sum of their velocities encode halting turing machines, otherwise the particles pass right through each other. A classical turing machine cannot decide the halting problem, so it's impossible to simulate a system with these particles because you never know if they will collide or not.