<p>The exact VC bounds will depend on the alphabet size and the exact specification of the transition function (must it always move left or right, or can it stay put, etc). For fixed alphabet size, say 2, I think you can apply the DFA-VCdim analysis of</p>

<blockquote>
  <p>Ishigami and Tani, <a href="https://www.sciencedirect.com/science/article/pii/S0166218X96000509" rel="nofollow noreferrer">VC-dimensions of finite automata and commutative finite automata with $k$ letters and $n$ states</a>, <em>Discrete Applied Mathematics</em> <strong>74</strong> (1997), no. 3, 229-240</p>
</blockquote>

<p>to show that the VC-dim of $n$-state TM's will be $\Theta(n\log n)$.</p>

<p>Those other VC bounds you mentioned in terms of the NN connection weights are more in the spirit of SVM bounds in terms of the norm of the separating hyperplane.</p>

<p>Update: Here's a proof sketch. For a fixed alphabet size (say, 2) and $n$ states, there are $n^{cn}$ transition functions from (state,letter) to (state,letter,head move), where $c$ is a universal constant. Taking logs gives you a VC upper estimate of $O(n\log n)$. The lower bound comes from the Ishigami-Tani analysis, since an $n$-state DFA can be realized as an $n$-state TM (plus $n$ additional bits to indicate which states are accepting, but this is negligible compared to the $n^{cn}$ factor).</p>

CC BY-SA 3.0
2018-02-21T15:04:42.407Z
Why do you expect the same VC result to apply for a full Turing machine with memory tape access and much more expressive power than a finite automata (e.g. in terms of being able to shatter the data)?
Andy
CC BY-SA 3.0
2018-02-21T15:12:30.047Z
The upper bound is a simple counting argument. How many TMs are there on $n$ states over 2 letters? Somewhere in the neighborhood of $n^{cn}$, for some constant $c$. The lower bound is showing that one can actually shatter sets of log this size, which is achievable even by DFAs, up to constants -- that's what the published lower bound shows. This shows that cardinality and computational complexity are very different things. There are as many TMs as there are DFAs -- what makes TMs "richer" is is *not* that there's more of them.
Aryeh
CC BY-SA 3.0
2018-02-21T15:24:02.033Z
You've shown that TMs have VC between this upper and lower bound, but what's not clear to me is why you think the VC-dim actually lies on the the lower bound despite the increased expressive power?  Note I'm not saying there are more of them, but potentially more that are distinct in terms of what they can help shatter?
Andy
CC BY-SA 3.0
2018-02-21T16:00:46.990Z
The two bounds match up to constants.
Aryeh
CC BY-SA 3.0
2018-02-21T16:06:59.753Z
I thought you were saying that a TM has a VC-dim at least as high as a FSA (i.e. n*log n) and no higher than the number of machines (i.e. n^cn).  How are these within a constant of each other?
Andy
CC BY-SA 3.0
2018-02-21T16:38:49.760Z
You need to take the log of n^cn in which case you get a matching bound.
Aryeh
CC BY-SA 3.0
2018-02-21T16:52:32.023Z
OK, I see.  But why does your answer say "I *think* you can apply..."?  Are you actually not sure that this is correct?
Andy
CC BY-SA 3.0
2018-02-21T16:55:11.200Z
Until I write a formal proof I can’t be 100% certain but yeah I’m pretty sure:)
Aryeh
CC BY-SA 3.0
2018-02-21T07:02:54.777Z
2018-02-22T01:15:40.430Z
2018-02-22T01:15:40.430Z
Aryeh
<p>Note by "maximum size" in the question I'm referring to the size of the Turing machine's state machine.</p>

<p>I chose Turing machines in the question to make the question concrete, but I'm also more generally interested in known VC bounds for Turing-complete languages with a limit on the program length (to avoid infinite vc dimension).</p>

<p>The closest I've seen is <a href="https://www.sciencedirect.com/science/article/pii/S0166218X98000146" rel="nofollow noreferrer">this article</a> giving VC dimension for recurrent neural nets, which can be Turing complete, but have finite VC dimension in terms of the number of weights and the length of the inputs.</p>

