✦ LIBER ✦

Recursively enumerable subsets of Rq in two computing models Blum-Shub-Smale machine and Turing machine

✍ Scribed by Ning Zhong

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 997 KB
Volume: 197
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(97)00008-x

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we compare recursively enumerable subsets of R" in two computing models over real numbers: the Blum-Shub-Smale machine and the oracle Turing machine. We prove that

any Turing RE open subset of RY is a BSS RE set, while a Turing RE closed set may not be a BSS RE set. As an application we show that the Julia set of any computable hyperbolic polynomial is decidable in the Turing computing model.