If problem A is not algorithmically solvable, and A is reducible to B, then problem B is also not algorithmically solvable (because, if B would be solvable, then so would A, viz. via the reduction).
In particular, Simple Language consisting of three statements (incr(X), decr(X), while (X) { statement list }) working on an unlimited set of arbitrary-sized nonnegative integer variables.
Simple Language is universal.
ArrayPlot[CellularAutomaton[32, {{1, 0, 1, 1, 0, 0, 1, 1}, 0}, 50]]
ArrayPlot[CellularAutomaton[108, {{1, 0, 1, 1, 0, 0, 1, 1}, 0}, 50]]
ArrayPlot[CellularAutomaton[30, {{1}, 0}, 100], ImageSize -> Large]
ArrayPlot[CellularAutomaton[110, {{1, 0, 1, 1, 0, 0, 1, 1}, 0}, 200],
ImageSize -> Large]
"... one of the implications of the Principle of Computational Equivalence is that almost any rule whose behavior is not obviously simple should ultimately be capable of achieving the same level of computational sophistication and should thus in effect be universal.Also see Ch.13, Sec.3: "The Phenomenon of Universality""So far from universality being some rare and special property that exists only in systems that have carefully been built to exhibit it, the Principle of Computational Equivalence implies that instead this property should be extremely common. And among other things this means that universality can be expected to occur not only in many kinds of abstract systems but also in all sorts of systems in nature." (Ch.12, Sec.2, p.718)
I,
you can add on a U at the end.
Mx.
Then you may add Mxx to your collection.
III occurs in one of the strings
in your collection,
you may make a new string with U in place of III.
UU occurs inside one of your strings,
you can drop it.
MU when you start with MI?
(K x y) = x (S x y z) = (x z (y z))
((S K K) x)
= { Currying }
(S K K x)
= { definition of S }
(K x (K x))
= { definition of K }
x
Note that (S K) complements K,
in that ((S K) x y) = y.
This is equivalent to (K I),
for which also ((K I) x y) = y.
Combinator (K I) can serve as representation of the number 0,
and the combinator (S (S (K S) K) as successor function
(that adds 1 to its argument).
primes.mc
in the folder "Other-Rules/WireWorld/"
(you need to zoom in, when running it)