Return to Answer

"Decodable with $\varepsilon$ error probability" is tautological to "max likelihood decoder fails with probability $\varepsilon$."

"Decodable with error probability less than $\varepsilon$" is tautological to "max-a-posteriori decoder $\arg\max_{\text{message}}P(\text{message}|\text{observation})$ fails with probability less than $\varepsilon$." By the problem's definition no decoder can have error probability less than this one.

It is useful to notice from the Bayes rule formula that when all codewords are equally likely, the max-a-posteriori decoding is the same as the max likelihood decoding.

By tautology, a code is decodable iff its max likelihood decoder succeeds.

"Decodable with $\varepsilon$ error probability" is tautological to "max likelihood decoder fails with probability $\varepsilon$."

A sufficient condition for $\{P_1,\dots, P_{M_n}\}\subset \operatorname{Hull}\{P_{Y^n|X^n=x^n}| x^n\in \mathcal{X}^n\}$ to be a working codebook is that it has some $c>0$ where taking $Y_m\sim P_m$ for each $m$, then for any $\ell\!\neq\! m$ we have: $$\mathbb{P}(P_m(Y_m) \leq c\cdot P_{\ell}(Y_m))=\mathcal{o}(1/M_n).$$

Then the following will be a working decoder: "Decide $m$ was sent if $\mathbb{P}(P_m(Y_m)>c\cdot P_{\ell}(Y_m))$ for each $\ell\neq m$." For $c=1$ this is just a maximum likelihood decoder.

This is a kind of unsatisfying answer since I am suspicious that you can come up with a channel that has a codebook that can be reliably decoded, but where the decoder has to do something different than this.

By tautology, a code is decodable iff its max likelihood decoder succeeds.