International Journal of Software and Informatics
1673-7288
2013
7
4
629
654
article
Rational vs. Real Computation
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.
computable analysis; modulus of continuity; polynomial time; discrete computation; Oracle Turing machines; arithmetical hierarchy
Walid Gomaa
Walid Gomaa
ijsi/article/abstract/i176