Is true randomness and the physical Church-Turing thesis incompatible? As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are incompatible? The reason is that there is a physical process which can generate a random sequence of digits (i.e. a random oracle), but a Turing machine can not. Moreover, generating a random sequence of digits should never hit a "wall". We can continue generating them forever without issue. Once the heat death of the universe hits, random numbers will be generated automatically.

Of course, this might be like asking if Turing machines can toast toast, but I don't think so. Generating a sequence of numbers if a purely computational task, and it would seem that if a Turing machine can not generate a physically realizable sequence of numbers, then that would disprove the physical Church-Turing thesis. Also, it is normally assumed that the physical Church-Turing thesis implies that the universe is simulatable (it a Turing machine can't toast toast, but it can simple toasting). Randomness seems to forbid this.

So, are the physical Church-Turing thesis and true-randomness incompatible, or not?
The Church-Turing thesis is about (partial) functions $\mathbb{N} \to \mathbb{N}$ (or $\Sigma^* \to \Sigma^*$ for a finite alphabet $\Sigma$). How do you define a definite value based on some random output (for a given input)? There is at most one (random) output occurring with probability $&gt;\frac{1}{2}$, so taking that output if it exists (and undefined otherwise) as definite value could be a reasonable definition. (One might argue that $\frac{1}{2}$ is too small for physical implementation and one should take $\frac{2}{3}$ instead, but I guess that is not really important for this answer.) The Church-Turing thesis now asserts that even this extended notion of computability for (partial) functions $\mathbb{N} \to \mathbb{N}$ still leads to the same set of computable functions.



If we are willing to leave the strict setting of (partial) functions $\mathbb{N} \to \mathbb{N}$, then we risk those toasting toast discussions. (Based on the older mustard watches or montres à moutarde parody by Jean-Yves Girard.) I prefered Martin Berger's and Neel Krishnaswami's position in that discussion over Scott Aaronson's position, but most everybody else seems to agree with Scott. I guess even Andrej Bauer would be unable to change that outcome. Scott's position is not meant as a parody:


  To the people who keep banging the drum about higher-level formalisms being vastly more intuitive than TMs, and no one thinking in terms of TMs as a practical matter, let me ask an extremely simple question. What is it that lets all those high-level languages exist in the first place, that ensures they can always be compiled down to machine code? Could it be ... err ... THE CHURCH-TURING THESIS, the very same one you've been ragging on?


I previously wrote "So if a theoretical machine had access to a random source which its opponent could not predict (and could conceal its internal state from its opponent), then this theoretical machine would be more powerful than a Turing machine." But that argument takes place in a game theoretic setting (and idealization of some real world scenario) different from the context of the Church-Turing thesis. The simulation argument (explained by Martin Berger in the above discussion) could reduce that setting back to TMs by simulating all interactions between the random source enhanced Turing machines, but that misses my original point, about the random source being a separate idealization which can fail in its own ways. But if already clear concepts like higher-level formalisms gets dismissed, then there is little point in elaborating such fine interpretative points.



It might be possible to keep the "$\mathbb{N} \to \mathbb{N}$" part, and replace the "(partial) functions" part with something else (I am thinking here of an analogy Fermions &lt;-> "(partial) functions", Bosons &lt;-> "something else"), but the Church-Turing thesis would probably still hold in such modified settings.