How many Turing Machines are there that run in time $t$ or in space $s$ on inputs of length $k$? I think half the battle in answering this question lies in formulating it precisely! A search engine doesn't turn up much, so I was wondering if this is a well-known or well-studied question.

My thoughts: I think the most straightforward way to formulate this question is as in my title: Given constants $t,s,k \in \mathbb{N}$, how many TMs are there that run in $t$ steps or fewer on all inputs of size $k$, and how many TMs are there that use $s$ tape squares or fewer on all inputs of size $k$? This seems like the most direct and simple way to ask the question, but we might want to restate it in a different way -- for example, given a function $p(k)$, how many TMs are there that run in time $p(k)$ on inputs of size $k$ for all $k$ (or how "dense" are these TMs)? This seems harder to me.

We should probably fix a tape alphabet (or a Godel numbering??). We could consider two TMs with different but isomorphic state diagrams to be the same or different, either way.

The immediate problem is that there are an infinite number: Take any TM that satisfies the criteria and add "dead states". I can think of two ways to deal with this. The first (which I don't like) is to add an additional parameter: how many TMs whose description has length $\leq L$ satisfy the criteria? The second (which I prefer) is to consider two TMs equivalent on inputs of size $\leq k$ if, for all such inputs, the TMs have exactly the same behavior (enter the same states and write/move on the tape identically). Then we would restrict to the minimal TM in each equivalence class, or just ask how many equivalence classes satisfy the criteria.

Edit: As pointed out by Vor in the comments, the problem with the second approach is that it's basically the same as a circuit at that point. So how about the first one? Or is there a nicer way to formalize this question?

Any references/literature, thoughts, or answers would be very interesting and appreciated!
Given $k$, consider the set of $\mathcal{M}_k = \{ M_i \mid i \in \mathbb{N} \}$ with $M_i$ defined by

if |x| = k
  accept
else
  simulate TM i on x


The set $\mathcal{M}_k$ is a subset of the Turing machines you want to count for all $s,t$. Since it is infinite, the set you want to count is infinite, too.

As far as I can tell, this result is stable against all restrictions you impose as long as you don't restrict the set of all feasible Turing machines to be finite.