# Understanding the Physical Church-Turing thesis and its implications

## Question:

Most of the applied mathematicians I know have considered Wigner's essay [3] at some point in their lives. Over time my intuition for this empirical observation of the immense progress of the mathematical sciences in the last four hundred years has been influenced by the Physical Church-Turing thesis. In fact, I would argue that the Physical Church-Turing thesis is not only compatible with Wigner's observation it actually implies that the effectiveness of mathematics in the natural sciences is reasonable.

Might such a connection between Wigner's arguments and the Physical Church-Turing thesis have been developed by either a theoretical computer scientist or theoretical physicist? One approach I have found for comparing the distinct claims of these theses is by formulating a choice of thesis as a model-selection problem, as proposed below.

## Choosing between theses as a model selection problem:

In my attempts to understand the Physical Church-Turing thesis I have managed to break it into two separate statements:

1. Every computational process is ultimately a mathematical description of a physical process in terms of (possibly coarse-grained) state transitions.

2. Every physical process has a mathematical description in terms of a sequence of mathematical operations such that it may be simulated by a Turing Machine. Therefore, every physical process may be simulated by a universal computing device.

I think most theoretical computer scientists and most scientists for that matter would accept the first point as it is consistent with the Church-Turing thesis and basic principles of computer engineering. However, the second point appears to be less universally accepted as it appears to have two possible interpretations: (a) The universe is computable and therefore we may identify such a device with the universe itself. (b) The universe is computable and so we may engineer a Planck-scale computer capable of simulating the universe itself.

If the vanilla Church-Turing thesis is identified with $$H_0$$, the first claim of the Physical Church-Turing thesis and (2a) is identified with $$H_1$$(modest thesis) and the first claim of the Physical Church-Turing thesis and (2b) is identified with $$H_2$$(strong thesis) then I think we may frame the problem of choosing between these distinct alternatives as follows:

$$$$X = \{\text{effectiveness of mathematics in the natural sciences} \} \tag{1}$$$$

$$$$H = \min_{H \in \mathcal{H}} -\ln P(X|H) \tag{2}$$$$

where $$\mathcal{H} = \bigcup_{i=1}^3 H_i$$.

My current intuition suggests that $$H_1$$ is more plausible than $$H_2$$ as there are probably epistemic limits to knowledge discovery via the scientific method.

## References:

1. Michael Nielsen. Interesting problems: The Church-Turing-Deutsch Principle. 2004. https://michaelnielsen.org/blog/interesting-problems-the-church-turing-deutsch-principle/
2. David Deutsch. Quantum theory, the Church–Turing principle and the universal quantum computer. 1985.
3. Eugene Wigner. The Unreasonable Effectiveness of Mathematics in the Natural Sciences. 1960.