Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

BB(3, 4) > Ack(14)

sligocki.com

Post reply on HN
Print view View original

61–70 of 114 posts

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

#61

Post by nickdrozd »

sans-seraph wrote: post #47
nickdrozd wrote: post #30

Earlier quoted context omitted.

The "states" (A, B, C) correspond to goto targets. The "colors" (0, 1, 2, 3) are runtime data. At each state, the current color is read, and an instruction is executed (print some color, move left or right, goto some state) based on which color is there. Transliterated into C it looks like this: #include "machine.h" int main(void) { A: switch (SCAN) { case 0: WRITE(1); RIGHT; goto B; case 1: WRITE(3); LEFT; goto B; c…

> 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(…

Wow! I don't know if I would call that "structured", but it's pretty clever. And horrifying. Well-done!

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

#62

Post by im3w1l »

mcherm wrote: post #21
j2kun wrote: post #14

Earlier quoted context omitted.

Finding bigger busy beaver numbers is not exactly foundational. More like recreational. If it were foundational it would be peer reviewed in a journal article, not posted on a blog.

> 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 i…

To me, figuring out the halting behavior of small turing machines is similar in spirit going over all short logical propositions and trying to determine if they are true or not.

Like it sounds like it could end up being useful somehow.

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

#63

Post by LegionMammal978 »

nilstycho wrote: post #57
im3w1l wrote: post #50

Earlier quoted context omitted.

You also need to subtract some bits from symmetries right? 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.

Also, is there any sense in restricting the universe of machines to those that include one and only one halting symbol? Machines with more or fewer than one halting symbol are possible, but they're less interesting, right?

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 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/

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

#64

Post by lisper »

vlovich123 wrote: post #56
lisper wrote: post #54

Earlier quoted context omitted.

> there would still be pressure to show that you somehow convinced the leading experts in the field And how do you tell who are the leading experts in the field?

It doesn’t matter. There’s plenty of ways. Tenure, those who get cited the most as contributing to other works, whoever manages to shmooze their way onto the grant review board, whoever has been doing “good” work in a space etc etc. If you think that peer review is the only way status is established, I’m afraid you’re failing to grok how humans work - we’re very status oriented and will come up with any mechanism to…

> Tenure

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:

https://www.youtube.com/watch?v=ODgYbmmgOss

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

#65

Post by lisper »

AlotOfReading wrote: post #59
lisper wrote: post #53

Earlier quoted context omitted.

What difference does it make if the original lasts a year or a century? The original is irrelevant except for historical purposes. What matters from a scientific point of view is that the results withstand scrutiny, and that they are reliably replicated and accessible.

We discover new approaches to replication all the time. Have you never come across foundational papers and arguments that everyone loved at the time, but made big methodological mistakes that led to the wrong conclusion? Or worse, found a source everyone references based on yet other secondary sources, only to look at the original context to discover that everyone's been misquoting it for decades? That happens regula…

Sure, but I don't see what that has to do with the choice of publication venue. All of these things happen in traditional peer-review publications too.

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

#66

Post by LegionMammal978 »

AlotOfReading wrote: post #59
lisper wrote: post #53

Earlier quoted context omitted.

What difference does it make if the original lasts a year or a century? The original is irrelevant except for historical purposes. What matters from a scientific point of view is that the results withstand scrutiny, and that they are reliably replicated and accessible.

We discover new approaches to replication all the time. Have you never come across foundational papers and arguments that everyone loved at the time, but made big methodological mistakes that led to the wrong conclusion? Or worse, found a source everyone references based on yet other secondary sources, only to look at the original context to discover that everyone's been misquoting it for decades? That happens regula…

In this case, Ligocki's presentation of the proofs in the blog post is really more rigorous than anything that went on in the Discord server. There's not some golden Truth in there that's being imperfectly mediated; it's just about the attribution. You might have more of a point for results originating from programmatic searches, but that's why the programs are all published outside of Discord, so their output can be replicated.

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

#67

Post by tsterin »

TeMPOraL wrote: post #33
pollyturples wrote: post #26

Earlier quoted context omitted.

MySpace: 16 years (2003–2019) Friendster: 12 years (2002–2013) Google+: 8 years (2011–2019) Vine: 4 years (2013–2017) Orkut: 10 years (2004–2014) Path: 8 years (2010–2018) Yik Yak: 4 years (2013–2017) Meerkat: 2 years (2015–2017) Windows Live Messenger (MSN Messenger): 15 years (1999–2014) AIM (AOL Instant Messenger): 20 years (1997–2017) ICQ: Ongoing (since 1996) but significantly declined after the early 2000s Yaho…

Even with services that lived over a decade, it's not clear whether messages were accessible for all that time. E.g. Google Talk/Meet/Whatever seemingly lost all messages before ~2013. Links to Facebook posts tend to die quickly, as both users and Meta itself seem to constantly play with privacy features. Etc.

I really like your point (I'm one of bbchallenge maintainers). I think that Discord is close to optimal for us in the short term, but bad for the reasons you and other have mentioned mid/long term.

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

#68

Post by vlovich123 »

lisper wrote: post #64
vlovich123 wrote: post #56

Earlier quoted context omitted.

It doesn’t matter. There’s plenty of ways. Tenure, those who get cited the most as contributing to other works, whoever manages to shmooze their way onto the grant review board, whoever has been doing “good” work in a space etc etc. If you think that peer review is the only way status is established, I’m afraid you’re failing to grok how humans work - we’re very status oriented and will come up with any mechanism to…

> Tenure 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…

> And how do you think that gets decided?

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.

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

#69

Post by nilstycho »

LegionMammal978 wrote: post #63
nilstycho wrote: post #57

Earlier quoted context omitted.

Also, is there any sense in restricting the universe of machines to those that include one and only one halting symbol? Machines with more or fewer than one halting symbol are possible, but they're less interesting, right?

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 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.

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

#70

Post by tromp »

nilstycho wrote: post #69
LegionMammal978 wrote: post #63

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…

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

Post reply on HN