Algorithm and proof as Ω-invariance and transfer: A new model of computation in nonstandard analysis

Sam Sanders

We propose a new model of computation based on nonstandard analysis. Intuitively, the role of "algorithm" is played by a new notion of finite procedure, called Omega-invariance and inspired by physics, from nonstandard analysis. Moreover, the role of 'proof' is taken up by the Transfer Principle from nonstandard analysis. We obtain a number of results in Constructive Reverse Mathematics to illustrate the tight correspondence to Errett Bishop's Constructive Analysis and the associated Constructive Reverse Mathematics.

In Benedikt Löwe and Glynn Winskel: Proceedings 8th International Workshop on Developments in Computational Models (DCM 2012), Cambridge, United Kingdom, 17 June 2012, Electronic Proceedings in Theoretical Computer Science 143, pp. 97–109.
Published: 29th March 2014.

ArXived at: http://dx.doi.org/10.4204/EPTCS.143.9 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org