News for hackers. Stuff that matters.
Re:With fifth busy beaver, researchers approach computation'... by Natsu on Tuesday July 02, 2024 @12:25PM (#40858148)
Looking at the pictures on Wikipedia regarding those programs, it's interesting how they seem to result in fractals.
Re:With fifth busy beaver, researchers approach computation'... by jerf on Tuesday July 02, 2024 @03:14PM (#40859613)
That is because these are small. Small machines can not help but still have those sorts of patterns in them. See all the simple 1-D automata of interest, for instance: https://atlas.wolfram.com/01/01/

As you step up I am fairly confident you'll see the winners get noisier and noisier. They'll have some sort of pattern, just ones you won't be able to comprehend. For some suitable definition of "noisier" this might even be a provable claim.

Re:With fifth busy beaver, researchers approach computation'... by Natsu on Tuesday July 02, 2024 @05:13PM (#40860473)
Wouldn't it make more sense for the longest running ones to be fractal in a sense given that the self-similarity is sort of compressible? I guess we'll probably never know, because it's not clear that we'll ever find another BB winner.
Re:With fifth busy beaver, researchers approach computation'... by 317070 on Wednesday July 03, 2024 @05:15AM (#40864182)
Ha, the funny thing is, there are conjectures both ways! Some people think winners get noisier and noisier, the spaghetti code conjecture. Others actually think the winners get cleaner and cleaner, the clean code conjecture.

Personally, I am slightly leaning towards clean code being more powerful. Chaos is hard to control.

https://nickdrozd.github.io/2022/03/12/formal-theory-of-spag...

Re:With fifth busy beaver, researchers approach computation'... by jerf on Wednesday July 03, 2024 @09:12AM (#40865646)
I think human's attempts to make busy beavers may be clean, but chaos being hard to control doesn't matter to the "real" busy beavers because we pick from the entire range. I think that's one of the hardest things to wrap human brains around trying to intuit how the sequence behaves. We are selecting for the maximally pathological machines. If there is a frontier between chaos, order, and simply never halting, we are deliberately hunting the one that is just barely on that line. I don't think clean patterns can ever hope to compete with one that is exploiting chaos to just that bit that barely walks up to the line and doesn't quite, after a number of steps beyond any human ability to write down with any amount of notation we have, cross it.

But yeah, it's an opinion. :)

Re:With fifth busy beaver, researchers approach computation'... by nickdrozd on Wednesday July 03, 2024 @10:06AM (#40866080)
> We are selecting for the maximally pathological machines.

This is not quite right. We're selecting for maximally long-running (or mark-producing, etc) programs. Whether those programs turn out to be "pathological" in some sense is an open question, and a question that can only be answered (to a limited extent) by observing and analyzing actual champion machines. Apriori, there's nothing we can say about what a champion program will do or what its code will be like. The Spaghetti Code Conjecture says that these champion programs will tend to be complicated. I have argued in the past that this may not be the case. It's entirely possible that the code of a champion program will be written more or less straightforwardly, and its long-running-ness comes from executing some bizarre and exotic mathematical function.

Actually, I think the more likely outcome is that some champions will be spaghetti and some will be clean. If they were all spaghetti or all clean, then that fact could be exploited to speed up the search process by discarding all programs not matching the property. And that sounds too good to be true, so it probably isn't. Maybe BB(8) champion is clean, BB(9) is spaghetti, etc, and there are no reliable trends.

Re:With fifth busy beaver, researchers approach computation'... by jerf on Wednesday July 03, 2024 @10:44AM (#40866402)
"Actually, I think the more likely outcome is that some champions will be spaghetti and some will be clean."

Ah, now, that's thinking with pathologies.

Re:With fifth busy beaver, researchers approach computation'... by lupire on Wednesday July 03, 2024 @08:04PM (#40871232)
Clean code isn't the same as clean behavior/output, though. A Collarz calculator would have rather unclean output.
Re:With fifth busy beaver, researchers approach computation'... by LegionMammal978 on Tuesday July 02, 2024 @12:42PM (#40858278)
This mainly has to do with the BB(5) champion having "bouncing" behavior: it moves from the left side of the current pattern to the right side and back again, each time extending it slightly. Since the time it takes to grow the pattern is strictly proportional to its current size, you end up with a bunch of parabolas that appear self-similar.
Re:With fifth busy beaver, researchers approach computation'... by lmm on Tuesday July 02, 2024 @07:07PM (#40861311)
Fractals or fractal-like things seem to be the main way you get "interesting" behaviour out of very simple rules. Procedurally generated art/content tends to use them a lot (look at e.g. demoscene programs).