[spragl]

Both P and NP are computable. That is, a Turing machine can compute both of them.

Those quantum processes are interesting. Take the random numbers generated from radioactive decay. They are (after some cleanup) truly random. That is what we think. But how could we tell the difference from pseudorandom numbers, generated by a sufficiently advanced algorithm? We couldnt. So particles could simply be Turing Machines running sufficiently advanced algorithms that we cant reverse engineer. If so, quantum mechanics is computable even if we cant compute it.

(Particles being TMs doesnt mean they are FAs with an infinite tape, but that they are computationally equivalent to TMs.)

[peter_m1]

There is such thing as a quantum Turing machine you know (Deutsch 1985).

[spragl]

Yes I know.

When I wrote Turing Machine, I was thinking about the classical determinstic Turing Machine.

Im not super knowledgable about Quantum Turing Machines, but as far as I know, they dont do better than the classical deterministic Turing Machines when we are talking about computability.