Kihara, Takayuki ;
Pauly, Arno
Dividing by Zero  How Bad Is It, Really?
Abstract
In computable analysis testing a real number for being zero is a fundamental example of a noncomputable 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 welldefined 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.
BibTeX  Entry
@InProceedings{kihara_et_al:LIPIcs:2016:6470,
author = {Takayuki Kihara and Arno Pauly},
title = {{Dividing by Zero  How Bad Is It, Reallyl}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {58:158:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6470},
URN = {urn:nbn:de:0030drops64702},
doi = {10.4230/LIPIcs.MFCS.2016.58},
annote = {Keywords: computable analysis, Weihrauch reducibility, recursion theory, linear algebra}
}
2016
Keywords: 

computable analysis, Weihrauch reducibility, recursion theory, linear algebra 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

2016 