Help with finding a flaw in argument simulating large Turing machines with smaller ones

I have an argument which, if it goes through, just about proves that either:

• Programming languages are more powerful than Turing machines

• The busy beaver function ($BB()$) on Turing machines is computable

Now, I understand that it's vastly more likely that my argument has some flaw that I can't find. But it's more interesting to me how I'm wrong, rather than whether I'm wrong.
Argument

Construct a Turing machine $M_1$ as which takes as arguments (on the tape) $n, k$, simulates all Turing machines with $n$ states until $k$ of them halt, and then halts itself. This is easy to write in a programming language, as demonstrated by the following Python snippet:

def M1(n, k):
    all_machines = generate_turing_machines(n)
    is_halted = [0] * len(generate_turing_machines)
    while sum(is_halted) < k:
        for (i, machine) in enumerate(all_machines):
            machine.step()
            if machine.is_halted():
                is_halted[i] = 1

Now, let $m_1$ be the number of states required by $M_1$. Fix $n$ much greater than $m_1$. Let $k_1$ be the largest number such that $M_1(n, k_1)$ halts and $k_0$ be the smallest number such that when $M_1(n, k_0)$ halts, $k_1$ simulated Turing machines have halted (as all equivalent machines will halt on the same step). Choose $k$ with $k_0\leq k\leq k_1$. This means that $M_1(n,k)$ halts in about $BB(n)$ steps.

Construct $M_2$ which is the same as $M_1$ except the first thing it does is write $n$ and $k$ to the tape. Let $m_2$ be the number of states required by $M_2$. Then $m_1+K(n)+K(k)+C=m_2$ for some small $C$ (which is probably constant and likely $0$), with $K(n)$ being the Kolmogorov complexity of $n$ in Turing machine states.

Now, $K(n)$ is at most $O(\log(n))$. There are about $n^n$ machines with $n$ states, so $k$ is about $n^n$, and thus $K(k)$ is at most $O(\log(n^n))=O(n \cdot \log(n))$. That means that $m_2>n$. But here we have a problem: if $k$ is easier to write to the tape (so tha

Your flaw seems to be here:


Now, $K(n)$ is at most $O(\log(n))$. $k$ is about $n^n$, so $K(k)$ is at most $O(n)$. That puts $m_2$ just slightly larger than $n$.

It's true that $k$ is about $n^n$ (more precisely, $k = n^{\Theta(n)}$ or $k = 2^{\Theta(n \log n)}$, and this can be shown by upper bounding $k$ by the number of Turing machines, and lower bounding by finding a family of simple halting Turing machines). However, that doesn't imply that $K(k)$ is at most $O(n)$.
Rather, we only know that $K(k)$ is at most
$$
O(\log(n^n)) = O(n \log n).
$$

Your contradiction relies on picking $k$ so that $K(k)$ is $o(n)$ (a bit smaller than $n$). Your reasoning shows that this is impossible.

But this is not too surprising: most $k$ we expect to be about $O(n \log n)$, and $k$ is a number that holds a lot of information about Turing machines with $n$ states, so we don't expect to be able to compress such a number to smaller than $O(n)$ states itself.

P.S. Putting aside the question of whether Python is really equivalent to Turing machines (probably no one knows, as it hasn't been formally shown), your program M1 is in fact clearly expressible as a Turing machine. From this, you should be able to see that the resolutions based on M1 not being expressible as a Turing machine are not correct.

StackExchange Computer Science Q#121911, answer score: 3