No CrossRef data available.
Article contents
Absolutely non-computable predicates and functions in analysis†
Published online by Cambridge University Press: 01 February 2009
Abstract
In the representation approach (TTE) to computable analysis, the representations of an algebraic or topological structure for which the basic predicates and functions become computable are of particular interest. There are, however, many predicates (like equality of real numbers) and functions that are absolutely non-computable, that is, not computable for any representation. Many of these results can be deduced from a simple lemma. In this article we prove this lemma for multi-representations and apply it to a number of examples. As applications, we show that various predicates and functions on computable measure spaces are absolutely non-computable. Since all the arguments are topological, we prove that the predicates are not relatively open and the functions are not relatively continuous for any multi-representation.
- Type
- Paper
- Information
- Mathematical Structures in Computer Science , Volume 19 , Special Issue 1: Theory and Applications of Models of Computation (TAMC) , February 2009 , pp. 59 - 71
- Copyright
- Copyright © Cambridge University Press 2009