Loading [a11y]/accessibility-menu.js
A Weakly Universal Cellular Automaton on the Heptagrid with Three States | IEEE Conference Publication | IEEE Xplore

A Weakly Universal Cellular Automaton on the Heptagrid with Three States

Publisher: IEEE

Abstract:

In this paper, we improve previous results giving the construction of a weakly universal cellular automaton on the heptagrid. Here we obtain such a cellular automaton wit...View more

Abstract:

In this paper, we improve previous results giving the construction of a weakly universal cellular automaton on the heptagrid. Here we obtain such a cellular automaton with three states only. Our cellular automaton makes use of the railway circuit model to which we give here several important changes.
Date of Conference: 10-12 December 2014
Date Added to IEEE Xplore: 02 March 2015
Electronic ISBN:978-1-4799-4152-0

ISSN Information:

Publisher: IEEE
Conference Location: Shizuoka, Japan

I. Introduction

In this paper, we construct a weakly universal cellular automaton on the heptagrid, see Theorem 3 at the end of the paper. Two papers, [9], [5] already constructed such a cellular automaton, the first one with 6 states, the second one with 4 states. In this paper, the cellular automaton we construct has three states only. It uses the same principle of simulating a register machine through a railway circuit, but the implementation takes advantage of new ingredients introduced by the author in his quest to lower down the number of states, see [7]. It also introduces new constructions which significantly improve the scenario used in the previous papers. The reader is referred to [3], [4], [7] for an introduction to hyperbolic geometry turned to the implementation of cellular automata in this context. A short introduction can also be found in [2]. However, it is not required to be an expert in hyperbolic geometry in order to read this paper.

References

References is not available for this document.