Noncomputable functions in the Blum-Shub-Smale model
Working in the Blum-Shub-Smale model of computation on the real numbers, we answer several questions of Meer and Ziegler. First, we show that, for each natural number d, an oracle for the set of algebraic real numbers of degree at most d is insufficient to allow an oracle BSS-machine to decide membe...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2011-05-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1226/pdf |
| _version_ | 1797268696192778240 |
|---|---|
| author | Wesley Calvert Ken Kramer Russell Miller |
| author_facet | Wesley Calvert Ken Kramer Russell Miller |
| author_sort | Wesley Calvert |
| collection | DOAJ |
| description | Working in the Blum-Shub-Smale model of computation on the real numbers, we
answer several questions of Meer and Ziegler. First, we show that, for each
natural number d, an oracle for the set of algebraic real numbers of degree at
most d is insufficient to allow an oracle BSS-machine to decide membership in
the set of algebraic numbers of degree d + 1. We add a number of further
results on relative computability of these sets and their unions. Then we show
that the halting problem for BSS-computation is not decidable below any
countable oracle set, and give a more specific condition, related to the
cardinalities of the sets, necessary for relative BSS-computability. Most of
our results involve the technique of using as input a tuple of real numbers
which is algebraically independent over both the parameters and the oracle of
the machine. |
| first_indexed | 2024-04-25T01:36:35Z |
| format | Article |
| id | doaj.art-6437c2d2e8414dc2bb51531d84244dae |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:36:35Z |
| publishDate | 2011-05-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-6437c2d2e8414dc2bb51531d84244dae2024-03-08T09:15:49ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742011-05-01Volume 7, Issue 210.2168/LMCS-7(2:15)20111226Noncomputable functions in the Blum-Shub-Smale modelWesley Calverthttps://orcid.org/0000-0002-1355-2694Ken KramerRussell MillerWorking in the Blum-Shub-Smale model of computation on the real numbers, we answer several questions of Meer and Ziegler. First, we show that, for each natural number d, an oracle for the set of algebraic real numbers of degree at most d is insufficient to allow an oracle BSS-machine to decide membership in the set of algebraic numbers of degree d + 1. We add a number of further results on relative computability of these sets and their unions. Then we show that the halting problem for BSS-computation is not decidable below any countable oracle set, and give a more specific condition, related to the cardinalities of the sets, necessary for relative BSS-computability. Most of our results involve the technique of using as input a tuple of real numbers which is algebraically independent over both the parameters and the oracle of the machine.https://lmcs.episciences.org/1226/pdfcomputer science - logic in computer sciencemathematics - logicf.1.1, f.1.3, i.1.2 |
| spellingShingle | Wesley Calvert Ken Kramer Russell Miller Noncomputable functions in the Blum-Shub-Smale model Logical Methods in Computer Science computer science - logic in computer science mathematics - logic f.1.1, f.1.3, i.1.2 |
| title | Noncomputable functions in the Blum-Shub-Smale model |
| title_full | Noncomputable functions in the Blum-Shub-Smale model |
| title_fullStr | Noncomputable functions in the Blum-Shub-Smale model |
| title_full_unstemmed | Noncomputable functions in the Blum-Shub-Smale model |
| title_short | Noncomputable functions in the Blum-Shub-Smale model |
| title_sort | noncomputable functions in the blum shub smale model |
| topic | computer science - logic in computer science mathematics - logic f.1.1, f.1.3, i.1.2 |
| url | https://lmcs.episciences.org/1226/pdf |
| work_keys_str_mv | AT wesleycalvert noncomputablefunctionsintheblumshubsmalemodel AT kenkramer noncomputablefunctionsintheblumshubsmalemodel AT russellmiller noncomputablefunctionsintheblumshubsmalemodel |