Optimal Sampling Rate And Bandwidth Of Bandlimited Signals - An Algorithmic Perspective

The bandwidth of a bandlimited signal is a key quantity that is relevant in numerous applications. For example, it determines the minimum sampling rate that is necessary to reconstruct a bandlimited signal from its samples. In this paper we study if it is possible to algorithmically determine the actual bandwidth of a bandlimited signal. We prove that this is not possible in general, because there exist bandlimited computable signals, which have a bandwidth that is not computable. To this end we employ the concept of Turing computability, which provides a theoretical model that describes the fundamental limits of any practically realizable digital hardware, such as CPUs, DSPs, or FPGAs. Further, we answer the weaker question if it can be algorithmically answered whether the bandwidth of a given signal is larger than a predefined value.