Technical Program

Paper Detail

Paper Title Turing Computability of the Fourier Transform of Bandlimited Functions
Paper IdentifierMO3.R4.2
Authors Holger Boche, Ullrich J. Mönich, Technical University of Munich, Germany
Session Signal Processing
Location Odéon, Level 3
Session Time Monday, 08 July, 14:30 - 16:10
Presentation Time Monday, 08 July, 14:50 - 15:10
Manuscript  Click here to download the manuscript
Abstract 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 L^2, 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.