The physical Church-Turing thesis and non-deterministic computation over the real numbers.
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.
INRIA, Paris, France. gilles.dowek@inria.fr
Gilles
G
Dowek