Rational vs. Real Computation
    Download PDF
Walid Gomaa. Rational vs. Real Computation. International Journal of Software and Informatics, 2013,7(4):629~654
Hits: 1466
Download times: 1552
Abstract:There have been several different approaches of investigating computation over the real numbers. Among such computable analysis seems to be the most amenable to physical realization and the most widely accepted model that can also act as a unifying framework. Computable analysis was introduced by A. Turing [1936], A. Grzegorczyk [1955], and D. Lacombe [1955]. A representation based approach to the field was then developed by C. Kreitz and K. Weihrauch [1983]. Any typical representation is based on using the rationals, a countable dense subset of the reals with finite representation, to approximate the real numbers. The purpose of this article is to investigate the transition phenomena between rational computation and the completion of such computation (in some given representation) that induces a computability concept over the reals. This gives deeper insights into the nature of real computation (and generally computation over infinite objects) and how it conceptually differs from the corresponding foundational notion of discrete computation. We have studied both the computability and the complexity-theoretic transition phenomena. The main conclusion is the finding of a conceptual gap between rational and real computation manifested, for instance, by the existence of computable rational functions whose extensions to the reals are not computable and vice versa. This gap can be attributed to two main reasons: (1) continuity and smoothness of real functions play necessary roles in their computability and complexity-theoretic properties whereas the situation is the contrary in rational computation and (2) real computation is approximate and hence robust whereas rational computation is exact and rigid. Despite these negative results, if we relax our framework to include relative computation, then we can bridge the rational-real computation gap relative to ¢2 oracles of the arithmetical hierarchy. We have shown that ¢2 is a tight bound for the rational-real computational equivalence. That is, if a continuous function over the rationals is computable, then its extension to the reals is computable relative to a ¢2 oracle; and vice versa. This result can also be considered an extension of the Shoenfield's Limit Lemma from classical recursion theory to the computable analysis context.
keywords:computable analysis  modulus of continuity  polynomial time  discrete computation  Oracle Turing machines  arithmetical hierarchy
View Full Text  View/Add Comment  Download reader



Top Paper  |  FAQ  |  Guest Editors  |  Email Alert  |  Links  |  Copyright  |  Contact Us

© Copyright by Institute of Software, the Chinese Academy of Sciences

京公网安备 11040202500065号