Feasible Real Random Access Machines |
| |
Authors: | Vasco Brattka Peter Hertling |
| |
Institution: | aTheoretische Informatik I, FernUniversität Hagen, Postfach 940, D-58084, Hagen, Germanyf1;bDepartment of Computer Science, University of Auckland, Private Bag, 92019, Auckland, New Zealandf2 |
| |
Abstract: | We present a modified real RAM model which is equipped with the usual discrete and real-valued arithmetic operations and with a finite precision test <kwhich allows comparisons of real numbers only up to a variable uncertainty 1/(k+1). Furthermore, ourfeasible RAMhas an extended semantics which allows approximative computations. Using a logarithmic complexity measure we prove that all functions computable on a RAM in time
(t) can be computed on a Turing machine in time
(t2·log(t)·log log(t)). Vice versa all functions computable on a Turing machine in time
(t) are computable on a RAM in time
(t). Thus, our real RAM model does not only express exactly the computational power of Turing machines on real numbers (in the sense of Grzegorczyk), but it also yields a high-level tool for realistic time complexity estimations on real numbers. |
| |
Keywords: | computational complexity computability complexity in analysis |
本文献已被 ScienceDirect 等数据库收录! |
|