Computability on continuous, lower semi-continuous and upper semi-continuous real functions
type: Item
instance of: scholarly article
title: Computability on continuous, lower semi-continuous and upper semi-continuous real functions
zbMATH Open document ID: 0944.68058
DOI: 10.1016/S0304-3975(98)00045-0
published in: Theoretical Computer Science
publication date: 2000-08-21T00:00:00Z
review text: In this paper we extend computability theory to the spaces of continuous, upper semi-continuous and lower semi-continuous real functions. We apply the framework of TTE, Type-2 Theory of Effectivity, where not only computable elements but also computable functions on the spaces can be considered. First some basic facts about TTE are summarized. For each of the function spaces, we introduce several natural representations based on different intuitive concepts of ``effectivity'' and prove their equivalence. Computability of several operations on the function spaces is investigated, among others limits, mappings to open sets, images of compact sets and preimages of open sets, maximum and minimum values. The positive results usually show computability in all arguments, negative results usually express discontinuity. Several of the problems have computable but not extensional solutions. Since computable functions map computable elements to computable elements, many previously known results on computability are obtained as simple corollaries.
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 1493452
zbMATH Keywords: computability
zbMATH Keywords: effective analysis
zbMATH Keywords: continuous real function
zbMATH Keywords: semi-continuous real function
author: Klaus Weihrauch
author: Xizhong Zheng
MaRDI profile type: Publication
cites work: Category theory and computer science. 6th international conference, CTCS '95, Cambridge, United Kingdom, August 7--11, 1995. Proceedings
cites work: Q4320143
cites work: Q5520521
cites work: Q4085497
cites work: Q3994935
cites work: Effective content of the calculus of variations. I: Semi-continuity and the chattering lemma
cites work: Introduction to global optimization
cites work: Q4002474
cites work: Theory of representations
cites work: Compactness in constructive analysis revisited
cites work: Q3994907
cites work: Q3890679
cites work: Q5573961
cites work: Q4405392
cites work: Algebraically Generalized Recursive Function Theory
cites work: Some characterizations of normal and perfectly normal spaces
cites work: Type 2 recursion theory
cites work: Q3751553
cites work: Q4217582
cites work: Representations of the real numbers and of the open subsets of the set of real numbers
cites work: Q4362969
description: scientific article; zbMATH DE number 1493452