Noncomputability of VC Dimension of Classifier Families

The following theoretical result is got in the article: Vapnik-Chervonenkis capacity or, speaking otherwise, $V C$ dimension of arbitrary general recursive family of classifiers is noncomputable. $V C$ dimension ($V CD$) or capacity of families of mappings which decision rules are extracted from, is one of major concepts of machine learning theory. Practice explored that VC dimension succeeded to be found only for a few simple families of classifiers. If to take into account that machine learning implies the use of computers, consideration of VC dimension of families of general recursive functions (algorithms) will be correct. Thus makes sense to examine such families of functions, which defined by neuron networks, decision trees, SVM, and other models in-use in the tasks of machine learning only. Such families, designated $\mathscr{S}$, and functional
$$\mathscr{F} :\mathscr{S} \to VCD(\mathscr{S}),$$
determined on these families and taking on a numerical value equal to the VC-dimension of these families, are examined. By description families of general recursive functions as the lines of arbitrary length, the functional is replaced by function in Turing presentation. Noncomputability of $V CD(S)$ is further proved for arbitrary family $\mathscr{S}$. Kolmogorov complexity of family of general recursive functions $K_l(S)$ is entered to do that, where l is a variable which defines sample length. It is well known that Kolmogorov complexity of arbitrary string is noncomputable. We proved that comlexity $K_l(S)$ is noncomputable as well. Inequality
$$VCD(\mathscr{S}) \leq K_l(\mathscr{S}) < VCD(\mathscr{S}) \operatorname{log}l$$
was proven in [3]. Noncomputability of $V CD(S)$ is proved by this inequality usage.

Relation between sample compression, learnability, and $VCD$ was studied in [8]. The compression function takes away from the sample so-called the compression set, consisting of
no more than $k$ teaching examples (number $k$ is referred to the size of compression).
In the same paper [8] it was proven, that at the length of sample l and the use of family of
classifiers S there is a scheme of compression of size k, satisfying to inequality
$$V CD(\mathscr{S}) < k \leq V CD(\mathscr{S}) \operatorname{log} l.$$
We proved that the size of compression $k = k(l, \mathscr{S} )$ is noncomputable as well.