Search

Abstract: This 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. [ABSTRACT FROM AUTHOR]

Abstract: This paper is the first part of a series of two papers dealing with bulking: a quasi-order on cellular automata comparing space–time diagrams up to some rescaling. Bulking is a generalization of grouping taking into account universality phenomena, giving rise to a maximal equivalence class. In the present paper, we discuss the proper components of grouping and study the most general extensions. We identify the most general space–time transforms and give an axiomatization of bulking quasi-order. Finally, we study some properties of intrinsically universal cellular automata obtained by comparing grouping to bulking. [Copyright &y& Elsevier]

Abstract: This paper is the second part of a series of two papers dealing with bulking: a way to define quasi-order on cellular automata by comparing space-time diagrams up to rescaling. In the present paper, we introduce three notions of simulation between cellular automata and study the quasi-order structures induced by these simulation relations on the whole set of cellular automata. Various aspects of these quasi-orders are considered (induced equivalence relations, maximum elements, induced orders, etc.) providing several formal tools allowing to classify cellular automata. [Copyright &y& Elsevier]