Nonstandard Analysis: a new way to compute
Sam Sanders ( University of Ghent )
Following recent results in Reverse Mathematics, we introduce
"$\Omega$-invariance", a simple and elegant notion from Nonstandard Analysis
meant to capture the notion of algorithm (both in the sense of Alan Turing and
Errett Bishop). Intuitively, an object is $\Omega$-invariant if it does not depend
on the choice of infinitesimal used in its definition.
We show that $\Omega$-invariance exactly captures the notion of Turing
computability and we identify an extra condition T (based on the Transfer Principle
of Nonstandard Analysis) so that "$\Omega$-invariance + condition T " captures
the constructive notion of algorithm à la Bishop.