Document Open Access Logo

Computing Measure as a Primitive Operation in Real Number Computation

Authors Christine Gaßner, Arno Pauly , Florian Steinberg

PDF
Thumbnail PDF

File

LIPIcs.CSL.2021.22.pdf
  • Filesize: 0.64 MB
  • 22 pages

Document Identifiers

Author Details

Christine Gaßner
  • Universität Greifswald, Germany
Arno Pauly
  • Department of Computer Science, Swansea University, UK
Florian Steinberg
  • INRIA, Sophia Antipolis, France

Cite As Get BibTex

Christine Gaßner, Arno Pauly, and Florian Steinberg. Computing Measure as a Primitive Operation in Real Number Computation. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CSL.2021.22

Abstract

We study the power of BSS-machines enhanced with abilities such as computing the measure of a BSS-decidable set or computing limits of BSS-computable converging sequences. Our variations coalesce into just two equivalence classes, each of which also can be described as a lower cone in the Weihrauch degrees.
We then classify computational tasks such as computing the measure of Δ⁰₂-set of reals, integrating piece-wise continuous functions and recovering a continuous function from an L₁([0, 1])-description. All these share the Weihrauch degree lim.

Subject Classification

ACM Subject Classification
  • Theory of computation → Abstract machines
  • Theory of computation → Turing machines
  • Mathematics of computing → Point-set topology
  • Mathematics of computing → Integral calculus
