TR01-088 Authors: Alexander Shen, Nikolay Vereshchagin

Publication: 28th November 2001 16:40

Downloads: 1517

Keywords:

We define Kolmogorov complexity of a set of strings as the minimal

Kolmogorov complexity of its element. Consider three logical

operations on sets going back to Kolmogorov

and Kleene:

(A OR B) is the direct sum of A,B,

(A AND B) is the cartesian product of A,B,

(A --> B) is the set of programs mapping

any element of A to an element of B.

We find complexity of certain

particular sets obtained from singelton sets (e.g. ({x}-->{y})-->{y}).