NEGATIVE RESULTS OF COMPUTABLE ANALYSIS DISAPPEAR IF WE RESTRICT OURSELVES TO RANDOM (OR, MORE GENERALLY, TYPICAL) INPUTS
Владик Крейнович · scholarworks - UTEP (The University of Texas at El Paso) · 2012
Abstract. 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 with An ⊇ An+1 and ∩ An = ∅, there exists an N for which AN ∩ T = ∅; the n definition of a set of random elements with respect to a probability measure P is similar, with the condition ∩ An = ∅ replaced by a more general condition lim P (An) = 0. n n 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. 1. Physically meaningful computations with real numbers: a brief reminder In practice, many quantities such as weight, speed, etc., are characterized by real numbers. To get information about the corresponding value x, we perform measurements. Measurements are never absolute accurate. As a result of each measurement, we get a measurement result ˜x; for each measurement, we usually also know the upper bound ∆ on the (absolute value of) the measurement error ∆x def = ˜x − x: |x − ˜x | ≤ ∆. To fully characterize a value x, we must measure it with a higher and higher accuracy. As a result, when we perform measurements with accuracy 2 −n with n = 0, 1,..., we get a sequence of rational numbers rn for which |x − rn | ≤ 2 −n. From the algorithmic viewpoint, we can view this sequence as an oracle that, given an integer n, returns a rational number rn. Such sequences represent real numbers in computable analysis; see, e.g., [Pou89, Wei00].