The surjectivity problem for 2D cellular automata

✍ Scribed by Bruno Durand

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 402 KB
• Volume: 49
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(05)80077-7

✦ Synopsis

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.