|
The Computable Multi-Functions on Multi-represented Sets are Closed under Programming
Klaus Weihrauch (University of Hagen, Germany)
Abstract: 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.
Keywords: computable analysis, flowcharts, multi-functions, multi-representations, realization, λ-abstraction
Categories: F.0
|
