The Computable Multi-Functions on Multi-represented Sets are Closed under Programming

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 comput- able, if it can be realized by a computable function on names. it is the purpose of this ar- ticle 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 realiz- ing 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 gen- eralize 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.