universal complete

posted on 2021-07-16

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.

appendix: a simple universal-complete program

here is a simple algorithm implemeting this, iterating over the countable set of turing machines.

x ← simplest turing machine
l ← empty list
loop:
    for machine in l:
        update machine by one step of computation

    append x to l
    x ← next simplest turing machine after x

posted on 2021-07-16