Hacker News new | past | comments | ask | show | jobs | submit login

"I wonder if this is something generally true for all BBs"

No. A BB is going to use "all" its states. When you're up into the hundreds, it's not going to be anything recognizably Collatz-like, because Collatz is so simple.

People love what I think of as "squinting until everything blurs and everything is the same" and will probably try to salvage this conjecture for whatever reason people tend to do this, but unless you're going to claim that all Turing Machines are "just" computing some sort of "Collatz-like computation", degenerately, by blurring your definition of "Collatz-like" until the hand-written Turing Machine from school to reverse a string is "Collatz-like" and the hand-written TM to simulate a multitape machine is "Collatz-like", I don't think there's any reason to believe BB will continue to be Collatz-like indefinitely.

To put it another way, we've got a pretty good sense that even some hand-written functions can exceed these Collatz machines pretty handily... we just need enough states to represent them. The odds of a Collatz machine being the optimal machine once you get enough states to represent other ultra-super-exponential functions (e.g., Tree) is basically zero. It's just an artifact of us not being able to test such small Busy Beavers.

The most likely thing that BB(100) "does" is going to be something utterly humanly incomprehensible, not some sort of cute Collatz-like computation that can be characterized in any manner that would make sense to a human.




I wouldn't put it so strongly: often a long-running TM can be analyzed in several layers with their own independent rules, each of which simulates the next. E.g., at the lowest level, most nontrivial TMs look like a list of unary or binary counters interacting with each other. I wouldn't be surprised if at least some of the lower layers of the longest-running machines included one or more Collatz-like components. After all, it is a cheap way to pad out the tape when setting up the parameters of some greater process! It's just not going to be the entirety of what it does, since no simple Collatz-like process will practically get you past an exponential number of steps.


Thank you for providing an example of exactly what I mean by "yeah, but if we just squint harder..."

It is generally considered very unlikely that BBs will just compose together lower level BBs in any comprehensible manner because that very human-comprehensible composibility is itself going to be a waste of states that could be used to do something simply incomprehensible. It is very, very unlikely that BB(100) will consist even of parts a human can understand. It will be a monolithic whole of impenetrable incomprehensibility.

When you say TMs can often be analyzed in terms of smaller ones, you are talking about human-built TMs. We have to build that way. We can't work with the raw chaos. You can see this in our design in every field; we have to work in modules. BBs do not and will not.


I'm not talking about human-built TMs: I specifically have in mind some of the 3x3 holdouts I have looked into. Every last one of those can be seen as simulating a higher-level process, up to a point where it potentially breaks down (either halting or transitioning to another process); we just can't tell whether that breakdown ever occurs in reality.

Just because a machine is incomprehensible as a whole, doesn't mean that every singular aspect is incomprehensible! The thing with TMs is, there is a finite (or very slow-growing) number of meaningful things a machine can do with raw symbols on the tape. "Raw chaos" printed directly on the tape would just cause it to either halt nearly immediately, or enter some trivial non-halting configuration. Compare this with Conway's Game of Life, where 99.99999999+% of random soups create only trivial output, despite the CA itself being universal.

Note that I'm not at all saying that large machines aren't doing wonderful and terrible things, immediately past the lowest level. But the formalism itself restricts them from being too wild right away, at least not without sacrificing dozens of valuable states to constantly fix things up. For a machine to be nontrivial, it must syntactically maintain a very fine line between halting and non-halting, so that we can't just easily decide it one way or another.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: