Capacity-Achieving Input Distributions: Algorithmic Computability and Approximability

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

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

1 Scopus citations


The capacity of a channel can usually be characterized as a maximization of certain entropic quantities. From a practical point of view it is of crucial interest to not only compute the capacity value, but also to find the corresponding optimizer, i.e., the capacity-achieving input distribution. This paper addresses the general question of whether or not it is possible to find algorithms that can compute the optimal input distribution depending on the channel. For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers and therewith fully specifies which tasks are algorithmically feasible in principle. It is shown that it is impossible to algorithmically compute the capacity-achieving input distribution, where the channel is given as an input to the algorithm or Turing machine. Finally, it is further shown that it is also impossible to algorithmically approximate these input distributions.

Original languageEnglish (US)
Title of host publication2022 IEEE International Symposium on Information Theory, ISIT 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781665421591
StatePublished - 2022
Externally publishedYes
Event2022 IEEE International Symposium on Information Theory, ISIT 2022 - Espoo, Finland
Duration: Jun 26 2022Jul 1 2022

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Conference2022 IEEE International Symposium on Information Theory, ISIT 2022

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Capacity-Achieving Input Distributions: Algorithmic Computability and Approximability'. Together they form a unique fingerprint.

Cite this