A universal Turing kernel?

At the end of my talk, someone asked why I focus exclusively on DFAs. After all, my result that any countable concept class over a countable sample space is linearly separable (in this sense) works equally well for push-down automata or even Turing machines. My first (mildly petulant) answer is that DFAs are the only automata I'm comfortable with and I won't be ready to move on to more powerful automata until someone resolves the star-height problem (at which point I'll grudgingly grant humanity the right to graduate on to higher machines).

Someone else was quick to suggested that the analogous kernel for Turing machines, T_n(x,y), would have to count the number of Turing machines on n states that accept both x and y -- and surely this is undecidable. But is that obvious? Might there not be some clever way of computing the kernel without solving the halting problem?

Turns out, there is not; this was shown by Jeremiah Blocki, a student in my class -- who, incidentally, has taken up the challenge of the notorious problem #3.