The VC-dimension of a hypothesis class $ \mathcal{H}$ is defined to be the size of the maximal set $ C$ such that $ \mathcal{H}$ cannot shutter. This paper shows that the VC-dimension of the set of all Turing Machines with $ n$ states is $ \Theta(n \log n)$ .

However, suppose that we take the set of all such Turing machines, for $ n$ sufficiently large so that the universal Turing machine is a member of $ \mathcal{H}$ . The result states that there exists a set $ C$ (wlog, $ C \subset \{0,1\}^*$ ) of size, say, $ n^2$ , such that $ \mathcal{H}$ cannot shatter. To my understanding, it means that there is no member of $ \mathcal{H}$ which can compute the function $ $ f(x) = \begin{cases} 1 \text{ if } x \in C(1) \ 0 \text{ else} \end{cases} $ $ Where $ C(1)$ are the points with label “1”.

But $ C$ is finite hence $ f$ is clearly computable, thus there is some Turing machine $ M_C$ which computes it, therefore $ M_C$ can be simulated by the universal Turing machine, which is in $ \mathcal{H}$ , and this is a contradiction. Where is the problem with this argument?