Login
You're viewing the functional.cafe public feed.
  • Nov 18, 2026, 11:57 PM

    @dalias @alcinnz @kevingranade Anyway, quantum computers are provably computers in the sense of the *weak* Church–Turing thesis (that is, in terms of computability), but aren't identical to classical computers in the sense of the *strong* Church–Turing thesis (that is, in terms of complexity).

    💬 1🔄 1⭐ 0

Replies

  • Nov 19, 2026, 12:17 AM

    @xgranade @alcinnz @kevingranade What I mean is that a QC does something different than the Church-Turing sense of computation. It does not answer a rigorous logical yes/no condition, accept/reject candidate members of a language, etc. Its results are qubits that need to be measured. This is a very different sense of computation.

    💬 3🔄 1⭐ 0
  • 💬 0🔄 0⭐ 0
  • Nov 19, 2026, 12:24 AM

    @xgranade @alcinnz @kevingranade In some sense real physical computers are like this too. They are subject, albeit with extremely low probability, to flipped bits from existing in a physical reality, on top of having some degree of finitude. But at least in an idealized form they are equivalent. I don't see any way a QC is equivalent except possibly in a limit as you approach infinitely many measurements. OTOH a QC is much better at other things.

    💬 0🔄 1⭐ 0
  • 💬 0🔄 0⭐ 0