Document Open Access Logo

Dividing by Zero - How Bad Is It, Really?

Authors Takayuki Kihara, Arno Pauly

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.58.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Takayuki Kihara
Arno Pauly

Cite As Get BibTex

Takayuki Kihara and Arno Pauly. Dividing by Zero - How Bad Is It, Really?. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.58

Abstract

In computable analysis testing a real number for being zero is a fundamental example of a non-computable task. This causes problems for division: We cannot ensure that the number we want to divide by is not zero. In many cases, any real number would be an acceptable outcome if the divisor is zero - but even this cannot be done in a computable way.

In this note we investigate the strength of the computational problem Robust division: Given a pair of real numbers, the first not greater than the other, output their quotient if well-defined and any real number else. The formal framework is provided by Weihrauch reducibility. One particular result is that having later calls to the problem depending on the outcomes of earlier ones is strictly more powerful than performing all calls concurrently. However, having a nesting depths of two already provides the full power. This solves an open problem raised at a recent Dagstuhl meeting on Weihrauch reducibility.

As application for Robust division, we show that it suffices to execute Gaussian elimination.

Subject Classification

Keywords
  • computable analysis
  • Weihrauch reducibility
  • recursion theory
  • linear algebra

Metrics

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

References

  1. Jeremy Avigad and Vasco Brattka. Computability and analysis: the legacy of Alan Turing. In Rod Downey, editor, Turing’s Legacy, volume 42 of Lecture Notes in Logic, pages 1-47. Cambridge University Press, 2014. available at http://arxiv.org/abs/1206.3431. Google Scholar
  2. Émile Borel. Le calcul des intégrales définies. Journal de Mathématiques pures et appliquées, 6(8):159-210, 1912. Google Scholar
  3. 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: http://dx.doi.org/10.1016/j.apal.2011.12.020.
  4. Vasco Brattka and Guido Gherardi. Effective choice and boundedness principles in computable analysis. Bulletin of Symbolic Logic, 1:73-117, 2011. arXiv:0905.4685. URL: http://dx.doi.org/10.2178/bsl/1294186663.
  5. Vasco Brattka and Guido Gherardi. Weihrauch degrees, omniscience principles and weak computability. Journal of Symbolic Logic, 76:143-176, 2011. arXiv:0905.4679. Google Scholar
  6. Vasco Brattka, Guido Gherardi, and Rupert Hölzl. Probabilistic computability and choice. Information and Computation, 242:249-286, 2015. arXiv 1312.7305. URL: http://dx.doi.org/10.1016/j.ic.2015.03.005.
  7. Vasco Brattka, Guido Gherardi, and Alberto Marcone. The Bolzano-Weierstrass Theorem is the jump of Weak König’s Lemma. Annals of Pure and Applied Logic, 163(6):623-625, 2012. also arXiv:1101.0792. URL: http://dx.doi.org/10.1016/j.apal.2011.10.006.
  8. Vasco Brattka, Akitoshi Kawamura, Alberto Marcone, and Arno Pauly. Measuring the Complexity of Computational Content (Dagstuhl Seminar 15392). Dagstuhl Reports, 5(9):77-104, 2016. URL: http://dx.doi.org/10.4230/DagRep.5.9.77.
  9. Vasco Brattka, Stéphane Le Roux, and Arno Pauly. On the computational content of the Brouwer fixed point theorem. In S.Barry Cooper, Anuj Dawar, and Benedikt Löwe, editors, How the World Computes, volume 7318 of Lecture Notes in Computer Science, pages 56-67. Springer Berlin Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-30870-3_7.
  10. Vasco Brattka and Arno Pauly. Computation with advice. Electronic Proceedings in Theoretical Computer Science, 24, 2010. CCA 2010. URL: http://arxiv.org/html/1006.0551.
  11. Vasco Brattka and Arno Pauly. On the algebraic structure of Weihrauch degrees. arXiv 1604.08348, 2016. URL: http://arxiv.org/abs/1604.08348.
  12. Guido Gherardi and Alberto Marcone. How incomputable is the separable Hahn-Banach theorem? Notre Dame Journal of Formal Logic, 50(4):393-425, 2009. URL: http://dx.doi.org/10.1215/00294527-2009-018.
  13. Kojiro Higuchi and Arno Pauly. The degree-structure of Weihrauch-reducibility. Logical Methods in Computer Science, 9(2), 2013. URL: http://dx.doi.org/10.2168/LMCS-9(2:2)2013.
  14. Tosio Kato. Pertubation Theory for Linear Operators. Springer, 1976. Google Scholar
  15. Takayuki Kihara and Arno Pauly. Dividing by zero - how bad is it, really? arXiv:1606.04126, 2016. Google Scholar
  16. Stéphane Le Roux and Arno Pauly. Finite choice, convex choice and finding roots. Logical Methods in Computer Science, 2015. URL: http://arxiv.org/abs/1302.0380, URL: http://dx.doi.org/10.2168/LMCS-11(4:6)2015.
  17. Arno Pauly. How incomputable is finding Nash equilibria? Journal of Universal Computer Science, 16(18):2686-2710, 2010. URL: http://dx.doi.org/10.3217/jucs-016-18-2686.
  18. Arno Pauly. On the (semi)lattices induced by continuous reducibilities. Mathematical Logic Quarterly, 56(5):488-502, 2010. URL: http://dx.doi.org/10.1002/malq.200910104.
  19. Arno Pauly. Computable Metamathematics and its Application to Game Theory. PhD thesis, University of Cambridge, 2012. Google Scholar
  20. Arno Pauly. Many-one reductions and the category of multivalued functions. Mathematical Structures in Computer Science, 2015. available at: arXiv 1102.3151. URL: http://dx.doi.org/10.1017/S0960129515000262.
  21. Arno Pauly. On the topological aspects of the theory of represented spaces. Computability, 2016. accepted for publication, available at http://arxiv.org/abs/1204.3763. URL: http://dx.doi.org/10.3233/COM-150049.
  22. Arno Pauly and Florian Steinberg. Representations of analytic functions and weihrauch degrees. In Proceedings of Computer Science Russia (CSR), volume 9691 of LNCS, pages 367-381, 2016. URL: http://dx.doi.org/10.1007/978-3-319-34171-2_26.
  23. Arno Pauly and Martin Ziegler. Relative computability and uniform continuity of relations. Journal of Logic and Analysis, 5, 2013. Google Scholar
  24. Matthias Schröder. Extended admissibility. Theoretical Computer Science, 284(2):519-538, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00109-8.
  25. Alan Turing. On computable numbers, with an application to the Entscheidungsproblem: Corrections. Proceedings of the LMS, 2(43):544-546, 1937. Google Scholar
  26. Klaus Weihrauch. The degrees of discontinuity of some translators between representations of the real numbers. Informatik Berichte 129, FernUniversität Hagen, Hagen, 1992. Google Scholar
  27. Klaus Weihrauch. The TTE-interpretation of three hierarchies of omniscience principles. Informatik Berichte 130, FernUniversität Hagen, Hagen, 1992. Google Scholar
  28. Klaus Weihrauch. Computable Analysis. Springer-Verlag, 2000. Google Scholar
  29. Martin Ziegler. Real computation with least discrete advice: A complexity theory of nonuniform computability with applications to effective linear algebra. Annals of Pure and Applied Logic, 163(8):1108-1139, 2012. URL: http://dx.doi.org/10.1016/j.apal.2011.12.030.
  30. Martin Ziegler and Vasco Brattka. Computability in linear algebra. Theoretical Computer Science, 326:187-211, 2004. Google Scholar
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