Open Access

Computability of sets in Euclidean space

Pure Mathematics and Applications's Cover Image
Pure Mathematics and Applications
Special issue dedicated to 70th anniversary of prof. Peter Tallos

Cite

We consider several concepts of computability (recursiveness) for sets in Euclidean space. A list of four ideal properties for such sets is proposed and it is shown in a very elementary way that no notion can satisfy all four desiderata. Most notions introduced here are essentially based on separability of ℝn and this is natural when thinking about operations on an actual digital computer where, in fact, rational numbers are the basis of everything. We enumerate some properties of some naïve but practical notions of recursive sets and contrast these with others, including the widely used and accepted notion of computable set developed by Weihrauch, Brattka and others which is based on the “Polish school” notion of a computable real function. We also offer a conjecture about the Mandelbrot set.