|
Abstract : |
In recent years the study of the complexity of computational problems involving real numbers has been an increasing research area. A foundational paper has been [4] where a computational model---the real Turing machine--- for dealing with the above problems was developed. One research direction that has been studied intensively during the last two years is the computational power of real Turing machines over binary inputs. The general problem can be roughly stated in the following way. Let us consider a class C of real Turing machines that work under some resource bound (for instance polynomial time, branching only on equality, etc.). If we restrict these machines to work on binary inputs (i.e. finite words over f0; 1g) they define a class of binary languages D. The question is, what can we say about D depending on C? More formally, let us denote by IR 1 the direct sum of countably many copies of IR and let P(IR 1) be the set of its subsets. Also, let us denote by \Sigma the subset f0; 1g of IR and---as usual--- by \Sigma, |
