The physical Church-Turing thesis and non deterministic computation over the real numbers

2023/04/19 by Gilles Dowek, Dowek, Gilles
Computer Science · Physics and Astronomy · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Quantum Mechanics and Applications

paper · pdf · doi:10.48550/arxiv.2305.01432

openalex publication_date 2023/04/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

On the real numbers, the notions of a semi-decidable relation and that of an effectively enumerable relation differ. The second only seems to be adequate to express, in an algorithmic way, non deterministic physical theories, where magnitudes are represented by real numbers.

Related

• Computing over the Reals: Foundations for Scientific Computing
• Confusion in the Church-Turing Thesis
• Turing-Church thesis, constructve mathematics and intuitionist logic
• Some consequences of a recursive number-theoretic relation that is not the standard interpretation of any of its formal representations
• The Church-Turing thesis as a guiding principle for physics