complexity theory

• intermediate
• 18 min read

Turing Machines, Computability, and What Quantum Computing Actually Changes

A quantum computer computes exactly the same set of functions as a Turing machine, no more and no fewer. It cannot solve the halting problem. What it changes is efficiency, not computability, and this tutorial draws the line precisely.