News for hackers. Stuff that matters.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by foxes on Thursday June 17, 2021 @10:30AM (#27539962)
Well I might add the quantum complexity-theory version of the Church–Turing thesis.

I believe that quantum computation is a richer more powerful theory. In essence BQP is a superset of BPP in your link.

I think this happens with all sorts of mathematical objects. Non commutative algebra is much richer than commutative algebra. There are also more interesting non commutative things than just deformations of classical objects. Its the classical commutative case that is the weird limit.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @11:02AM (#27540318)
Yeah, there are all sorts of layers we can add, especially regarding complexity (i.e. resource usage limits, rather than simple yes/no questions of decidability).

It's interesting to consider P = NP as a physical law, although that's certainly more tenuous than the Church-Turing thesis, etc.