# 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 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?

• Your definition of VC dimension is wrong. It’s the maximal size of a shattered set. – Yuval Filmus Jul 17 '19 at 15:42
• In your example, the property you state is very different from shattering. I suggest reading the definition of shattering on Wikipedia or on one of many online lecture notes. – Yuval Filmus Jul 17 '19 at 15:46
• Finally, the connection you attempt to make with universal Turing machines isn’t completely clear. This might have to do with your shaky definition of shattering. – Yuval Filmus Jul 17 '19 at 15:48
• A set C is shattered by H if for every labeling $f : C \rightarrow \{0,1\}$ there exists $h \in H$ such that $h = f$. If a set $C$ is not shattered by $H$, it means that there is some labeling $f$ such that there is no $h \in H$ where $h=f$. Why is that not the definition of shattering? – SomeoneHAHA Jul 17 '19 at 16:48
• A universal Turing machine can simulate an arbitrary Turing machine which forms part of its input. You don’t account for that. The simulated machine should be part of $C$. – Yuval Filmus Jul 17 '19 at 19:18

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.

• Thanks. Regarding the first part: If I want to show that a class does not shatter a set, why can't I consider a single $f$? I need to consider a single $f$, then show that for every $h \in H$ (in my case, indeed $2^{|C|}$ Turing machines), it holds that $h \neq f$. Is this correct? – SomeoneHAHA Jul 18 '19 at 5:23
• That's right, to show that a class does not shatter a set you need a single $f$. – Yuval Filmus Jul 18 '19 at 5:52