Universality of the chip-firing game
โ
Eric Goles; Maurice Margenstern
๐
Article
๐
1997
๐
Elsevier Science
๐
English
โ 744 KB
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