3 ms·

Would this mean that either the strong Church-Turing thesis(any model of computation based on physical reality gives the same class of problems solvable in poly

• whatshisface 6y ago
  If what is suspected is true, then yes, strong Church-Turing is false. If there's a symmetry in QCD that makes simulation possible in polynomial time, i.e. a helpful property that is true of QCD specifically but absent from the more general class of integrals its solutions belong to, then no. If you're looking for something to raise your hair even farther, some suspect that gravity is outright uncomputable[0] due to the unclassifiability of 4-manifolds and the expectation that quantum gravity will require summing over possible spacetimes. Since all of our computers are built with QED, it should come as no surprise that everything else made out of QED-obeying-matter, like Turing machines are imagined to be, is equally difficult to compute and equally powerful at computing. I don't see why you'd expect the other field theories to fall in to the same computational class. [0]https://arxiv.org/pdf/gr-qc/0506019.pdf https://arxiv.org/pdf/gr-qc/0506019.pdf