On the limits of computations with the floor function (Q1112603)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the limits of computations with the floor function |
scientific article |
Statements
On the limits of computations with the floor function (English)
0 references
1988
0 references
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)\).
0 references
decidable languages
0 references
analytic computation tree
0 references
real function
0 references
analytic functions
0 references
floor function
0 references
algebraic computation trees
0 references
halting
0 references
measurable sets
0 references