computationally bounded observers and non-constructive mathematics

José Manuel Rodríguez Caballero josephcmac at
Tue Feb 14 20:07:21 EST 2023

Vaughan Pratt wrote:

>  Martin Dowd wrote, "A line segment in 3-dimensional Euclidean space
> has uncountably many points."

Since no one else has challenged Martin's statement, let me do so here.


> When your only tools are a straightedge and compass, you don't need
> anything more than the constructible points, aka real algebraic
> geometry with only linear and quadratic polynomials.  And if you
> insist on Euclidean space being topologically complete,  then
> furthermore you need the limits of sequences of contructible points
> when those limits exist.


> When your tools include a smartphone or other computer, you need at
> most the computable points, and its completion via computable
> sequences (more constrained than general Cauchy sequences) is likewise
> countable.

Assume the worst-case for the real numbers, that is, that the universe as a
whole is a computation (physical Church-Turing thesis, due to David Deutsch
[1] and Stephen Wolfram [2]). I will borrow from Stephen Wolfram the notion
of the computationally bounded observer that he uses to conceptualize the
second law of thermodynamics [3].

Let us consider a scientifically relevant mathematical model: the
continuous-time Markov process that describes births and deaths [4].
According to the physical Church-Turing thesis, all births and deaths in
nature are computational processes. Hence, the most realistic model would
be algorithmic. But, in practice, we can not access the actual algorithm
because of our computational boundedness. What we do instead is transfer
our epistemic limitations into ontological idealizations.

Of course, there are constructive versions of probability theory [5]. But
why should we insist on the construction of all mathematical objects in
models where the point is precisely that we don't know how to construct the
phenomenon under study? The non-constructive parts of mathematics may be a
useful way to formalize our computational boundeness.

Kind regards,
José M.

[1] Deutsch, David. "Quantum theory, the Church–Turing principle and the
universal quantum computer." Proceedings of the Royal Society of London. A.
Mathematical and Physical Sciences 400.1818 (1985): 97-117.
[2] Wolfram, Stephen. "Undecidability and intractability in theoretical
physics." Physical Review Letters 54.8 (1985): 735.
[3] Computational Foundations for the Second Law of Thermodynamics, Stephen
Wolfram's Writings, URL:
[4] Chazottes, J-R., P. Collet, and S. Méléard. "Sharp asymptotics for the
quasi-stationary distribution of birth-and-death processes." Probability
Theory and Related Fields 164.1-2 (2016): 285-332.
[5] Chan, Yuen-Kwok. *Foundations of Constructive Probability Theory*. Vol.
177. Cambridge University Press, 2021.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20230214/07d62510/attachment.html>

More information about the FOM mailing list