# What is the VC dimension of Turing machines with specified maximum size?

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 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.

• 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 supports Monica Feb 21 '18 at 2:32
• @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 Feb 21 '18 at 4:05
• the description of the finite state machine should be finite. – Thomas supports Monica Feb 21 '18 at 5:14

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, 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).

• 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 Feb 21 '18 at 15:04
• 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 Feb 21 '18 at 15:12
• 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 Feb 21 '18 at 15:24
• The two bounds match up to constants. – Aryeh Feb 21 '18 at 16:00
• 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 Feb 21 '18 at 16:06