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?

  • $\begingroup$ I think many in CS would be comfortable interpreting or extending Church-Turing to include Turing Machines with access to a random oracle, which assumes away this issue. (Otherwise your example seems to falsify Church-Turing immediately...) $\endgroup$
    – usul
    Commented Mar 22, 2018 at 15:49

2 Answers 2


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 $>\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 <-> "(partial) functions", Bosons <-> "something else"), but the Church-Turing thesis would probably still hold in such modified settings.

  • $\begingroup$ Ah, so you saying that a random function isn't actually a function. That's reasonable. My question though what if you use caching to guarantee that it's a function (i.e. maps the same input to the same output)? Basically, a machining that given $n$, either outputs the same output, or generates a random bit if it's a new input. $\endgroup$ Commented Mar 23, 2018 at 14:41
  • $\begingroup$ @PyRulez That's still not a function. Or how would you ensure that two copies of your machine arrive at the same values? $\endgroup$ Commented Mar 23, 2018 at 15:09
  • $\begingroup$ @EmilJeřábek two different machines wouldn't. They'd calculate different functions. $\endgroup$ Commented Mar 23, 2018 at 16:02
  • $\begingroup$ @PyRulez What I try to say is that as long as you stay in the original context of the Church-Turing thesis, it holds even if you allow randomness. And if you leave that context, better accept that those toasting toast discussions are not pointless, but contain valid points and insights. $\endgroup$ Commented Mar 24, 2018 at 10:37

In a way, if we imagine time continuing indefinitely then with probability 1, random numbers, obtained from I guess the collapse of the wave function in quantum mechanics, will form a non-computable sequence. So Church-Turing and true randomness would seem to be incompatible.

There is a deeper problem with "true randomness", though: what does it even mean to say that a physical system obeys a probability distribution?

Perhaps it means that most likely, something will happen, but that's circular (what is "most likely"). Or, if you repeat an experiment, it will most likely happen in close to the proportion given by the probability. Again, "most likely" is circular. To resolve this, one way out may be Cournot's Principle:

very very unlikely events just do not happen.

Or equivalently, a very very likely event will definitely happen. Here "very very" could be something to do with the Planck time as described by Peter Shor in another answer -- maybe an event $A$ of probability $10^{-200}$ could qualify. But this is a tricky subject, for instance the probability $\epsilon$ may have to depend on the descriptional complexity of $A$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.