What is the VC dimension of Turing machines with specified maximum size?
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).