On the limits of computations with the floor function

AbstractUp to now, few models of computation with the power of evaluating discontinuous functions have been analyzed and few of their lower bounds or results on the decidability of languages are known. In this paper, we present a model of an “analytic computation tree” (ACT). These trees operate on real numbers and are able to compare real numbers, to evaluate functions on real numbers, and to evaluate certain discontinuous functions like the “floor function.” This model generalizes the model of “algebraic computation trees” introduced by Ben Or. We show by topological arguments that by ACTs one cannot decide certain classes of languages, examples of which are Qn and the set of tuples (x1,…,xn) ∈ Rn that have components which are Z-linearly or algebraically dependent