Remarks on Σ–definability without the equality test over the Reals
Author(s) -
Andrey Morozov,
Margarita Korovina
Publication year - 2008
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2008.03.023
Subject(s) - computability , computable analysis , mathematics , test (biology) , set (abstract data type) , discrete mathematics , algebra over a field , computer science , pure mathematics , programming language , paleontology , biology
In this paper we study properties of Σ–definability over the reals without the equality test which is one of the main concepts in the logical approach to computability over continuous data. It has been shown that a set $B\subset R^n$ is Σ–definable without the equality test if and only if $ B $ is c.e. open. If we allow the equality test, the structur$e of a Σ–definable subset of $R^n$ can be rather complicated. The next natural question to consider is the following. Is there an effective procedure producing a set which is a maximal c.e. open subset of a given Σ–definable with the equality subset of $R^n$? It this paper we give the negative answer to this question
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom