BB(3, 4) > Ack(14)

To be fair, the responsibility for the replication crises is much trickier. It’s based on human motivations and poor science:

1. Outright fraud

2. Lack of independent verification of results before building up a body of work resulting in a bunch of garbage. Contributes to making #1 “easy”.

3. Financial pressures to publish or perish contributing to 1 & 2. If peer review didn’t exist you’d still something similar about producing “recognized” results. This is also probably why we haven’t done any major breakthroughs in particle physics which now has a much longer term thinking phase to come up with anything.

The biggest problem with peer review is actually the establishment of an orthodoxy which discourages itself being upended by controlling the career success of anyone who dare challenge it - you have to support the orthodoxy to get career success and you fail to get recognition if your idea challenges the peer reviewers ideas and careers. That being said, such pressures existed before, but at least you could try to build your own following and it was competing orthodoxies instead of a single one winning out.

Because Discord is a proprietary glorified IRC SaaS; its contents are, by nature, ephemeral and under control of the vendor. I'd expect such links to rot very quickly.

Collaborating on Discord is fine. Important results, including citations backing them, should really be published or at least replicated in more durable medium that's less susceptible to link rot, and easier to archive. Today, that's PDFs in paper repositories, or even regular blog posts.

But Discord isn't citable. Somebody needs to archive the Discord and make that available through the proper channels (e.g. a website, a book, the Internet Archive).

If it were foundational it would be peer reviewed in a journal article, not posted on a blog.

What I think you are doing here is to DEFINE "foundational work" as something that gets published in a journal.

I don't mind if you use that definition, but if you do then the fact that all foundational work is published in journals is not insightful or informative, it is merely the definition.

If, on the other hand, you intended for the statement to say something meaningful about how important scientific and mathematical work is communicated, then you need a different definition of "foundational". And you would have to look to that definition to decide whether this work was foundational, because if it was then it disproves your hypothesis: it would be a counter example that illustrates that some foundational work is shared in places other than journals.

That's fine, but the citation shouldn't be in the form of a Discord link, or at least not exclusively in that form. Make a copy of the relevant messages, host them elsewhere, and include that copy in the citation. Discord has been pretty good so far but being a durable archive has never been their core selling point so I don't trust that to continue indefinitely.

What's the initial state supposed to be?

I love these puzzles. GNU C supports a label as value for computed goto. This is useful for direct threaded dispatch. You trade off a branch instruction for an address lookup, but it makes the code more structured.

  int main(void) {
    void* A[] = {&&A0, &&A1, &&A2, &&A3};
    void* B[] = {&&B0, &&B1, &&B2, &&B3};
    void* C[] = {&&C0, &&C1, &&C2, &&C3};
    goto *A[SCAN];
    A0: WRITE(1); RIGHT; goto *B[SCAN];
    A1: WRITE(3); LEFT ; goto *B[SCAN];
    A2: WRITE(1); RIGHT; HALT; return 0;
    A3: WRITE(2); RIGHT; goto *A[SCAN];
    B0: WRITE(2); LEFT ; goto *C[SCAN];
    B1: WRITE(3); RIGHT; goto *B[SCAN];
    B2: WRITE(1); LEFT ; goto *C[SCAN];
    B3: WRITE(2); RIGHT; goto *A[SCAN];
    C0: WRITE(3); RIGHT; goto *B[SCAN];
    C1: WRITE(1); LEFT ; goto *B[SCAN];
    C2: WRITE(3); LEFT ; goto *C[SCAN];
    C3: WRITE(2); RIGHT; goto *C[SCAN];
  }

Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations?

Because A and C only jump to B it is possible to structure this using only loops and one boolean. Let us use Rust to demonstrate as it lacks GOTO:

    let mut a = true;
    loop {
        loop {
            if a { // state A
                match scan() {
                    0 => { write(1); right(); break }
                    1 => { write(3); left(); break }
                    2 => { write(1); right(); return }
                    3 => { write(2); right() }
                }
            } else { // state C
                match scan() {
                    0 => { write(3); right(); break }
                    1 => { write(1); left(); break }
                    2 => { write(3); left() }
                    3 => { write(2); right() }
                }
            }
        }

        a = loop { // state B
            match scan() {
                0 => { write(2); left(); break false }
                1 => { write(3); right() }
                2 => { write(1); left(); break false }
                3 => { write(2); right(); break true }
            }
        }
    }

I miscalculated. It should be 3*4*log2(4*2*(3+1))= 60 bits of information.

Do you know of any (hand-wavy is ok) intuitive explanation for why this machine will halt, beyond the inductive proof's given in your article? Just watching the machine run, I would guess at some kind of infinite behavior. It is remarkable that this is not the case.

Similarly, 2^n would be a huge overcount of the number of n-bit closed terms, which is given by OEIS sequence A114852 [1]. There are 36140122614 ~ 2^35 closed terms of size 49 bits (length of a straightforward self-delimiting encoding). So in that sense it's still a smaller lambda term computing an incomprehensibly larger output.

[1] https://oeis.org/A114852

streetlamp effect

I agree completely, all of these kinds of conjectures are shaped by what is detectable. If there are any "dark matter" programs out there, they by definition will be difficult to find. That said, I find it entirely plausible that the champions will win by exploiting complex and exotic mathematical facts, while the implementations of the math do not themselves need to be complex or exotic at the code level.

More rambling thoughts about this: https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjec...

At a high level, wouldn’t you expect Champions to be chaotic in the limit? As in, the halting problem tells us that any increasing sequence of Champions is not computable.

Handwaving here, but I think longest running machines can't follow a specific structure in general.

Rough sketch of an argument:

Let's construct a number from all intermediate states of the machine concatenated. The number of digits of this number should correspond to the runtime (sketchy). We only care about the halting machines, so it's finite. We know that it must be unique because if a smaller machine computes the same number, we could get a bigger number by simply running the smaller program and doing other nonsense. That means the biggest programs are komolgorov optimal, and the numbers themselves should be k-trivial and thus nearly but not quite computable. Since they're not computable, the programs themselves can't follow a structure to generate them (since that would be computable in turn for larger values).

2^60 is very little! Is it known what fraction of them has an insanely large run time?

Well, the goal is to get as close to infinity as possible with the smallest program possible. We can name big numbers just fine, by recursing over recursion for some number of steps, but the fun part is to have these fall out 'naturally' from the space of small Turing machines.

In this case, we can actually name the number of symbols in terms of Knuth's up-arrow notation [0], which describes the sequence of operations starting with multiplication, exponentiation, repeated exponentiation (called tetration, e.g., 2↑↑5 = 2^[2^[2^[2^2]]]), repeated tetration (called pentation, e.g., 2↑↑↑5 = 2↑↑[2↑↑[2↑↑[2↑↑2]]]), and so on. This number is big enough that it needs 15 arrows in a row to describe it reasonably. So it's not just that the number is very large, it's that we can also put a neat lid over its value. For instance, we know it's still nothing compared to Graham's number, which can't be described with any reasonable number of up-arrows.

[0] https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation

I think I can explain that. If you only have two symbols, you can encode the same information as having four symbols in two cells, so performing the same operation on them requires an extra state to read the first of the two and then move to one of two other states to handle the second. Less symbols requires more states.

This is related to the linear speed-up theorem, which roughly states that you can speed up any TM by expanding its alphabet. And speed-up is not what BB is about.

So actually, it would make sense to limit the the busy beavers to BB(n, 2) only.