avatar

universal complete

under a turing-complete model of computation, there are some initial-states or initial-states-and-rulesets which eventually contain an algorithm that iterates over all possible algorithms and runs them.

in single-threaded models, it can do this by having an increasingly long list of algorithms that it runs by one step each; it's not an issue if each algorithm runs increasingly slowly, as long as it keep running.

i choose to call such initial-states[-and-rulesets] Universal Complete.

they contain all turing computation based universes (and thus each other, if indirectly); so, for example, if Rule 30 with one alive cell is Universal Complete, then it contains all computable universes (including ours).

this could be interesting because proving that property about some frameworks means that programming a particular algorithm starting from that initial-state[-and-ruleset] is just a matter of locating it.

it could also be interesting because it might turn out that many things that look sufficiently chaotic (such as Rule 30 with one alive cell) are effectively universal complete, and so Wolfram's quest for the rule that describes our universe in his hypergraph-rewrite system might be reductible to "whichever simplest initial-state-and-ruleset starts all algorithms"; though his idea of running every rule at every step might kind of functionally do that.


RSS feed available here; new posts are also linked on my twitter.
CC_ -1 License Unless otherwise specified on individual pages, all posts on this website are licensed under the CC_-1 license.
This site lives at https://carado.moe and /ipns/k51qzi5uqu5di8qtoflxvwoza3hm88f5osoogsv4ulmhurge2etp9d37gb6qe9.