Reproduce “Nominal Cellular Automata” on OpenResearch

About this paper

Tommaso Bolognesi, Vincenzo Ciancia

This paper introduces Nominal Cellular Automata (NCAs), a novel computational model that extends classical cellular automata by using an infinite alphabet of "pure names" and transition rules based on local equality patterns. This work demonstrates that NCAs are Turing-universal and exhibit unique emergent behaviors, including "nominal particles" that continuously generate new names, offering a refined perspective on the computational universe conjecture.

Key insights

• The use of an infinite set of pure names and equality patterns offers a more abstract and potentially fundamental basis for modeling emergent complexity than classical CAs with their fixed, universally understood cell states.
• Despite a smaller rule space for Elementary Nominal Cellular Automata (216 rules vs. 256 for ECAs), NCAs exhibit a rich diversity of complex emergent behaviors, including patterns of unbounded name creation.
• NCAs are Turing-universal, as demonstrated by their capability to simulate any classical ECA, specifically the Turing-complete ECA 110, through a clever encoding scheme.
• The paper introduces "nominal particles," a new category of emergent phenomena where periodicity applies to equality patterns, while the particles continuously generate new, distinct names along their trajectories.

Summary by alphaXiv.