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

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: