Affordable Access

Publisher Website

Type Two Theory of Effectivity and Real PCF

Elsevier B.V.
Publication Date
DOI: 10.1016/s1571-0661(05)82509-5
  • Biology
  • Medicine


Abstract There have been many suggestions for what should be a computable real number or function. Some of these exhibited pathological properties [16]. Presently, research concentrates on domain theoretic approaches [4, 9] based on an idea of Scott [15], an application of Weihrauch's Type Two Theory of Effectivity [19, 20, 21] and an approach introduced by Pour-El and Richards for the more general case of Banach spaces [13]. All these approaches are claimed to be equivalent, but only in a few cases proofs have been given [3]. In this paper we show that a real number as well as a function on the reals are computable in Weihrauch's approach if and only if they are definable in Real PCF [5,6], an extension of the functional language PCF [12] by new ground type representing intervals which approximate real numbers.

There are no comments yet on this publication. Be the first to share your thoughts.