<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>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 ℝ<italic><sup>n</sup></italic> 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 <italic>computable</italic> 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.</p>
</abstract>

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.

Computability of sets in Euclidean space

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Computability of sets in Euclidean space"}

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...

Computability of sets in Euclidean space

Published Online: Nov 07, 2022

Page range: 65 - 77

Received: Nov 08, 2021

DOI: https://doi.org/10.2478/puma-2022-0025

Keywords
Computability of sets, separability, computable function, impossibility results, Mandelbrot set

© 2022 Petrus H Potgieter, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Computability of sets in Euclidean space

Published Online: Nov 07, 2022

Page range: 65 - 77

Received: Nov 08, 2021

DOI: https://doi.org/10.2478/puma-2022-0025

KeywordsComputability of sets, separability, computable function, impossibility results, Mandelbrot set

© 2022 Petrus H Potgieter, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Keywords
Computability of sets, separability, computable function, impossibility results, Mandelbrot set