From heaps of matches to the limits of computability

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

13 pages, 7 figures

Scientific paper

We study so-called invariant games played with a fixed number $d$ of heaps of matches. A game is described by a finite list $\mathcal{M}$ of integer vectors of length $d$ specifying the legal moves. A move consists in changing the current game-state by adding one of the vectors in $\mathcal{M}$, provided all elements of the resulting vector are nonnegative. For instance, in a two-heap game, the vector $(1,-2)$ would mean adding one match to the first heap and removing two matches from the second heap. If $(1,-2) \in \mathcal{M}$, such a move would be permitted provided there are at least two matches in the second heap. Two players take turns, and a player unable to make a move loses. We show that these games embrace computational universality, and that therefore a number of basic questions about them are algorithmically undecidable. In particular, we prove that there is no algorithm that takes two games $\mathcal{M}$ and $\mathcal{M}'$ (with the same number of heaps) as input, and determines whether or not they are equivalent in the sense that every starting-position which is a first player win in one of the games is a first player win in the other.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

From heaps of matches to the limits of computability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with From heaps of matches to the limits of computability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and From heaps of matches to the limits of computability will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-4534

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.