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 complexitytheoretic 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 complexitytheoretic 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 rationalreal computation gap relative to ￠2 oracles of the arithmetical hierarchy. We have shown that ￠2 is a tight bound for the rationalreal 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 


