Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-05T02:07:42.715Z Has data issue: false hasContentIssue false
  • English
  • Français

On computably locally compact Hausdorff spaces

Published online by Cambridge University Press:  01 February 2009

YATAO XU  and
TANJA GRUBBA
YATAO XU
Affiliation:
Department of Mathematics, Nanjing University, Nanjing 210093, P.R. China Email: [email protected]
TANJA GRUBBA
Affiliation:
Department of Mathematics and Computer Science, University of Hagen, Hagen 58097, Germany Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Locally compact Hausdorff spaces generalise Euclidean spaces and metric spaces from ‘metric’ to ‘topology’. But does the effectivity on the latter (Brattka and Weihrauch 1999; Weihrauch 2000) still hold for the former? In fact, some results will be totally changed. This paper provides a complete investigation of a specific kind of space – computably locally compact Hausdorff spaces. First we characterise this type of effective space, and then study computability on closed and compact subsets of them. We use the framework of the representation approach, TTE, where continuity and computability on finite and infinite sequences of symbols are defined canonically and transferred to abstract sets by means of notations and representations.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 19 , Special Issue 1: Theory and Applications of Models of Computation (TAMC) , February 2009 , pp. 101 - 117
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

Brattka, V. (2003) Recursive quasi-metric spaces. Theoret. Comput. Sci. 305 17–42.CrossRefGoogle Scholar
Brattka, V. and Hertling, P. (1994) Continuity and computability of relations. Informatik Berichte 164, Fern University in Hagen.Google Scholar
Brattka, V. and Presser, G. (2003) Computability on subsets of metric spaces. Theoret. Comput. Sci. 305 43–76.CrossRefGoogle Scholar
Brattka, V. and Weihrauch, K. (1999) Computability on subsets of Euclidean space I: Closed and compact subsets. Theoret. Comput. Sci. 219 65–93.Google Scholar
Collins, P. (2005) Continuity and computability on reachable sets. Theoret. Comput. Sci. 341 162–195.CrossRefGoogle Scholar
Engelking, R. (1989) General Topology, Heldermann, Berlin.Google Scholar
Grubba, T. and Weihrauch, K. (2005) A computable version of Dini's theorem for topological spaces. Springer-Verlag Lecture Notes in Computer Science 3733 927–936.Google Scholar
Grubba, T. and Weihrauch, K. (2006) On computable metrization. In: Cenzer, D., Dillhage, R., Grubba, T. and Weihrauch, K. (eds.) Informatik Berichte 333, Fern University in Hagen 176–191.Google Scholar
Grzegorczyk, A. (1955) Computable functions. Fund. Math. 42 168–202.CrossRefGoogle Scholar
Hauck, J. (1973) Berechenbare reelle funktionen. Z. math. Logik Grundlagen Math. 19 121–140.Google Scholar
Ko, K. I. (1991) Complexity Theory of Real Functions, Birkhauser.Google Scholar
Kreitz, C. and Weihrauch, K. (1984) A unified approach to constructive and recursive analysis. In: Richter, M., Borger, E., Oberschelp, W., Schinzel, B. and Thomas, W. (eds.) Computation and Proof Theory. Springer-Verlag in Mathematics 1104 259–278.Google Scholar
Kusner, B. A. (1984) Lectures on Constructive Mathematical Analysis, Translations of Mathematical Monographs Series 60, American Mathematical Society.Google Scholar
Lacombe, D. (1955) Extension de la notion de fonction recursive aux fonctions d'une ou plusieurs variables reelles I. Comptes Rendus Academie des Sciences Paris 240 2478–2480.Google Scholar
Mazur, S. (1963) Computable Analysis. Razprawy Matematyczne 33, Warsaw.Google Scholar
Pour-El, M. B. and Richards, J. I. (1989) Computability in Analysis and Physics, Perspectives in Mathematical Logic, Springer-Verlag.CrossRefGoogle Scholar
Schröder, M. (1998) Effective metrization of regular spaces. In: Ko, K. I., Nerode, A., Pour-El, M. B., Weihrauch, K. and Wiedermann, J. (eds.) Informatik Berichte 235, Fern University in Hagen 63–80.Google Scholar
Scott, D. (1970) Outline of a mathematical theory of computation, Oxford University Press.Google Scholar
Stoltenberg-Hansen, V. and Tucker, J. V. (1999) Concrete models of computation for topological algebras. Theoret. Comput. Sci. 219 347–378.CrossRefGoogle Scholar
Turing, A. M. (1936) On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. 42 230–265.Google Scholar
Weihrauch, K. (1993) Computability on computable metric spaces. Theoret. Comput. Sci. 113 191–210.Google Scholar
Weihrauch, K. (2000) Computable Analysis, Springer-Verlag.Google Scholar
Yasugi, M., Mori, T. and Tsujii, Y. (1999) Effective properties of sets and functions in metric spaces with computability structure. Theoret. Comput. Sci. 219 467–486.CrossRefGoogle Scholar
Zhong, N. and Weihrauch, K. (2003) Computability theory of generalized functions. J. Asso. for Comp. Mach 50 (4)469–505.Google Scholar
Zhou, Q. (1996) Computable real-valued functions on recursive open and closed subsets of Euclidean space. Math. Logic Q. 42 379–409.CrossRefGoogle Scholar
Ziegler, M. (2002) Computability on regular subsets of Euclidean space. Math. Logic Q. 48 (Supplement 1)157–181.3.0.CO;2-4>CrossRefGoogle Scholar
Ziegler, M. (2004) Computable operators on regular sets. Math. Logic Q. 50 (4-5)392–404.CrossRefGoogle Scholar