Turing Meets Shannon: Algorithmic Constructability of Capacity-Achieving Codes

Holger Boche, Rafael F. Schaefer, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationICC 2021 - IEEE International Conference on Communications, Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728171227
StatePublished - Jun 2021
Externally publishedYes
Event2021 IEEE International Conference on Communications, ICC 2021 - Virtual, Online, Canada
Duration: Jun 14 2021Jun 23 2021

Publication series

NameIEEE International Conference on Communications
ISSN (Print)1550-3607


Conference2021 IEEE International Conference on Communications, ICC 2021
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Turing Meets Shannon: Algorithmic Constructability of Capacity-Achieving Codes'. Together they form a unique fingerprint.

Cite this