John Archibald Wheeler was a famous physicist.

It has been stated that he thought that there was a strong connection between undecidability and quantum physics:

This idea was given an early formulation by Wheeler himself: in unpublished notes to a discussion held with, among others, Roger Penrose and Simon Kochen, he identifies the point of origin of the ‘quantum principle’ as the undecidable propositions of mathematical logic

(See Jochen Szangolies, Epistemic Horizons and the Foundations of Quantum Mechanics.)

But then, this same physicist proposed that the universe was similar to a computer and that reality emerged as digital informational processes in form of bits (It from Bit): digital physics.

As far as I know, digital physics models cannot be undecidable. They must be decidable (If not, we could never construct an algorithm which would get a correct answer to a yes/no question)

So, what is happening here? Did Wheeler change of mind?

  • $\begingroup$ I encourage you to elaborate on "digital physics models cannot be undecidable". What do you mean by that? Why if not, then we could never construct an algorithm? $\endgroup$
    – John L.
    Commented Jun 18, 2019 at 19:03
  • $\begingroup$ @Apass.Jack according to these models, the universe would be completely computable, so no undecidable/uncomputable things could exist. This is mentioned here for example: (philosophy.stackexchange.com/questions/7131/…), where it is said that: "the presence of a rule 110 system (or any other Turing complete system) in a finite universe would not imply the existence of undecidable properties." $\endgroup$
    – jerard
    Commented Jun 18, 2019 at 21:27

1 Answer 1


The inference "the universe would be completely computable, so no undecidable/uncomputable things could exist" is invalid.

In the effective topos, where everything is computable, there are many undecidable phenomena. For example, all real numbers are computable, but equality of real numbers is undecidable (and computable).

To give you an idea how this happens: equality of reals is a map $\mathbb{R} \times \mathbb{R} \to \Sigma$ which is implemented by a Turing machine that takes (Turing machines that compute) reals $x$ and $y$ and returns a non-boolean truth value represented by a Turing machine which terminates if, and only if, $x \neq y$.

In contrast, equality of natural numbers is decidable. It is a map $\mathbb{N} \times \mathbb{N} \to \{0,1\}$ which takes two natural numbers and outputs either $0$ or $1$, depending on whether they are equal.

As far as physcists are concerned, I would be careful about learning computability theory from them. I wouldn't want anyone to learn physics from me.

  • $\begingroup$ thank you! Then I guess undecidable things could exist in Wheeler's It from Bit universe...But, anyways, wouldn't Wheeler's ideas and models be related to decidability? For example, he introduced the concept of "Participatory Universe" where the universe would "model" the universe due to a series of decidable yes/no questions. Wheeler based his ideas on Weizsäcker's ur-alternatives theory, which was based also in a series of decidable yes-no questions @AndrejBauer $\endgroup$
    – jerard
    Commented Jun 19, 2019 at 11:06
  • $\begingroup$ that is indicated here ((books.google.es/…), so wouldn't Wheeler's models of the universe also contain/be related to decidability? @AndrejBauer $\endgroup$
    – jerard
    Commented Jun 19, 2019 at 11:06
  • 1
    $\begingroup$ Why decidable questions, as opposed to, say, semidecidable? The concept of a physical observation is closer to semidecidability. $\endgroup$ Commented Jun 19, 2019 at 13:52

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.