Define $ \{\sigma(n,k,m,i)\}_{i=1}^{l_m}$ an ordered set of all TMs with $ n$ states and $ k$ symbols that halt after $ m$ steps on $ \epsilon$

There are $ (2kn)^{kn}$ TMs with $ n$ states and $ k$ symbols, so $ l_m$ is always finite and so is the range of $ m$ .

If we could iterate over $ \sigma$ given $ n,k$ for all $ m,i$ , then we could decide the halting problem:

- Get $ n,k$ from input machine
- Iterate over $ \sigma$ for all $ m,i$ and check for each one if $ \sigma(n,k,m,i)$ equals the input machine, if they are equal accept.
- Reject.

This is odd because It seems very feasible to constract $ \{\sigma(n,k,m,i)\}_{i=1}^{l_m}$ using elementary combinatorics. Even settling on a (computable) combinatorial formula for $ l_m$ for all $ m$ given $ n,k$ will be enough to solve the haling problem since we will know how many machines are there that halt for each $ m$ , and we can simulate one step at a time for all the $ (2kn)^{kn}$ machines and compare each machine that halts with the input machine until reaching $ l_m$ for all $ m$ without a correct comparison and reject.

Is there a fact (independent of it contradicting the Halting problem) that makes it clear why there is no computable combinatorial formula for $ l_m(n,k)$ ? or am I missing some detail here?