Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-04T19:25:58.125Z Has data issue: false hasContentIssue false
  • English
  • Français

Absolutely non-computable predicates and functions in analysis†

Published online by Cambridge University Press:  01 February 2009

KLAUS WEIHRAUCH ,
YONGCHENG WU  and
DECHENG DING
KLAUS WEIHRAUCH
Affiliation:
Department of Mathematics and Computer Science, University of Hagen, Germany Email: [email protected]
YONGCHENG WU
Affiliation:
Nanjing University of Information Science and Technology, 210044 Nanjing, China Email: [email protected]
DECHENG DING
Affiliation:
Department of Mathematics, Nanjing University, 210093 Nanjing, China Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In the representation approach (TTE) to computable analysis, the representations of an algebraic or topological structure for which the basic predicates and functions become computable are of particular interest. There are, however, many predicates (like equality of real numbers) and functions that are absolutely non-computable, that is, not computable for any representation. Many of these results can be deduced from a simple lemma. In this article we prove this lemma for multi-representations and apply it to a number of examples. As applications, we show that various predicates and functions on computable measure spaces are absolutely non-computable. Since all the arguments are topological, we prove that the predicates are not relatively open and the functions are not relatively continuous for any multi-representation.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 19 , Special Issue 1: Theory and Applications of Models of Computation (TAMC) , February 2009 , pp. 59 - 71
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bauer, H. (1974) Wahrscheinlichkeitstheorie und Grundzüge der, Walter de Gruyter, Berlin.CrossRefGoogle Scholar
Bauer, H. (2001) Measure and Integration Theory, Walter de Gruyter, Berlin.CrossRefGoogle Scholar
Cohn, D. L. (1980) Measure Theory, Birkhäuser.CrossRefGoogle Scholar
Ding, D., Weihrauch, K. and Wu, Y. (2007) Absolutely non-effective predicates and functions in computable analysis. In: Cai, J.-Y., Cooper, S. B. and Zhou, H. (eds.) Theory and Applications of Models of Computation. Springer-Verlag Lecture Notes in Computer Science 4484 595–604.CrossRefGoogle Scholar
Engelking, R. (1989) General Topology, Sigma series in pure mathematics 6, Heldermann, Berlin.Google Scholar
Hertling, P. (1999) A real number structure that is effectively categorical. Mathematical Logic Quarterly 45 (2)147–182.CrossRefGoogle Scholar
Schröder, M. (2003) Admissible representations for continuous computations. Dissertation. Informatik Berichte 299, FernUniversität Hagen, Hagen, April 2003.Google Scholar
Weihrauch, K. (1993) Computability on computable metric spaces. Theoretical Computer Science 113 191–210.CrossRefGoogle Scholar
Weihrauch, K. (2000) Computable Analysis, Springer, Berlin.CrossRefGoogle Scholar
Weihrauch, K. (2008) The computable multi-functions on multi-represented sets are closed under programming. To appear in Journal of Universal Computer Science.Google Scholar
Wu, Y. and Ding, D. (2005) Computabibility of measurable sets via effective metrics. Mathematical Logic Quarterly 51 (6)543–559.CrossRefGoogle Scholar
Wu, Y. (2005) Computable Measure Theory, Ph.D. Dissertation, Nanjing University.Google Scholar
Wu, Y. and Ding, D. (2006) Computabibility of measurable sets via effective topologies. Archive for Mathematical Logic 45 365–379.CrossRefGoogle Scholar
Wu, Y. and Weihrauch, K. (2006) A computable version of the Daniell–Stone theorem on integration and linear functionals. Theoretical Computer Science 359 (1-3)28–42.CrossRefGoogle Scholar