Type-2 computability on spaces of integrable functions

摘要

Using Type-2 theory of effectivity, we define computability notions on the spaces of Lebesgue-integrable functions on the real line that are based on two natural approaches to integrability from measure theory. We show that Fourier transform and convolution on these spaces are computable operators with respect to these representations. By means of the orthonormal basis of Hermite functions in L2, we show the existence of a linear complexity bound for the Fourier transform.