Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-02-06T13:11:41.026Z 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: zilj@math.hr
LUCIJA VALIDŽIĆ
Affiliation:
DEPARTMENT OF MATHEMATICS FACULTY OF SCIENCE UNIVERSITY OF ZAGREB 10000 ZAGREB, CROATIAE-mail: lvalidz@student.math.hr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 

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