Turing Machine Kernel

In Leonid's talk (Kernel Methods for Learning Languages), the question was raised if there was a computable kernel for languages decided by a Turing Machine.
Given a fixed alphabet S and x,y Î S*,
Formally define:
T(n)(x,y) : = { < H > :H is a Turing Machine with n states st. H accepts x and y }
Kn(TM)(x,y) : = |T(n)(x,y)|
Answer Claim: Kn(TM)(x,y) is NOT computable.
Proof: Suppose that there was some Turing Machine TK to compute Kn(TM)(x,y). Then we could decide ATM as follows:
H = Ön input ( < M > ,w)
  1. Enumerate all Turing Machines with n = |M| states (there are finitely many such turing machines, and M is one of them)
  2. Use Tk to compute Kn(TM)(w,w)
  3. Set finishedCounter = 0
  4. Run each enumerated machine on w in parallel (each one step at a time)
  5. If M ever Accepts/Rejects then Accept/Reject
  6. If some machine finishes (accepts or rejects) increment finishedCounter
  7. If finishedCounter = = Kn(TM)(x,y) and M has not halted then Reject (There are only Kn(TM)(w,w) turing machines with n states that accept w and hence M is not one of them). Note that Kn(TM)(x,y) of the Turing Machines MUST accept w after finitely many steps.
This is a contradiction: ATM is not decidable. Hence, Kn(TM)(x,y) is not computable.
References: Jeremiah Blocki, "Kernel Methods for Learning Languages"

File translated from TEX by TTH, version 3.77.
On 27 Feb 2007, 15:46.