Undecidability of approximating the capacity of time-invariant Markoff channel with feedback, and non-existence of linear finite-letter conditional mutual information character

04/16/2018
by   Mukul Agarwal, et al.
0

It is proved that approximating, within an additive constant, the capacity of time-invariant Markoff channels with feedback can be posed as a problem which is undecidacable. Then, a definition for the capacity region, which we call the linear finite-letter conditional mutual information characterization is provided, and it is proved that evaluating the feasibility of achievability of a certain rate for this characterization is a decidable problem if Schanuel's conjecture is true. Thus, assuming Schanuel's conjecture is true, there is no linear finite-letter mutual information characterization for the capacity of a time-invariant Markoff channel with feedback.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset