Uncomputability in Information Theory

Master Thesis (2019)
Author(s)

B.T.A.E. Bassem Tarek Abdelraheem Elsayed Safieldeen (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Contributor(s)

D. Elkouss Coronas – Mentor (TU Delft - Quantum Information and Software)

Neil Yorke-Smith – Graduation committee member (TU Delft - Algorithmics)

M.P.T. Caspers – Graduation committee member (TU Delft - Analysis)

Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright
© 2019 Bassem Bassem Tarek Abdelraheem Elsayed Safieldeen
More Info
expand_more
Publication Year
2019
Language
English
Copyright
© 2019 Bassem Bassem Tarek Abdelraheem Elsayed Safieldeen
Graduation Date
27-08-2019
Awarding Institution
Delft University of Technology
Faculty
Electrical Engineering, Mathematics and Computer Science
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.

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