The Computable Multi-Functions on Multi-represented Sets are Closed under Programming
Дата
Авторы
Weihrauch,Klaus
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
In the representation approach to computable analysis (TTE) [Grz55, KW85, Wei00], abstract data like rational numbers, real numbers, compact sets or continuous real functions are represented by finite or infinite sequences (Σ*, Σω) of symbols, which serve as concrete names. A function on abstract data is called computable, if it can be realized by a computable function on names. It is the purpose of this article to justify and generalize methods which are already used informally in computable analysis for proving computability. As a simple formalization of informal programming we consider flowcharts with indirect addressing. Using the fact that every computable function on Σω can be generated by a monotone and computable function on Σ* we prove that the computable functions on Σω are closed under flowchart programming. We introduce generalized multi-representations, where names can be from general sets, and define realization of multi-functions by multi-functions. We prove that the function computed by a flowchart over realized functions is realized by the function computed by the corresponding flowchart over realizing functions. As a consequence, data from abstract sets on which computability is well-understood can be used for writing realizing flowcharts of computable functions. In particular, the computable multi-functions on multi-represented sets are closed under flowchart programming. These results allow us to avoid the "use of 0s and 1s" in programming to a large extent and to think in terms of abstract data like real numbers or continuous real functions. Finally we generalize effective exponentiation to multi-functions on multi-represented sets and study two different kinds of λ-abstraction. The results allow simpler and more formalized proofs in computable analysis.
Ключевые слова
computable analysis , multi-functions , multi-representations , realization , flowcharts , λ-abstraction