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

Question

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 exists a function $f : C \rightarrow \{0,1\}$ ("labeling"), such that for every $h \in \mathcal{H}$, it holds that $h \neq f$. Since the elements of $\mathcal{H}$ are Turing machines, I say that "$h$ computes $f$" when the machine $h$ implements $f$.

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 (since we assumed $\forall h \in \mathcal{H}, f \neq h$ ). Where is the problem with this argument?

Answer 1

First, let me correct your definition of VC dimension: it is the largest size of a set which can be shattered.

If the VC dimension is $d$, then this means that for every set $C$ of size larger than $d$ there exists a function $f\colon C \to \{0,1\}$ which is not compatible with any function computed by an $n$-state Turing machine.

You are attempting to refute the claim that the VC dimension is $\Theta(n\log n)$ by showing that for any set $C$ of size $n^2$ there exists a single function $f\colon C \to \{0,1\}$ which is compatible with some function computed by an $n$-state Turing machine. However, what you need to do in order to refute the claim is to give a single set $C$ of size $n^2$ (say) such that all functions $f\colon C \to \{0,1\}$ are compatible with some function computed by an $n$-state Turing machine. Note the different quantifiers: you considered all $C$ and one $f$, but in fact you should consider a single $C$ but all $f$.

Finally, suppose that $M$ is a universal Turing machine having $n$ states. This doesn't mean that $M$ can compute arbitrary functions – in fact, $M$ computes a single function. What it does mean is that for any Turing machine $T$, $M(\langle T \rangle, x) = T(x)$. That is, if $M$ is given as input the pair $(\langle T \rangle, x)$ (where $\langle T \rangle$ is the encoding of $T$), then $M$ evaluates $T$ on $x$. This is different than what you claim, since the Turing machine being simulated is part of the input, that is, part of the set $C$.

In fact, in order to show that the collection of $n$-state Turing machines shatter a set $C$, you need to exhibit $2^{|C|}$ different Turing machines. Considering just a single universal Turing machine cannot possibly work.

Since there are only $O(n)^{O(n)}$ many different Turing machines having $n$ states (assuming the alphabet is fixed), this implies that the class of $n$-state Turing machines cannot shatter any set of size larger than $\log[O(n)^{O(n)}] = O(n\log n)$. This is how you get the upper bound on the VC dimension. The lower bound looks more challenging.