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) &lt; 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&gt;n$.  But here we have a problem: if $k$ is easier to write to the tape (so that $K(k)&lt;n-\log(n)$), then $m_2$ would be slightly smaller than $n$.  That would mean $BB(m_2)&gt;BB(n)$ and $m_2&lt;n$, a clear contradiction.
In my mind, these are the possible resolutions:

$M_1$ is impossible to create as a Turing machine, meaning that Python is more powerful than Turing machines are.
There is some transfinite extension to Turing machines which is not much more powerful than Turing machines in general, and $M_1$ can be written in this extension.  In other words, $M_1$ is the limit of a set of machines $M_{1,N}$, each of which can handle any $n&lt;N$.  This would probably entail the busy beaver function being computable.
There is a large set of numbers which cannot be written by a Turing machine in much fewer than $\log(k)=n$ states (we need $K(k)&lt;n-\log(n)$).  It seems impossible to me that no candidate for $(n, k)$ could be sufficiently compressed.

Where is the error in this logic?

I had previously said that $K(k)\leq O(n)$, but @6005 pointed out that was suspect.  With that fixed (to $O(n \cdot \log(n))$), it still seems very surprising to me that we can't achieve a reduction from $K(k)\approx n \cdot \log(n)$ to $K(k)&lt;n-\log(n)$ for any potential value of $(n,k)$, but no longer inconceivable.
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.