Kolmogorov complexity of classes of general recursive functions with limited capacity

The double inequality V CD(S) ≤ Kl(S) < V CD(S) log l is proven, where V CD(S) is the Vapnik —Chervonenkis Dimension of some collection of general recursive functions, Kl(S) is the Kolmogorov’s complexity of this collection S, l is the length of data set (sample) which is shattered by S. The novel pV CD approach for V CD estimation based on above inequality is suggested.