Computing Unity in C[0,1]

By Tyler Brown


8 November 2019

Let C[0,1] denote the Banach space of all continuous functions on the unit interval with the usual supremum norm. A computable presentation of C[0,1] can be thought of as an infinite list of functions E whose span is dense in C[0,1] and such that there exists an algorithm that computes the max height of |f|, where f is any function in the rational linear span of functions in E. In 2014, A.G. Melnikov and K.M. Ng demonstrated the existence of a computable presentation P of C[0,1] in which the constant unit function 1 is not computable, i.e. there is no algorithm that can find a function in the rational linear span of vectors in P that, within arbitrary precision, approximates 1 with respect to the sup-norm. In this talk, via the use of Turing reductions, we determine the amount of extra "computational power" sufficient for computing 1 in any computable presentation of C[0,1].