Four states are enough!

AbstractThis paper presents a 1D intrinsically universal cellular automaton with four states for the first neighbor’s neighborhood, improving on the previous lower bound and getting nearer to the Turing universality bound. Intrinsic universality is discussed. Construction and proof rely on a combination of bulking techniques with programming using particles and collisions