Algorithmic Characterization of the Outage Capacity of Fading Gaussian Channels

As we advance towards 6G networks, the concept of ultra-reliability takes center stage. For ensuring ultra-reliabile communication the outage requirement is crucial. In this paper, the outage capacity of slow fading channels with additive white Gaussian noise is studied from a fundamental algorithmic point of view by addressing the question of whether or not the outage 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 fading channels having a computable continuous and differentiable probability density function whose outage capacity yields a non-computable number. Moreover, it is demonstrated that for these channels, it is impossible to algorithmically determine the minimum blocklength for transmission codes needed to operate at a certain precision relative to their outage capacity.