3
$\begingroup$

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 that $K(k)<n-\log(n)$), then $m_2$ would be slightly smaller than $n$. That would mean $BB(m_2)>BB(n)$ and $m_2<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<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)<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)<n-\log(n)$ for any potential value of $(n,k)$, but no longer inconceivable.

$\endgroup$
  • 1
    $\begingroup$ Your argument just shows that busy beaver numbers have high Kolmogorov complexity (your last option). Your machine $M_1$ can be easily implemented as a Turing machine. There’s absolutely no contradiction, only to your intuition. $\endgroup$ – Yuval Filmus Mar 19 at 16:34
  • $\begingroup$ @YuvalFilmus No, those aren't busy beaver numbers. $k$ represents the number of machines with $n$ states which halt. There isn't any reason in particular why those numbers would have high Kolmogorov complexity, especially since (depending on the enumeration) there are a large number of equivalent machines and thus a large number of equivalent consecutive $k$s which would all need high Kolmogorov complexity. $\endgroup$ – Spitemaster Mar 19 at 16:50
  • $\begingroup$ Your argument might be less confusing if you wrote it down using Kolmogorov complexity rather than your $\mathbb S$ measure. $\endgroup$ – Yuval Filmus Mar 19 at 17:17
  • 1
    $\begingroup$ @AndrejBauer Suppose $M_1(n, k_1)$ halts in $x$ steps. Then there exists a $k_0\leq k_1$ such that $M_1(n, k_0)$ halts in $x$ steps but $M_1(n, k_0 - 1)$ halts in fewer than $x$ steps. We can say $k_0<k_1$ because in some enumerations of Turing machines there are many equivalent machines (up to order of states, etc.). Does that explain it? $\endgroup$ – Spitemaster Mar 19 at 20:01
  • 1
    $\begingroup$ @Spitemaster As for your post, everything is clear prior to the paragraph beginning "Now, $K(n)$ is at most O(log(n))". However that paragraph is less than clear, and all based on intuition and heuristics. What you should do is put some time into formalizing this paragraph; in particular, how exactly are you choosing $n$ and $k$? Your argument that $k$ has kolmogorov complexity $O(n)$ seems particularly suspect, as $k$ is some arbitrary, uncomputable number that you don't get to control (and just the fact that $k$ is between $k_0$ and $k_1$ doesn't give much flexibility). $\endgroup$ – 6005 Mar 19 at 20:07
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ A very small fragment of Python, which can easily be formalized, is quite clearly Turing complete, so I wouldn't worry about that. $\endgroup$ – Andrej Bauer Mar 19 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.