Three notions of effective computation on $\mathbb{R}$

Details Three notions of effective computation on $\mathbb{R}$ Three notions of effective computation on $\mathbb{R}$

2008-03-20

arxiv.org/abs/0803.3073v2

Mathematics

Logic

Added a major section comparing real computation to $\Sigma$-definability, plus some additional references. Formerly entitled

Scientific paper

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 $\Sigma$-definability over $HF(\real)$, defined by Ershov as a generalization of the observation that the computably enumerable sets are exactly those $\Sigma_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 $\Sigma$-definable over $HF(\real)$. One consequence of this equivalence is a method of approximating certain $\real$-computable structures by Turing computable structures.

Affiliated with

Also associated with

No associations

Rating

Three notions of effective computation on $\mathbb{R}$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Three notions of effective computation on $\mathbb{R}$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Three notions of effective computation on $\mathbb{R}$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-586852