On the limits of computations with the floor function (Q1112603)

The authors define the concept of an ``analytic computation tree'' (ACT) as an algorithmic model (decision tree) which operates on \({\mathbb{R}}^ n\) and at each step either (a) compares a real number with 0 and branches according to the result, or (b) computes a real function which is a composition of analytic functions and the floor function. ACTs appear thus as a direct generalization of the ``algebraic computation trees'' introduced by \textit{M. Ben-Or} [Proc. 15th Ann. ACM Symp. Theory Comput., 80-86 (1983)]. Topological arguments are used in an attempt to characterize those languages (subsets of \({\mathbb{R}}^ n)\) which are decidable by ACTs. Necessary conditions for a language to be accepted (or accepted by halting) by an ACT are derived; these are expressed in terms of zero sets with open complements or in terms of Lebesgue or Jordan measurable sets. As an application of these results, it is shown that the languages \({\mathbb{Q}}^ n\), REL (the \({\mathbb{Z}}\)-linearly dependent n-tuples of reals), and ALG (the algebraically dependent n-tuples) are accepted (but not their complements in \({\mathbb{R}}^ n)\).