Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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)

Filter by
Sorted by
Tagged with
2
votes
0answers
23 views

Explicit Construction of Classical Rules in Quantum Turing Machine

I knew that we usually use circuit instead of Turing machine in Quantum computation. In a deterministic Turing machine one has transition rules, $$ \delta: Q\times\Gamma\rightarrow Q\times\Gamma\...
2
votes
0answers
44 views

Quantum algorithms for Prolog or automated theorem proving?

Are there quantum algorithms for Prolog (SLD resolution - unification and depth-first-search) or for automated theorem proving in general (negation, resolution, and SAT)? Usually automated theorem ...
2
votes
0answers
111 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 ...
29
votes
2answers
1k views

Can a quantum computer simulate a normal computer?

Similar to the question Could a Turing Machine simulate a quantum computer?: given a 'classical' algorithm, is it always possible to formulate an equivalent algorithm which can be performed on a ...
62
votes
3answers
2k views

Can a Turing machine simulate a quantum computer?

I know that a Turing machine1 can theoretically simulate "anything", but I don't know whether it could simulate something as fundamentally different as a quantum-based computer. Are there any ...