Programmability in fields

Publisher Website
Google Scholar
Abstract
In the present paper we investigate algorithmic properties of fields. We prove that axioms of formally real fields for the field R of reals and axioms of fields of characteristic zero for the field C of complex numbers, give the complete characterization of algorithmic properties. By Kfoury’s theorem programs which define total functions over R or C are effectively equivalent to loop-free programs. Examples of programmable and nonprogrammable functions and relations over R and C are given. In the case of ordered reals the axioms of Archimedean ordered fields completely characterize algorithmic properties. We show how to use the equivalent version of Archimed’s axiom (the exhaustion rule) in order to prove formally the correctness of some iterative numerical algorithms.

This publication has 0 references indexed in Scilit: