# How can the VC-dimension of Turing machine be finite?

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?