Live data from Hacker News

BB(3, 4) > Ack(14)

sligocki.com

81–90 of 114 posts

Re: BB(3, 4) > Ack(14)

#81
post #49
post #41

There are only so many Turing machines that we can possibly describe with a not too large amount of symbols such as 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC. The fact that some of these can make such a crazy large number of steps before halting to me is mind blowing.

There are 2^60 such 3 state 4 symbol Turing machines. A 49-bit lambda term whose output (normal form) exceeds Graham's Number should blow your mind even more.

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

Re: BB(3, 4) > Ack(14)

#83
post #80

Earlier quoted context omitted.

Ok, so what you seem to have said in this thread is that the system today is a huge contributor to the replication crisis but any suggestion that things could be done differently is met with an endless barrage of questions and resistance that no, it had to be done this way. So your complaint is that there’s a system at all instead of anarchy? Really not sure what point you’re trying to make.

Maybe re-reading my original comment will help clarify: https://news.ycombinator.com/item?id=40456188

Not really no. I suggested that you can decouple tenure (1900s) from modern peer review (1970s). Citations aren't an issue when publishing (you can publish anywhere) a result but are maybe more of an issue when you have a collaborative body of work (e.g. closer to open-source software development). But even still you can have citations (e.g. the citation using the Discord channel). For some reason you seemed to take the position that citations are inextractable from peer review. The grant mechanism is definitely a problem because of how it interacts with university funding, but the grant selection mechanism can evolve to be closer to how entrepreneurs work in the business market (which has its own pluses and minuses). What I suggested though is that even if you completely remove the modern peer review system, you'll still be left with the replication crises because. You've seem to have taken issue both with the suggestion that peer review is removable from academia and completely failed to engage with the issues that have nothing to do with peer review.

1. Issues around funding are a higher order problem with peer review only being a symptom at best (if at all). For example, Sabine talks about the issues and focuses on grants and spends 0 time on modern peer review.

2. Fraud didn't come into being because of peer review but grows with funding. The more funding the bigger the problem. Conversely the less funding the more likely proportionally the research is fraudulent or of poor quality because there's a smaller community checking the work. We know that the more funding we spend, the more research activity a field experiences. We don't have good ways to sift out fraud proactively - it takes disproportionately more work to root out fraud and bad science than it is to publish that & reap the rewards. This is true beyond academia - it's easier to spew BS than it is to explain the truth.

3. Not registering for null results has nothing to do with peer review. It's more just "hey I did this work and I'm not going to get rewarded so I'm not going to bother spending the work to publish the null result". That exists independent of the modern peer review system & even publish/perish is ancillary to this - a null result amounts to "failure" emotionally and that can be hard to deal with. That's why there's systems now to mandate pre-registration of the experiment - so that meta analysis can determine whether or not a result has actually been replicated enough to reduce the risk of p-hacking.

4. The replication crises for particle physics is a stark example how peer review is not really contributing as much. There's two schools of thought. The first is that we just follow the math and use data to refine which mathematical model to pick. The second is that we need to come up with better philosophical underpinnings for what the math is telling us. For now the first school is winning in terms of funding dollars (& results), but it's really hard to determine a priori which path is actually the one we should be following. Moreover, the orthodoxy exists independent of the peer review system (& even independent of grant proposals).

Re: BB(3, 4) > Ack(14)

#84
post #80

Earlier quoted context omitted.

Maybe re-reading my original comment will help clarify: https://news.ycombinator.com/item?id=40456188

Not really no. I suggested that you can decouple tenure (1900s) from modern peer review (1970s). Citations aren't an issue when publishing (you can publish anywhere) a result but are maybe more of an issue when you have a collaborative body of work (e.g. closer to open-source software development). But even still you can have citations (e.g. the citation using the Discord channel). For some reason you seemed to take…

> Not really no.

Well, then I don't know what to tell you. My point is that the contemporary peer review process is still operating under constraints that date back to the pre-internet age, and so that process could probably stand to be improved, and using the web might be part of that, and so the presence of a discord link as a citation is not necessarily something to lament. It might be part of the solution rather than the problem.

Re: BB(3, 4) > Ack(14)

#85

Can someone point me to some resources as to how to interpret the table, which I assume is some sort of description for a Turing machine?

In Python:

    def L():
        global index, tape
        if index: index -= 1
        else: tape.insert(0, 0)

    def R():
        global index, tape
        index += 1
        if index >= len(tape): tape.append(0)

    table = {
     ('A', 0): (1, R, 'B'),
     ('A', 1): (3, L, 'B'),
     ('A', 2): (1, R, 'Z'),
     ('A', 3): (2, R, 'A'),
     ('B', 0): (2, L, 'C'),
     ('B', 1): (3, R, 'B'),
     ('B', 2): (1, L, 'C'),
     ('B', 3): (2, R, 'A'),
     ('C', 0): (3, R, 'B'),
     ('C', 1): (1, L, 'B'),
     ('C', 2): (3, L, 'C'),
     ('C', 3): (2, R, 'C'),
     }

    state = 'A'
    tape = [0]
    index = 0
    while state != 'Z':
        tape[index], direction, state = table[state, tape[index]]
        direction()

