Chain rule for Kolmogorov complexity: Difference between revisions

Revision as of 09:18, 3 February 2014

Revision as of 12:08, 5 May 2014

Line 36:

* contains the pair ''(x,y)'',

* can be [[recursively enumerable|enumerated]] given ''k'' and ''l'' (by running all programs of length ''K(x,y)'' in parallel),

* has at most ''2^K(x,y)'' elements (because there are at most 2ⁿ programs of length n).

First, suppose that ''x'' appears less than ''2^l'' times as first element. We can specify ''y'' given ''x,k,l'' by enumerating ''(a₁,b₁), (a₂,b₂), ...'' and then selecting ''(x,y)'' in the sub-list of pairs ''(x,b)''. By assumption, the index of ''(x,y)'' in this sub-list is less than ''2^l'' and hence, there is a program for ''y'' given ''x,k,l'' of length ''l + O(1)''.

Now, suppose that ''x'' appears at least ''2^l'' times as first element. This can happen for at most ''2^K(x,y)-l = 2^k'' different strings. These strings can be enumerated given ''k,l'' and hence ''x'' can be specified by its index in this enumeration. The corresponding program for ''x'' has size ''k + O(1)''. Theorem proved.

==References==

Line 53 ⟶ 52:

| isbn = 0-387-94868-6 }}

* {{cite articlenews

| last = Kolmogorov

| first = A.N.

Line 60 ⟶ 59:

| number = 5

| volume = 14

| pages = 662-664662–664

| year = 1968 }}

* {{cite articlenews

| first = A.

| last = Zvonkin

Line 71 ⟶ 70:

| volume = 25

| number = 6

| pages = 83-12483–124

| year = 1970}}

[[Category:Algorithmic information theory|*]]