Algorithmic Computability of the Capacity of Additive Colored Gaussian Noise Channels

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