Re: BB(3, 4) > Ack(14)

#86
post #82

Is it not true that BB(5) > BB(3,4)? On the https://bbchallenge.org site it said they're trying to prove or disprove the conjecture that BB(5) is about 47 million but BB(3,4) is apparently much bigger than that.

Yes, it seems that BB(3, 4) >>> BB(5, 2) (BB(5) = BB(5, 2)). This is not too surprising since BB(3, 4) has 12 transitions in it's table (3*4), while BB(5, 2) only has 10. But it seems that also BB(3, 4) >> BB(6, 2) (which both have the same number of transitions, so it appears that having more symbols is valuable to these little TMs.

Re: BB(3, 4) > Ack(14)

#87
post #70

Earlier quoted context omitted.

What I mean is that instead of measuring the bits of a particular program BB(n,k), we could instead define a function BBWOHT(n,k) ("Busy Beaver With One Halting Transition"), and measure the bits of a particular BBWOHT(n,k) program, which would be fewer bits than in the equivalent BB(n,k) program. Perhaps this is semantic games, but I'm trying to get at the idea that while there may be 60 bits of information in the B…

There are many inefficiencies in Turing Machines which you could try to work around with increasingly complicated encodings. But that will never yield a provably optimal machine encoding such as you can obtain with BBλ2 [1]. [1] https://oeis.org/A361211

Can you clarify what you mean by BBλ being "provably optimal"? IIUC BB functions for any Turing-complete computation model should be equivalent up to a constant. Maybe something like: there exists N, c: forall n >= N: BBλ(n) < BB(n + c) and vice-versa. I am not sure what the exact equation will be off-hand, maybe in this case we will need to replace BB() with a version based on binary encoding of TMs.

Re: BB(3, 4) > Ack(14)

#88

Earlier quoted context omitted.

If you mean multiple halting transitions , then it doesn't really help for BB purposes. If the machine does halt, then only one of the halting transitions will ever be taken, and the others will be 'dead code'. If you mean multiple halting states , then that is possible, and it can be used as a model of computation for, e.g., computable functions returning a single bit as output. But you still don't gain any addition…

What I mean is that instead of measuring the bits of a particular program BB(n,k), we could instead define a function BBWOHT(n,k) ("Busy Beaver With One Halting Transition"), and measure the bits of a particular BBWOHT(n,k) program, which would be fewer bits than in the equivalent BB(n,k) program. Perhaps this is semantic games, but I'm trying to get at the idea that while there may be 60 bits of information in the B…

Limiting to one halt does easily shave off a few bits.

Looking at the state transitions:

12 * log2(3+1) is 24 bits

log2(12) + 11 * log2(3) is only 21.02 bits

And since the specific output symbol and movement direction of the halting state don't matter, that's another few bits you can throw away.

So that gets you down to 54.02 bits before you even consider factoring out symmetries.

Re: BB(3, 4) > Ack(14)

#89
post #70

Earlier quoted context omitted.

There are many inefficiencies in Turing Machines which you could try to work around with increasingly complicated encodings. But that will never yield a provably optimal machine encoding such as you can obtain with BBλ2 [1]. [1] https://oeis.org/A361211

Can you clarify what you mean by BBλ being "provably optimal"? IIUC BB functions for any Turing-complete computation model should be equivalent up to a constant. Maybe something like: there exists N, c: forall n >= N: BBλ(n) < BB(n + c) and vice-versa. I am not sure what the exact equation will be off-hand, maybe in this case we will need to replace BB() with a version based on binary encoding of TMs.

As the OEIS entry says:

> for any other busy beaver BB based on self-delimiting programs, there is a constant c such that a(c+n) >= BB(n)

This requires an information theoretic measure of program size, such as bits or bytes, whereas the TM-based BB measures in states. I don't believe there are additively tight bounds on how many states are needed to encode an arbitrary string of n bits.

Re: BB(3, 4) > Ack(14)

#90

If you know, you know I guess. I certainly have no idea.

The acronyms refer to:

https://en.wikipedia.org/wiki/Busy_beaver

https://en.wikipedia.org/wiki/Ackermann_function

As I understand it, the game around functions like this is to get as close to infinity as you can, but not quite, and then to try to uncover properties about what you find there.

I'm under the impression that it's a certain kind of fun because the results are all way too large to work with computationally, so rather than comparing the values (which you can't calculate directly) you have to reason about the various algorithms that yield them.

That's all I got. The gust of the post is greek to me. I wish I had more computer science and less software engineering under my belt. Then maybe this could be my kind of fun too.

Post reply on HN