Uncomputability in Information Theory

Bassem Tarek Abdelraheem Elsayed Safieldeen, B.T.A.E.

Uncomputability in Information Theory

Master thesis (2019)

Authors

B.T.A.E. Bassem Tarek Abdelraheem Elsayed Safieldeen Electrical Engineering, Mathematics and Computer Science

Contributors

D. Elkouss Quantum Information and Software (mentor)

N. Yorke-Smith Algorithmics (graduation committee member)

M.P.T. Caspers Analysis (graduation committee member)

Faculty

Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science

Quantum information Finite state machine Complexity Information Entropy

To reference this document use:

http://resolver.tudelft.nl/uuid:f51aed2d-6a83-4b40-9ce6-bec29f5b69b6

More Info

expand_more

Published Date

27-08-2019

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

We present a powerful approach for learning about uncomputability and undecidability in informationtheory. Our approach is to use automata from automata theory that have undecidable properties toconstruct channels for which an information-theoretic quantity is uncomputable or undecidable. Wedemonstrate this approach by showing that, for channels with memory, capacity is uncomputable andinformation-stability is undecidable.

Files

Masters_Thesis.pdf

(pdf | 4.98 Mb)

License info not available