- Report number: 1995-056
- Authors: E. GOLES, M. MARGENSTERN
- Title: Universality of the parallel chip-firing game and related results
- Summary:
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 ones. Also, we prove, for infinite graphs, that the reachability problem is undecidable.