Negative Results of Computable Analysis Disappear If We Restrict Ourselves to Random (Or, More Generally, Typical) Inputs

It is well known that many computational problems are, in general, not algorithmically solvable: e.g., it is not possible to algorithmically decide whether two computable real numbers are equal, and it is not possible to compute the roots of a computable function. We propose to constraint such operations to certain sets of typical elements or sets of random elements . In our previous papers, we proposed (and analyzed) physics-motivated definitions for these notions. In short, a set T is a set of typical elements if for every definable sequences of sets An for which each An is a subset of An+1 and the intersection of all An is empty, there exists an N for which T has no common elements with AN; the definition of a set of random elements with respect to a probability measure P is similar, with the condition that the intersection of all An is empty replaced by a more general condition that this intersection has probability 0. In this paper, we show that if we restrict computations to such typical or random elements, then problems which are non-computable in the general case -- like comparing real numbers or finding the roots of a computable function -- become computable