EUVIMEDEUVIMED entdecken
Crossref

Abstract versus concrete computation on metric partial algebras

J. V. Tucker, J. I. Zucker

ACM Transactions on Computational Logic · 2004

DOI: 10.1145/1024922.1024924 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, 2004. Verfasst von J. V. Tucker und 1 weiteren Autor:innen. Die Arbeit wurde bisher 40-mal zitiert (Crossref) und nennt 41 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In the theory of computation on topological algebras there is a considerable gap between so-called abstract and concrete models of computation. In concrete models, unlike abstract models, the computations depend on the representation of the algebra. First, we show that with abstract models, one needs algebras with partial operations, and computable functions that are both continuous and many-valued. This many-valuedness is needed even to compute single-valued functions, and so abstract models must be nondeterministic even to compute deterministic problems. As an abstract model, we choose the "while"-array programming language, extended with a nondeterministic "countable choice" assignment, called the WhileCC* model. Using this, we introduce the concept of approximable many-valued computation on metric algebras. For our concrete model, we choose metric algebras with effective representations. We prove:(1) for any metric algebra A with an effective representation α, WhileCC* approximability implies computability in α, and (2) also the converse, under certain reasonable conditions on A. From (1) and (2) we derive an equivalence theorem between abstract and concrete computation on metric partial algebras. We give examples of algebras where this equivalence holds.

Zitieren

APA

Tucker, J. V., & Zucker, J. I. (2004). Abstract versus concrete computation on metric partial algebras. ACM Transactions on Computational Logic. https://doi.org/10.1145/1024922.1024924

Vancouver

Tucker JV, Zucker JI. Abstract versus concrete computation on metric partial algebras. ACM Transactions on Computational Logic. 2004. doi:10.1145/1024922.1024924

BibTeX
@article{Tucker2004,
  author = {Tucker, J. V. and Zucker, J. I.},
  title = {Abstract versus concrete computation on metric partial algebras},
  journal = {ACM Transactions on Computational Logic},
  year = {2004},
  doi = {10.1145/1024922.1024924}
}
Kostenlos starten →