Three notions of effective computation on \mathbb{R}

arXiv0803.3073MaRDI QIDQ6208835FDOQ6208835

Authors: Wesley Calvert 

Publication date: 20 March 2008

Abstract: We compare three notions of effectiveness on uncountable structures. The first notion is that of a $eal$-computable structure, based on a model of computation proposed by Blum, Shub, and Smale, which uses full-precision real arithmetic. The second notion is that of an $F$-parameterizable structure, defined by Morozov and based on Mal'tsev's notion of a constructive structure. The third is $Sigma$-definability over $HF(eal)$, defined by Ershov as a generalization of the observation that the computably enumerable sets are exactly those $Sigm{a}_1$-definable in $HF(mathbbN)$. We show that every $eal$-computable structure has an $F$-parameterization, but that the expansion of the real field by the exponential function is $F$-parameterizable but not $eal$-computable. We also show that the structures with $eal$-computable copies are exactly the structures with copies $Sigma$-definable over $HF(eal)$. One consequence of this equivalence is a method of approximating certain $eal$-computable structures by Turing computable structures.

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

This page was built for publication: Three notions of effective computation on $\mathbb{R}$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6208835)