Turing Meets Shannon: Algorithmic Constructability of Capacity-Achieving Codes

Abstract

Proving a capacity result usually involves two parts: achievability and converse which establish matching lower and upper bounds on the capacity. For achievability, only the existence of good (capacity-achieving) codes is usually shown. Although the existence of such optimal codes is known, constructing such capacity-achieving codes has been open for a long time. Recently, significant progress has been made and optimal code constructions have been found including for example polar codes. A crucial observation is that all these constructions are done for a fixed and given channel and this paper addresses the question whether or not it is possible to find universal algorithms that can construct optimal codes for a whole class of channels. For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers. It is shown that there exists no universal Turing machine that takes the channel from the class of interest as an input and outputs optimal codes. Finally, implications on channel-aware transmission schemes are discussed.