Universality of the chip-firing game

✍ Scribed by Eric Goles; Maurice Margenstern

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 744 KB
• Volume: 172
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(95)00242-1

✦ Synopsis

We prove that the parallel updating of the chip-firing game on undirected graphs is universal. To achieve that, we simulate any given two-register machine by chip configurations. As corollaries, we prove that for finite graphs there exists exponential transient time to reach periodic configurations as well as exponential cycles. Also, we prove, for infinite graphs, that the reachability problem is undecidable.