CC BY-SA 3.0
2018-02-21T02:32:13.360Z
VC dimension is always at most log of the cardinality of the set. I.e., the number of bits needed to specify a classifier. I suspect that's the tightest bound you'll get in this situation.
Thomas Steinke
CC BY-SA 3.0
2018-02-21T04:05:02.300Z
@Thomas But in this case isn't the cardinality of the hypothesis space infinite (even with a maximum program length specified)?  Or do mean the cardinality assuming we also cap the input length?
Andy
CC BY-SA 3.0
2018-02-21T05:14:02.763Z
the description of the finite state machine should be finite.
Thomas Steinke
<machine-learning><turing-machines><vc-dimension><universal-turing-machines>
What is the VC dimension of Turing machines with specified maximum size?
Andy
# What is the VC dimension of Turing machines with specified maximum size?

(Asked by: username_0 on 2018-02-21)

Note by "maximum size" in the question I'm referring to the size of the Turing machine's state machine.

I chose Turing machines in the question to make the question concrete, but I'm also more generally interested in known VC bounds for Turing-complete languages with a limit on the program length (to avoid infinite vc dimension).

The closest I've seen is [this article](https://www.sciencedirect.com/science/article/pii/S0166218X98000146) giving VC dimension for recurrent neural nets, which can be Turing complete, but have finite VC dimension in terms of the number of weights and the length of the inputs.

**Tags:** machine-learning, turing-machines, vc-dimension, universal-turing-machines
> **Comments:**
> **username_1**: VC dimension is always at most log of the cardinality of the set. I.e., the number of bits needed to specify a classifier. I suspect that's the tightest bound you'll get in this situation.  
> **username_0**: @Thomas But in this case isn't the cardinality of the hypothesis space infinite (even with a maximum program length specified)?  Or do mean the cardinality assuming we also cap the input length?  
> **username_1**: the description of the finite state machine should be finite.  

---

## 1 answers

### Answer by username_2 on 2018-02-21. Score: 2 | Accepted answer

The exact VC bounds will depend on the alphabet size and the exact specification of the transition function (must it always move left or right, or can it stay put, etc). For fixed alphabet size, say 2, I think you can apply the DFA-VCdim analysis of

> Ishigami and Tani, [VC-dimensions of finite automata and commutative finite automata with $k$ letters and $n$ states](https://www.sciencedirect.com/science/article/pii/S0166218X96000509), *Discrete Applied Mathematics* **74** (1997), no. 3, 229-240

to show that the VC-dim of $n$-state TM's will be $\Theta(n\log n)$.

Those other VC bounds you mentioned in terms of the NN connection weights are more in the spirit of SVM bounds in terms of the norm of the separating hyperplane.

Update: Here's a proof sketch. For a fixed alphabet size (say, 2) and $n$ states, there are $n^{cn}$ transition functions from (state,letter) to (state,letter,head move), where $c$ is a universal constant. Taking logs gives you a VC upper estimate of $O(n\log n)$. The lower bound comes from the Ishigami-Tani analysis, since an $n$-state DFA can be realized as an $n$-state TM (plus $n$ additional bits to indicate which states are accepting, but this is negligible compared to the $n^{cn}$ factor).

> **Comments:**
> **username_0**: Why do you expect the same VC result to apply for a full Turing machine with memory tape access and much more expressive power than a finite automata (e.g. in terms of being able to shatter the data)?  
> **username_2**: The upper bound is a simple counting argument. How many TMs are there on $n$ states over 2 letters? Somewhere in the neighborhood of $n^{cn}$, for some constant $c$. The lower bound is showing that one can actually shatter sets of log this size, which is achievable even by DFAs, up to constants -- that's what the published lower bound shows. This shows that cardinality and computational complexity are very different things. There are as many TMs as there are DFAs -- what makes TMs "richer" is is *not* that there's more of them.  
> **username_0**: You've shown that TMs have VC between this upper and lower bound, but what's not clear to me is why you think the VC-dim actually lies on the the lower bound despite the increased expressive power?  Note I'm not saying there are more of them, but potentially more that are distinct in terms of what they can help shatter?  
> **username_2**: The two bounds match up to constants.  
> **username_0**: I thought you were saying that a TM has a VC-dim at least as high as a FSA (i.e. n*log n) and no higher than the number of machines (i.e. n^cn).  How are these within a constant of each other?  
> **username_2**: You need to take the log of n^cn in which case you get a matching bound.  
> **username_0**: OK, I see.  But why does your answer say "I *think* you can apply..."?  Are you actually not sure that this is correct?  
> **username_2**: Until I write a formal proof I can’t be 100% certain but yeah I’m pretty sure:)  

---

