cfaed Publications

@INPROCEEDINGS{8849462,
author={H. {Boche} and U. J. {Mönich}},
booktitle={2019 IEEE International Symposium on Information Theory (ISIT)},
title={Turing Computability of the Fourier Transform of Bandlimited Functions},
year={2019},
volume={},
number={},
pages={380-384},
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 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.},
keywords={approximation theory;computability;Fourier transforms;Turing machines;Turing computability;Fourier transform;digital computer;information sciences;bandlimited function;approximation error;Fourier transforms;Digital computers;Turing machines;Approximation error;Optics;Signal processing algorithms;Physics},
doi={10.1109/ISIT.2019.8849462},
ISSN={2157-8095},
month={July},}