Algorithmic Computability of the Signal Bandwidth

Abstract

The bandwidth of a bandlimited signal is an important number that is relevant in many applications and concepts. For example, according to the Shannon sampling theorem, the bandwidth determines the minimum sampling rate that is required for a perfect reconstruction. In this paper we consider bandlimited signals with finite energy and bandlimited signals that are absolutely integrable and analyze whether the bandwidth of these signals can be determined algorithmically. We employ the concept of Turing computability, a theoretical model that describes the fundamental limits of what can be solved algorithmically on a digital hardware, and ask if, for a given computable bandlimited signal, it is possible to compute its bandwidth on a Turing machine. We show that this is not possible in general, because there exist computable bandlimited signals for which the bandwidth is a non-computable real number. Even the weaker question if the bandwidth of a given signal is smaller than a predefined value cannot be always answered algorithmically. Further, we prove that in the case where the bandwidth in not computable, it is even impossible to algorithmically determine a sequence of upper bounds that converges to the actual bandwidth of the signal. As a positive result, we show that the set of signals whose bandwidth is larger than some given value is semi-decidable.