Algorithmic Computability of the Capacity of Gaussian Channels with Colored Noise

Designing capacity achieving coding schemes for the band-limited additive Gaussian channel with colored noise has been and is still a challenge. In this paper, the capacity of the band-limited additive Gaussian channel with colored noise is studied from a fundamental algorithmic point of view by addressing the question of whether or not the capacity can be algorithmically computed. To this aim, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It has been shown that there exist Gaussian colored noise with a computable continuous noise spectral density whose capacity is a non-computable number. Moreover, it has been demonstrated that for these channels, it is not possible to find a computable sequence of asymptotically sharp upper bounds for their capacity.