>There are computation devices more powerful than the Turing machine, which is why we have complexity classes Equivalent meaning computability, not complexity.

>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.