Keywords
  • BSS-machine
  • Weihrauch reducibility
  • integrable function
  • Lebesgue measure
  • computable analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and Real Computation. Springer, 1998. Google Scholar
  2. Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 21(1):1-46, 1989. URL: http://projecteuclid.org/euclid.bams/1183555121.
  3. Vasco Brattka. Computable invariance. Theoretical Computer Science, 210:3-20, 1999. URL: https://doi.org/10.1016/S0304-3975(98)00095-4.
  4. Vasco Brattka. A computable Kolmogorov superposition theorem. Informatik Berichte 272, FernUniversität Hagen, 2000. Google Scholar
  5. Vasco Brattka. Effective Borel measurability and reducibility of functions. Mathematical Logic Quarterly, 51(1):19-44, 2005. URL: https://doi.org/10.1002/malq.200310125.
  6. Vasco Brattka, Matthew de Brecht, and Arno Pauly. Closed choice and a uniform low basis theorem. Annals of Pure and Applied Logic, 163(8):968-1008, 2012. URL: https://doi.org/10.1016/j.apal.2011.12.020.
  7. Vasco Brattka, Guido Gherardi, Rupert Hölzl, Hugo Nobrega, and Arno Pauly. Borel choice. in preparation. Google Scholar
  8. Vasco Brattka, Guido Gherardi, and Arno Pauly. Weihrauch complexity in computable analysis, 2017. URL: https://arxiv.org/abs/1707.03202.
  9. Vasco Brattka and Peter Hertling. Feasible real random acess machines. Journal of Complexity, 14:490-526, 1998. URL: https://doi.org/10.1006/jcom.1998.0488.
  10. Vasco Brattka, Peter Hertling, and Klaus Weihrauch. A tutorial on computable analysis. In Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 425-491. Springer, 2008. URL: https://link.springer.com/chapter/10.1007/978-0-387-68546-5_18.
  11. Vasco Brattka and Arno Pauly. On the algebraic structure of Weihrauch degrees. Logical Methods in Computer Science, 14(4):1-36, 2018. URL: https://doi.org/10.23638/LMCS-14(4:4)2018.
  12. Vasco Brattka and Gero Presser. Computability on subsets of metric spaces. Theoretical Computer Science, 305(1-3):43-76, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00693-X.
  13. Peter Bürgisser and Felipe Cucker. Counting complexity classes for numeric computations ii: Algebraic and semialgebraic sets. Journal of Complexity, 22(2):147-191, 2006. URL: https://doi.org/10.1016/j.jco.2005.11.001.
  14. Thomas Chadzelek and Günter Hotz. Analytic machines. Theoretical Computer Science, 219:151-167, 1999. URL: https://doi.org/10.1016/S0304-3975(98)00287-4.
  15. Matthew de Brecht. Levels of discontinuity, limit-computability, and jump operators. In Vasco Brattka, Hannes Diener, and Dieter Spreen, editors, Logic, Computation, Hierarchies, pages 79-108. de Gruyter, 2014. URL: https://doi.org/10.1515/9781614518044.79.
  16. Matthew de Brecht, Arno Pauly, and Matthias Schröder. Overt choice. Computability, 2020. available at https://arxiv.org/abs/1902.05926. URL: https://doi.org/10.3233/COM-190253.
  17. Hugo de Holanda Cunha Nobrega. Game characterizations of function classes and Weihrauch degrees. M.Sc. thesis, University of Amsterdam, 2013. URL: https://eprints.illc.uva.nl/905/1/MoL-2013-16.text.pdf.
  18. Tobias Gärtner and Martin Ziegler. Real analytic machines and degrees. Logical Methods in Computer Science, 7:1-20, 2011. URL: https://doi.org/10.2168/LMCS-7(3:11)2011.
  19. Christine Gaßner. On NP-completeness for linear machines. Journal of Complexity, 13:259-271, 1997. URL: https://doi.org/10.1006/jcom.1997.0444.
  20. Christine Gaßner. The P-DNP problem for infinite abelian groups. Journal of Complexity, 17:574-583, 2001. URL: https://doi.org/10.1006/jcom.2001.0583.
  21. Christine Gaßner. A hierarchy below the halting problem for additive machines. Theory Computing Systems, 17:574-583, 2008. URL: https://doi.org/10.1007/s00224-007-9020-y.
  22. Christine Gaßner. An introduction to a model of abstract computation: the BSS-RAM model. In Adrian Rezus, editor, Contemporary Logic and Computing, volume 1 of Landscapes in Logic, pages 574-603. College Publications, 2020. Google Scholar
  23. Christine Gaßner and Pedro F. Valencia Vizcaíno. Operators for BSS RAM’s. In Martin Ziegler and Akitoshi Kawamura, editors, The Twelfth International Conference on Computability and Complexity in Analysis, pages 24-26, 2015. Google Scholar
  24. Vassilios Gregoriades, Tamás Kispéter, and Arno Pauly. A comparison of concepts from computable analysis and effective descriptive set theory. Mathematical Structures in Computer Science, 27(8):1414-1436, 2017. 2015. URL: https://doi.org/10.1017/S0960129516000128.
  25. Anders C. Hansen. On the solvability complexity index, the n-pseudospectrum and approximations of spectra of operators. Journal of the AMS, 24:81-124, 2011. Google Scholar
  26. Armin Hemmerling. Computability of string functions over algebraic structures. Mathematical Logic Quarterly, 44(1):1-44, 1998. URL: https://doi.org/10.1002/malq.19980440102.
  27. Denis R. Hirschfeldt and Carl G. Jockusch. On notions of computability-theoretic reduction between Π¹₂-principles. Journal of Mathematical Logic, 16(1), 2016. 1650002:1-1650002:59. URL: https://doi.org/10.1142/S0219061316500021.
  28. Klaus Meer. Counting problems over the reals. Theoretical Computer Science, 242:41-58, 2000. URL: https://doi.org/10.1016/S0304-3975(98)00190-X.
  29. Yiannis N. Moschovakis. Abstract first order computability. I. Transactions of the American Mathematical Society, 138:427-464, 1969. URL: https://doi.org/10.2307/1994926.
  30. Eike Neumann and Arno Pauly. A topological view on algebraic computations models. Journal of Complexity, 44:1-22, 2018. URL: https://doi.org/10.1016/j.jco.2017.08.003.
  31. Arno Pauly. On the topological aspects of the theory of represented spaces. Computability, 5(2):159-180, 2016. URL: https://doi.org/10.3233/COM-150049.
  32. Arno Pauly and Matthew de Brecht. Towards synthetic descriptive set theory: An instantiation with represented spaces. http://arxiv.org/abs/1307.1850, 2013. Google Scholar
  33. Arno Pauly and Matthew de Brecht. Non-deterministic computation and the Jayne Rogers theorem. Electronic Proceedings in Theoretical Computer Science, 143:87-96, 2014. DCM 2012. URL: https://doi.org/10.4204/EPTCS.143.8.
  34. Arno Pauly and Matthew de Brecht. Descriptive set theory in the category of represented spaces. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 438-449, 2015. URL: https://doi.org/10.1109/LICS.2015.48.
  35. Arno Pauly and Florian Steinberg. Comparing representations for function spaces in computable analysis. Theory of Computing Systems, 62(3):557-582, 2018. URL: https://doi.org/10.1007/s00224-016-9745-6.
  36. Marian Pour-El and Ian Richards. Computability in analysis and physics. Perspectives in Mathematical Logic. Springer, 1989. Google Scholar
  37. Florian Steinberg. Complexity theory for spaces of integrable functions. Logical Methods in Computer Science, 13(3):1-39, 2017. URL: https://doi.org/10.23638/LMCS-13(3:21)2017.
  38. Nazanin Tavana and Klaus Weihrauch. Turing machines on represented sets, a model of computation for analysis. Logical Methods in Computer Science, 7:1-21, 2011. URL: https://doi.org/10.2168/LMCS-7(2:19)2011.
  39. John V. Tucker and Jeffrey I. Zucker. Computable functions and semicomputable sets on many-sorted algebras. In T.S.E. Maybaum S. Abramsky, D.M. Gabbay, editor, Handbook of Logic in Computer Science, volume 5 of Oxford Science Publications, pages 317-523, 2000. Google Scholar
  40. Klaus Weihrauch. Computable Analysis. Springer-Verlag, 2000. Google Scholar
  41. Linda Westrick. A note on the diamond operator. Computability, 202X. to appear. URL: https://doi.org/10.3233/COM-200295.
  42. Martin Ziegler. Computability and continuity on the real arithmetic hierarchy and the power of type-2 nondeterminism. In Barry S. Cooper, Benedikt Löwe, and Leen Torenvliet, editors, Proceedings of CiE 2005, volume 3526 of Lecture Notes in Computer Science, pages 562-571. Springer, 2005. URL: https://link.springer.com/chapter/10.1007/11494645_68.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact