The surjectivity problem for 2D cellular automata

摘要

The surjectivity problem for 2D cellular automata was proved undecidable in 1989 by Jarkko Kari. The proof consists in a reduction of a problem concerning finite tilings into the previous one. This reduction uses a special and very sophisticated tile set. In this article, we present a much more simple tile set which can play the same role.