Abstract
In this paper, we will observe that the notion of computability in an effectively given domain is dependent on the indexing of its basis. This indicates that we cannot identify two effectively given domains just because they are order isomorphic. We propose a suitable notion of effective isomorphism to compensate for this deficiency. Also we show that, for every recursion domain equation, there is an effectively given domain which is an initial solution to within effective isomorphism.
(Extended Abstract)
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Egli-Constable, Computability concepts for programming language semantics, Theoritical Computer Science, Vol. 2 (1976).
Kanda. A, Data types as effective objects, Theory of Computation Report No.22, Warwick University, (1977).
Markowsky-Rosen, Bases for chain complete posets, IBM Journal of Research and Development, Vol.20, No.2, (1979).
Plotkin. G, A power domain construction, SIAM Journal on Computing, Vol.5, (1976).
Rogers, H. Theory of recursive functions and effective computability, McGraw Hill, New York, (1967).
Tang. A, Recrusion theory and descriptive set theory in effectively given To-spaces, Ph.D. theesis, Princeton Univ. (1974).
Scott. D, Outline of the mathematical theory of computation, Proc. of the 4th Princeton Conference on Information Science, (1970).
Smyth. M, Effectively given domains, Theoretical Computer Science, Vol. 5 (1977).
Smyth-Plotkin, The categorical solution of recursive domain equattions, Proc. of the 18th IEEE FOCS Conference, (1977).
Editor information
Rights and permissions
Copyright information
© 1979 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kanda, A., Park, D. (1979). When are two effectively given domains identical?. In: Weihrauch, K. (eds) Theoretical Computer Science 4th GI Conference. Lecture Notes in Computer Science, vol 67. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-09118-1_19
Download citation
DOI: https://doi.org/10.1007/3-540-09118-1_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-09118-9
Online ISBN: 978-3-540-35517-5
eBook Packages: Springer Book Archive