<p>For channel capacity, it seems difficult to replace Shannon entropy by Kolmogorov complexity. The definition of channel capacity does not contain any mention of entropy.
Using the Shannon entropy gives the <strong><em>right formula</em></strong> for channel capacity (this is Shannon's theorem). If you replaced the formula with Shannon entropy by a formula with Kolmogorov complexity, it would presumably be a different formula, and so it would be the <strong><em>wrong answer</em></strong>.</p>

<p>If you want to send a string with Kolmogorov complexity $K$ through a channel with capacity $C$ using only slightly more than $K/C$ channel uses, this is very easy. Find the description of the Turing machine that produces the string. Then encode it with an error-correcting code so this description can be sent through the noisy channel with only a small probability of error. </p>

<p>The hard part of the source-channel separation theorem is showing that you can't do better than the obvious method (described in the previous paragraph) of first compressing and then encoding. I don't know whether anybody has proved this for Kolmogorov complexity and channel capacity, but it's a reasonable question to investigate.  </p>

CC BY-SA 3.0
2013-07-27T19:13:15.320Z
Am I missing something subtle, or does it follow from the definition of Kolmogorov complexity? *I.e.* any scheme for sending the string with asymptotically fewer than $K$ bits could be, with constant overhead, turned into a TM of size asymptotically smaller than $K$ (that is, the decoder plus the message) that reproduces the original string?
usul
CC BY-SA 3.0
2013-07-27T20:06:40.403Z
@usul: for channels which transmit bits, $C \leq 1$. On the other hand, I suspect it should be fairly easy to prove using the tools of information theory.
Peter Shor 
CC BY-SA 3.0
2013-09-14T23:55:59.900Z
@PeterShor"......If you replaced the formula with Shannon entropy by a formula with Kolmogorov complexity, it would presumably be a different formula....". How different would this formula be? Usually Kolmogorov compression provides an $\Omega(\log^{*}n)$ extra multiplicative factor in compression if the optimal number of bits is $n$ (For instance, the KC version of prime number theorem gives $\log\log{n}$ factor in the denominator). Say the capacity is $r$, then even if KC gave $\frac{r}{\log^{*}r}$, it would be interesting. Do you have any calculations? Also SE and KC are same is known.
Turbo
CC BY-SA 3.0
2013-07-25T11:27:16.483Z
2013-07-25T11:37:55.197Z
2013-07-25T11:37:55.197Z
Peter Shor 
<p>I am not sure what you are talking about when you use the local/global qualifiers on Shannon's entropy and Kolmogorov's complexity.</p>

<p>So correct me if I am wrong.</p>

<p>Shannon's entropy is computable. Kolmogorov's complexity is not. Therefore they do not describe the same problem. </p>

<p>You could see Shannon's entropy as an upper bound to Kolmogrov's complexity.</p>

CC BY-SA 3.0
2013-09-15T00:01:04.813Z
How is Shannon entropy an upper bound? I believe it is proven both are the same.
Turbo
CC BY-SA 3.0
2013-07-25T04:49:44.610Z
2013-07-25T15:18:29.450Z
2013-07-25T15:18:29.450Z
Phil
<p>Usually Shannon entropy is used to prove channel coding results. Even for source-channel separation results shannon entropy is used. Given the equivalence between Shannon (global) vs Kolmogorov (local) notions of information, has there been a study to utilize Kolmogorov complexity for these results (or atleast to replace the source coding part in source channel separation results)?</p>

CC BY-SA 3.0
2012-03-31T14:51:13.603Z
Have you taken a look at the 3rd edition of the [Li & Vitanyi book](http://homepages.cwi.nl/~paulv/kolmogorov.html)? If I'm not mistaken, the 8. chapter in the book was added in the newest edition, and contains a chapter on Information Theory. It features Shannon entropy, mutual information, rate distortion etc. analyzed in the sense of Kolmogorov complexity.
Juho
CC BY-SA 3.0
2012-03-31T17:05:27.273Z
Hi that is true. But there is no application to the noisy coding theorem of Shannon!
v s
<it.information-theory><kolmogorov-complexity><shannon-entropy>
Channel coding results using Kolmogorov complexity
v s
# Channel coding results using Kolmogorov complexity

(Asked by: username_0 on 2011-09-06)

Usually Shannon entropy is used to prove channel coding results. Even for source-channel separation results shannon entropy is used. Given the equivalence between Shannon (global) vs Kolmogorov (local) notions of information, has there been a study to utilize Kolmogorov complexity for these results (or atleast to replace the source coding part in source channel separation results)?

**Tags:** it.information-theory, kolmogorov-complexity, shannon-entropy
> **Comments:**
> **username_1**: Have you taken a look at the 3rd edition of the [Li & Vitanyi book](http://homepages.cwi.nl/~paulv/kolmogorov.html)? If I'm not mistaken, the 8. chapter in the book was added in the newest edition, and contains a chapter on Information Theory. It features Shannon entropy, mutual information, rate distortion etc. analyzed in the sense of Kolmogorov complexity.  
> **username_0**: Hi that is true. But there is no application to the noisy coding theorem of Shannon!  

---

## 2 answers

### Answer by username_2 on 2013-07-25. Score: 8

For channel capacity, it seems difficult to replace Shannon entropy by Kolmogorov complexity. The definition of channel capacity does not contain any mention of entropy.
Using the Shannon entropy gives the ***right formula*** for channel capacity (this is Shannon's theorem). If you replaced the formula with Shannon entropy by a formula with Kolmogorov complexity, it would presumably be a different formula, and so it would be the ***wrong answer***.

If you want to send a string with Kolmogorov complexity $K$ through a channel with capacity $C$ using only slightly more than $K/C$ channel uses, this is very easy. Find the description of the Turing machine that produces the string. Then encode it with an error-correcting code so this description can be sent through the noisy channel with only a small probability of error.

The hard part of the source-channel separation theorem is showing that you can't do better than the obvious method (described in the previous paragraph) of first compressing and then encoding. I don't know whether anybody has proved this for Kolmogorov complexity and channel capacity, but it's a reasonable question to investigate.

> **Comments:**
> **username_3**: Am I missing something subtle, or does it follow from the definition of Kolmogorov complexity? *I.e.* any scheme for sending the string with asymptotically fewer than $K$ bits could be, with constant overhead, turned into a TM of size asymptotically smaller than $K$ (that is, the decoder plus the message) that reproduces the original string?  
> **username_2**: @usul: for channels which transmit bits, $C \leq 1$. On the other hand, I suspect it should be fairly easy to prove using the tools of information theory.  
> **username_4**: @PeterShor"......If you replaced the formula with Shannon entropy by a formula with Kolmogorov complexity, it would presumably be a different formula....". How different would this formula be? Usually Kolmogorov compression provides an $\Omega(\log^{*}n)$ extra multiplicative factor in compression if the optimal number of bits is $n$ (For instance, the KC version of prime number theorem gives $\log\log{n}$ factor in the denominator). Say the capacity is $r$, then even if KC gave $\frac{r}{\log^{*}r}$, it would be interesting. Do you have any calculations? Also SE and KC are same is known.  

---

### Answer by username_5 on 2013-07-25. Score: 1

I am not sure what you are talking about when you use the local/global qualifiers on Shannon's entropy and Kolmogorov's complexity.

So correct me if I am wrong.

Shannon's entropy is computable. Kolmogorov's complexity is not. Therefore they do not describe the same problem.

You could see Shannon's entropy as an upper bound to Kolmogrov's complexity.

> **Comments:**
> **username_4**: How is Shannon entropy an upper bound? I believe it is proven both are the same.  

---

