BB(3, 4) > Ack(14)
sligocki.com
sligocki.com
There are three states: A, B, C. (States are just like goto targets in C.) State B passes control to A and C, but states A and C don't "know about" each other; they only pass control back to B. This is a sort of modular construction, whereas in true spaghetti code each state would be able to pass to all the others.
This program has some other interesting features. It never prints a blank (that is, whenever it scans a 0, it prints 1, 2, or 3). Additionally, every instruction changes either the state or the color -- there are no "lazy instructions" like B1 -> 1LB that just move position without changing anything else.
Though I suspect that no long-running machine can be utterly chaotic, at least when you look at the patterns it produces on the tape. To run for a long time, a machine must simulate some sort of higher-level rule: if it were dumping symbols on the tape at random, then it would very soon reach a halting configuration, a cyclical configuration, or some other simplified pattern. Still, one can have long-running machines that do simulate something chaotic on a higher level, spending an inordinate amount of time between each high-level step until it halts.
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...
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).
An n-state s-symbol TM can transition to n other states at most (or halt). Thus, for s=4 or s=2, only the smallest of TMs could be spaghetti like.
0 1 2 3
A 1RB 3LB 1RZ 2RA
B 2LC 3RB 1LC 2RA
C 3RB 1LB 3LC 2RC
This is 3*4*log2(4*2*log2(4+1)) or about 64 bits of information. Meanwhile, in only 49 bits, BBλ(49) far exceeds Graham's number [1].
If the Halting problem could be solved by intuition, it wouldn't be much of a problem.
(Even writing of the 1 doesn't matter, though a 0 would have been suboptimal I guess. A 2 was already written on the tape there, it's being replaced by a 1 but the 2 counted just as much for 'number of symbols on the tape')
I calculate 3*4*log2(4*2*log2(4+1)) ≈ 51.
I (a layperson) would have thought the calculation would be 3*4*log2(4*2*4) = 60.
Is it perhaps 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64?
Like you can mirror the tape. You can relabel states B and C. And you can relabel symbols 1, 2, 3. Though the analysis is complicated a little bit by the fact that some (combinations) of those operations may yield the exact same machine.
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 additional running time before the machine halts.
As for no halting transitions, the problem is choosing what point to measure the tape at. One thing you can do is to put a mark on one of the transitions, then see whether the machine only runs that transition a finite number of times, or if it keeps running it forever. This yields the "Beeping Busy Beaver" numbers [0], which are uncomputable even if you have an oracle for the halting problem.
[0] https://www.sligocki.com/2021/03/06/beeping-busy-beaver/
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 BB(3,4) program, there are fewer in the BBWOHT(3,4) program, because we can prima facie exclude a bunch of "uninteresting" BB(n,k) programs from consideration if we restrict ourselves to BBWOHT(n,k), in the same way that we can exclude a bunch of "uninteresting" BB(n,k) programs from consideration if we restrict ourselves to BB(n,k) programs that aren't symmetries of other BB(n,k) programs.
> 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.
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.
If you run it for a bit you see what's going on, State B turns 0's into 2's and 1's into 1's transitioning to C and state C turns 3 -> 2's and transitions to A. So you just iteratively lengthen your run of 3's exponentially since it requires a full pass through all the 3's to fix a 2->1.
But the really tricky part to understand is why it eventually stops. After an unimaginably high number of steps.
Here's a tangent to explore:
A BitGrid[1] (my personal hobby horse) only has 4 bits of state per cell, so a 4x4 grid of cells can't count more than 2^64, no matter what. Finding the highest it could count would be interesting. For small grids, the edge connections would dominate the outcome.
#include "machine.h"
int main(void)
{
A:
switch (SCAN) {
case 0:
WRITE(1); RIGHT; goto B;
case 1:
WRITE(3); LEFT; goto B;
case 2:
WRITE(1); RIGHT; goto H;
case 3:
WRITE(2); RIGHT; goto A;
}
B:
switch (SCAN) {
case 0:
WRITE(2); LEFT; goto C;
case 1:
WRITE(3); RIGHT; goto B;
case 2:
WRITE(1); LEFT; goto C;
case 3:
WRITE(2); RIGHT; goto A;
}
C:
switch (SCAN) {
case 0:
WRITE(3); RIGHT; goto B;
case 1:
WRITE(1); LEFT; goto B;
case 2:
WRITE(3); LEFT; goto C;
case 3:
WRITE(2); RIGHT; goto C;
}
H:
HALT;
}
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];
}Why doesn't any modern C standard like C23 include this? Seems like a glaring omission.
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 }
}
}
}
> A TM string is in lexical normal form iff the following conditions obtain: …The non-initial active states first occur in ascending order…
The cell in the table describes which actions to perform. The first row & first column has "1RB" which means: "replace the symbol on the tape with '1', shift 1 symbol to the right on the tape and switch to state 'B'".
The state 'Z' corresponds to the halting state.
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()[0] https://bbchallenge.org/story#turing-machines
[1] https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti...
[2] https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2...
Despite a CS undergrad I don’t recall really learning any of these canonical representations of TMs before.
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.
The right way to reference scientific publications is by URN [1], not URL. That makes the location irrelevant, as it should be.
I'm not sure that they're collector's items, but they're probably not in that many university libraries. For example, the University of Michigan library has a physical copy in its special collection, but my university's considerably smaller library does not. But that's just because of age: this is a 119-year-old paper; were it a little younger, say, about 70 years, it would be in my university's holdings. I think that's a considerably different order of magnitude of its lifetime from a Discord link that I'd be absolutely astounded to see last a decade, and that in practice will probably last much less time than that.
I was a grad student at the institute for theoretical physics in Heidelberg. It's famously housed in two old villas with little room for books, so all the walls in almost all rooms are lined with shelfs. In the office I shared with five other students, there was one shelf in it that was locked. The only one in the building. In it was one book from 1905 that had a different color than all the others.
That's the physical copy of the papers you mean. They had issues with theft so they had to have it replaced and then lock it. It probably wasn't even original though.
so clearly discord is inherently different and here to stay forever! /s
feels like time is a circle sometimes ha
It’s shuttering.
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.
But those only exist because of the current peer-review model. There is a huge non-linearity built in to the publication process that provides disproportionate rewards for conning a small number of people, fewer than half a dozen. That, combined with a presumption of trustworthiness, produces a perverse incentive for attempting such cons because they are very easy to pull off, much easier than actually doing good science.
And how do you tell who are the leading experts in the field?
And how do you think that gets decided?
> those who get cited the most
And how do you get cited without first getting published in a peer-reviewed publication?
> whoever manages to shmooze their way onto the grant review board
Do you think it's possible to do that without a publication record?
> whoever has been doing “good” work in a space
As decided by whom?
The point is that the current system is based on a small cadre of people assessing each other's work on the assumption that they are all competent and trustworthy. The bigger the community, the easier it becomes to game the system, and the bigger the incentives to do so, and so the less reliable traditional peer review becomes as a predictor of scientific quality. To say nothing of the sheer horrible inefficiency. It takes months to do something that should take days. If anything was ever ripe for disruption, it's peer review.
BTW, here is an example of what happens when someone actually sets out to game the system and is fairly good at it:
Tenure precedes peer review afaik which I think pretty obviously negates this question - humans established tenure somehow so whatever that mechanism was. Peer review as a concept is quite old (17th century) and what these guys did on discord is peer review and collaboration. I’m assuming you’re just using shorthand to refer to journal peer review which is the more recent phenomenon.
> And how do you get cited without first getting published in a peer-reviewed publication?
Citations exist independently of peer review. Not sure why you think you can’t have one without the other. Journals are certainly not the only source cited. For example, math I believe doesn’t even generally use journals and yet citations are going strong there.
> Do you think it's possible to do that without a publication record?
Possible? Of course. Pick 10 random bureaucrats and have them pick admissions at random. Good? Well, now you seem to be arguing the pro publication position as a way of coming up with a better review board. But anyway, yes obviously there are better ways of establishing a grant review board by trying to populate it with some amount of “freethinkers”).
Were agreed that the peer review system sucks for all sorts of reasons but we’re now very far afield from what I was trying to correct which is that the replication crises has many origins and isn’t just the fault of peer reviews. You’d have it even if journals and publish or perish weren’t a thing.
Um, no. Tenure decisions turn largely on publication record, which turns on peer review.
> Citations exist independently of peer review
To cite something there has to be something to cite. It is of course possible to cite a non-peer-reviewed publication, but in academia this is heavily frowned upon. Non-peer-reviewed is generally considered synonymous with crackpottery.
> Pick 10 random bureaucrats
I meant do you think it's possible to "shmooze [your] way onto the grant review board" without a publication record in the real world, not some counterfactual world where you have stacked the deck.
> the replication crises has many origins and isn’t just the fault of peer reviews
I didn't say it was just the fault of peer review. What I said was that peer review was "probably in no small measure responsible for [the] replication crises", and I stand by that.
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).
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.
> Um, no. Tenure decisions turn largely on publication record, which turns on peer review.
I'm pretty sure your parent meant that the concept of tenure precedes the concept of peer review. However, this too seems to be false, according to the repository of truth, Wikipedia, which says that:
> The first record of an editorial pre-publication peer-review is from 1665 by Henry Oldenburg, the founding editor of Philosophical Transactions of the Royal Society at the Royal Society of London.
(https://en.wikipedia.org/wiki/Scholarly_peer_review) but:
> Tenure was introduced into American universities in the early 1900s in part to prevent the arbitrary dismissal of faculty members who expressed unpopular views.
Even if that were true, what does the historical development of these institutions have to do with the claim that contemporary peer review is responsible for the contemporary replication crisis?
Also, I'd consider these more as attributions than citations. All the major arguments supporting the results have been replicated in the blog post (in a more rigorous form), so it can stand on its own: the Discord links just provide historical context for those interested.
I don't like discord but... The people doing research have chosen this method of collaboration. I like their research. Let's not be choosing beggars and tell them how to conduct their research.
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.
Like it sounds like it could end up being useful somehow.
[1] https://en.wikipedia.org/wiki/Superpermutation#Lower_bounds,...
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.
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.
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