Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-19T03:27:53.628Z Has data issue: false hasContentIssue false
  • English
  • Français

MAXIMAL COMPUTABILITY STRUCTURES

Published online by Cambridge University Press:  30 December 2016

ZVONKO ILJAZOVIĆ  and
LUCIJA VALIDŽIĆ
ZVONKO ILJAZOVIĆ
Affiliation:
DEPARTMENT OF MATHEMATICS FACULTY OF SCIENCE UNIVERSITY OF ZAGREB 10000 ZAGREB, CROATIAE-mail: [email protected]
LUCIJA VALIDŽIĆ
Affiliation:
DEPARTMENT OF MATHEMATICS FACULTY OF SCIENCE UNIVERSITY OF ZAGREB 10000 ZAGREB, CROATIAE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A computability structure on a metric space is a set of sequences which satisfy certain conditions. Of a particular interest are those computability structures which contain a dense sequence, so called separable computability structures. In this paper we observe maximal computability structures which are more general than separable computability structures and we examine their properties. In particular, we examine maximal computability structures on subspaces of Euclidean space, we give their characterization and we investigate conditions under which a maximal computability structure on such a space is unique. We also give a characterization of separable computability structures on a segment.

Keywords

03D9968Q99computable metric spaceseparable computability structuremaximal computability structure
Type
Articles
Information
Bulletin of Symbolic Logic , Volume 22 , Issue 4 , December 2016 , pp. 445 - 468
Copyright
Copyright © The Association for Symbolic Logic 2016 

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

REFERENCES

Brattka, V. and Presser, G., Computability on subsets of metric spaces . Theoretical Computer Science, vol. 305 (2003), pp. 43–76.Google Scholar
Brattka, V. and Weihrauch, K., Computability on subsets of euclidean space i: Closed and compact subsets . Theoretical Computer Science, vol. 219 (1999), pp. 65–93.Google Scholar
Hertling, P., Effectivity and effective continuity of functions between computable metric spaces , Combinatorics, Complexity and Logic, Proceedings of DMTCS96 (Bridges, D. S. et al., editors), Springer, Berlin, 1996, pp. 264–275.Google Scholar
Iljazović, Z., Isometries and computability structures . Journal of Universal Computer Science, vol. 16 (2010), no. 18, pp. 2569–2596.Google Scholar
Melnikov, A. G., Computably isometric spaces . The Journal of Symbolic Logic, vol. 78 (2013), pp. 1055–1085.CrossRefGoogle Scholar
Mori, T., Tsujji, Y., and Yasugi, M., Computability structures on metric spaces , Combinatorics, Complexity and Logic, Proceedings of DMTCS96 (Bridges, D. S. et al., editors), Springer, Berlin, 1996, pp. 351–362.Google Scholar
Pour-El, M. B. and Richards, J. I., Computability in Analysis and Physics, Springer, Berlin, 1989.Google Scholar
Turing, A. M., On computable numbers, with an application to the entscheidungsproblem . Proceedings of the London Mathematical Society, vol. 42 (1936), pp. 230–265.Google Scholar
Weihrauch, K., Computability on computable metric spaces . Theoretical Computer Science, vol. 113 (1993), pp. 191–210.Google Scholar
Weihrauch, K., Computable Analysis, Springer, Berlin, 2000.CrossRefGoogle Scholar
Yasugi, M., Mori, T., and Tsujji, Y., Effective properties of sets and functions in metric spaces with computability structure . Theoretical Computer Science, vol. 66 (1999), pp. 127–138.Google Scholar