Turing Computability of the Fourier Transform of Bandlimited Functions
Holger Boche, Ullrich J. Mönich · 2019
The Fourier transform is an essential operation in information sciences. However, it can rarely be calculated in closed form. Nowadays, digital computers are used to compute the Fourier transform. In this paper we study the computability of the Fourier transform. We construct an absolutely integrable bandlimited function that is computable as an element of L2, such that its Fourier transform is not Turing computable. This means the Fourier transform is not computable on a digital computer, because we have no way of effectively controlling the approximation error. This result has consequences for algorithms that use the Fourier transform of bandlimited function, e.g., the computation of the convolution via a multiplication in the Fourier domain.