Wednesday, March 28, 2018

Von Neumann believed in Church's Thesis

John von Neumann is regarded by many as the smartest man of the XX century. Two of his areas of expertise were the foundations of quantum mechanics, and computability theory. He wrote the first QM textbook that clearly explain how observations yield collapse of the wave function, 1932. He was one of the first in the mainstream mathematical community to recognize the significance of Goedel's work on the computability of proofs.

The Church–Turing thesis of the 1930s was the physically computable functions were those defined by Goedel, Church, and Turing.

Not until around 1985 did anyone argue that von Neumann's QM is in direct contradiction to the Church-Turing thesis, and that quantum computers will be able to create computable functions that are beyond what can be done with Turing machines.

How was von Neumann so stupid as to not notice this?

Von Neumann did a lot of work to build early computers, and yet he never commented that with quantum mechanics, he could outdo a Turing machine. Why?

And why didn't anyone else notice it either?

I say that the answer is that there is no such contradiction. The foundations of quantum mechanics do not imply a violation of Church's thesis. It is a myth.

QM says that if you have a system with a |0> state and a |1> state, and if you cannot predict which will be the result of a future measurement, then the formalism represents it as a cat-state, where either is possible. It is like the Schroedinger cat that might be alive or dead, until you open the box and look.

The theory works great, and I don't question it.

But the quantum computing enthusiasts claim that you can some use your uncertainty to do a super-Turing computation. This is like putting a cat in a box, generating some uncertainty about whether the cat is alive, and they trying to use that uncertainty to do a super-Turing computation. At the end, you might open the box to find that the cat was alive all along, but the intervening uncertainty somehow magicly does some super-natural computation.

I don't believe it. The conventional wisdom should be in the validity of Church's thesis, unless someone convincing demonstrates otherwise.


  1. Nobody has argued that QM is in direct contradiction with the Church-Turing thesis. It is that QM is in direct contradiction with Extended Church-Turing thesis.

    There is a subtle difference. The Church-Turing thesis has to do with computability theory, while the Extended Church-Turing thesis has to do with computational complexity theory.

    Also, computational complexity theory started in the 1960's after von Neumann died.

  2. You are making terminology distinctions that did not exist during von Neumann's life. Why didn't von Neumann ever say that a quantum computer might expand the class of computable functions? He was the world's expert on both quantum foundations and computability.

    1. Nobody today says a quantum computer might expand the class of computable functions. They say the quantum computer might expand the class of *efficiently* computable functions. During von Neumann's lifetime, people didn't really think about this; they were happy just to get computers to work.

    2. You've got a good point, but von Neumann actually built computers. The common von Neumann architecture is named after him. So certainly thought a lot about computing efficiently. And yet he never saw any point to putting bits in a cat state.

    3. I meant that before the 1960s, people didn't really think of algorithms as polynomial time or exponential time, at least not in the literature.

  3. Uncertainty and probability are not a quasi form of existence, they change nothing actual, they physically inform nothing actual. Both are attributes or properties of the observer or a calculation done by an observer, not attributes of what is observed.

    It does not matter how certain or uncertain you are about what is going on inside a damn box, regardless, it is what it is with or without an observers measurement or recognition. If you question this, just ask someone blind if they have run into things they were not aware of. You can walk into a wall whether or not you know it's there. Reality is not informed by how much awareness you have of it, however, awareness IS informed by reality.

    It does not matter how much of a probability you 'calculate' something has or hasn't happened inside a box, as the functioning of whatever is or is not in the box, and is not informed in any way by what you think, know, or don't know about it.

    If you want to understand a process, acknowledge the limits of what you know, and stop conflating the mechanism of the math model with the actuality of the subject.

  4. This comment has been removed by the author.