### Abstract

The theory of Verdú and Han provides a powerful framework to analyze and study general non-independent and identically distributed (non-i.i. d.) sources and channels. Already for simple non-i.i. d. sources and channels, this framework can result in complicated general capacity formulas. Ahlswede asked in his Shannon lecture if these general capacity formulas can be effectively, i.e., algorithmically, computed. In this paper, it is shown that there exist computable non-i.i. d. sources and channels, for which the capacity is a non-computable number. Even worse, it is shown that there are non-i.i. d. sources and channels for which the capacity is a computable number, i.e., the limit of the corresponding sequence of multi-letter capacity expressions is computable, but the convergence of this sequence is not effective. This answers Ahlswede's question in a strong form, since in this case, the multi-letter capacity expressions for these sources and channels cannot be used to approximate the optimal performance algorithmically.

Original language | English (US) |
---|---|

Title of host publication | 2019 IEEE Information Theory Workshop, ITW 2019 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

ISBN (Electronic) | 9781538669006 |

DOIs | |

State | Published - Aug 2019 |

Event | 2019 IEEE Information Theory Workshop, ITW 2019 - Visby, Sweden Duration: Aug 25 2019 → Aug 28 2019 |

### Publication series

Name | 2019 IEEE Information Theory Workshop, ITW 2019 |
---|

### Conference

Conference | 2019 IEEE Information Theory Workshop, ITW 2019 |
---|---|

Country | Sweden |

City | Visby |

Period | 8/25/19 → 8/28/19 |

### All Science Journal Classification (ASJC) codes

- Software
- Computational Theory and Mathematics
- Computer Networks and Communications
- Information Systems

## Cite this

*2019 IEEE Information Theory Workshop, ITW 2019*[8989316] (2019 IEEE Information Theory Workshop, ITW 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITW44776.2019.8989316