
Continuous Algorithms
by
Michael D. Rice

Many of the established connections between topology and computer science involve the interplay of ordertheoretic ideas and "nonclassical" topological spaces with weak separation properties. Recently, I have been investigating the continuity (with respect to Euclidean topologies) of elementary algorithms that are widely used in computer science. In many situations, an algorithm's correctness guarantees that it will not compute a continuous function. This is the case for search algorithms or for an algorithm that computes the two nearest points in a set of points in the plane. On the other hand, an algorithm that correctly sorts sequences of real numbers of length N computes a Lipschitz mapping on Euclidean Nspace.
I have found that for a certain class of algorithms, the assumption that a member computes a continuous function between Euclidean spaces is surprisingly restrictive. Roughly speaking, this class consists of algorithms where the output data is a subset of the input data that depends on its ordertheoretic structure. The familiar algorithms used for sorting and for computing an orderstatistic are members of this class.
The lecture will present several results establishing that certain algorithms in the above class can compute only finitely many distinct continuous mappings. Therefore, in these cases, it may be possible to design decision procedures for establishing the "discontinuity of an algorithm". The proof techniques have also been used to establish a topological version of the 01 Sorting Lemma (under certain conditions an algorithm that correctly sorts sequences of 0's and 1's correctly sorts all sequences).