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


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): https://en.wikipedia.org/wiki/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. Jun 18 '19 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 Jun 18 '19 at 21:27

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 Jun 19 '19 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 Jun 19 '19 at 11:06
  • $\begingroup$ Why decidable questions, as opposed to, say, semidecidable? The concept of a physical observation is closer to semidecidability. $\endgroup$ – Andrej Bauer Jun 19 '19 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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