Uncomputability in Information Theory
B.T.A.E. Bassem Tarek Abdelraheem Elsayed Safieldeen (TU Delft - Electrical Engineering, Mathematics and Computer Science)
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)
More Info
expand_more
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.