Questions tagged [computability-theory]

For questions on Church-Turing thesis, computable functions, etc. as relevant to quantum computing. It is a major branch of the theory of computation. Computability theory, also known as recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. (Wikipedia)

1 question with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
47 views

What precisely is the quantum extended Church-Turing thesis?

Context Prof. Aaronson mentions that the quantum extended Church-Turing (quantum ECT) thesis has no known counterexamples cf. around 14:18 but doesn't mention its precise statement. Questions What ...