1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Your definition of VC dimension is wrong. It’s the maximal size of a shattered set. $\endgroup$ – Yuval Filmus Jul 17 at 15:42
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 17 at 15:46
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 17 at 15:48
  • $\begingroup$ 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? $\endgroup$ – SomeoneHAHA Jul 17 at 16:48
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Jul 17 at 19:18
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – SomeoneHAHA Jul 18 at 5:23
  • $\begingroup$ That's right, to show that a class does not shatter a set you need a single $f$. $\endgroup$ – Yuval Filmus Jul 18 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.