The Computable Multi-Functions on Multi-represented Sets are Closed under Programming
| dc.creator | Weihrauch,Klaus | |
| dc.date | 2008 | |
| dc.date.accessioned | 2024-02-06T12:56:21Z | |
| dc.date.available | 2024-02-06T12:56:21Z | |
| dc.description | 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. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-014-06-0801 | |
| dc.identifier | https://lib.jucs.org/article/29005/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/9664 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 14(6): 801-844 | |
| dc.subject | computable analysis | |
| dc.subject | multi-functions | |
| dc.subject | multi-representations | |
| dc.subject | realization | |
| dc.subject | flowcharts | |
| dc.subject | λ-abstraction | |
| dc.title | The Computable Multi-Functions on Multi-represented Sets are Closed under Programming | |
| dc.type | Research Article |