Three notions of effective computation on $\mathbb{R}$
| dc.creator | Calvert, Wesley | |
| dc.date | 2008-03-20 | |
| dc.date | 2008-09-01 | |
| dc.date.accessioned | 2026-07-07T09:59:20Z | |
| dc.date.available | 2026-07-07T09:59:20Z | |
| dc.description | We compare three notions of effectiveness on uncountable structures. The first notion is that of a $\real$-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 $Σ$-definability over $HF(\real)$, defined by Ershov as a generalization of the observation that the computably enumerable sets are exactly those $Σ_1$-definable in $HF(\mathbb{N})$. We show that every $\real$-computable structure has an $F$-parameterization, but that the expansion of the real field by the exponential function is $F$-parameterizable but not $\real$-computable. We also show that the structures with $\real$-computable copies are exactly the structures with copies $Σ$-definable over $HF(\real)$. One consequence of this equivalence is a method of approximating certain $\real$-computable structures by Turing computable structures. | |
| dc.description | Added a major section comparing real computation to $Σ$-definability, plus some additional references. Formerly entitled "$\mathbb{R}$-computation and $F$-parameterizability." | |
| dc.identifier | https://arxiv.org/abs/0803.3073 | |
| dc.identifier | http://arxiv.org/abs/0803.3073 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/167985 | |
| dc.subject | Logic | |
| dc.subject | 03D45; 03C57 | |
| dc.title | Three notions of effective computation on $\mathbb{R}$ | |
| dc.type | text |