This is a bit of a theoretical question. In a programming assignment, we have been told to implement the Game of Life by John Conway. As an additional task, we've been asked to modify the program so that it can detect repetitions of patterns for periods up to four generations. For example, the program should behave like this, given this specific "seed" to the game:
--------
| |
| OOO |
| |
| |
| |
--------
--------
| 0 |
| 1 |
| 0 |
| |
| |
--------
--------
| |
| O2O |
| |
| |
| |
--------
Repetition detected (2): exiting
Indicating that the program repeated itself and that the period was 2 generations long.
My question is this. Is it possible to really know when a program is simply repeating the same pattern over and over again? I've heard of the "Halting problem". Is this related to that?
Now, if it indeed is possible, how can the program that the teachers seem to be running seem to be able to detect it after just one repetition? Second, is it really reasonable to expect students of a basic programming course to write a program that detects repeating patterns in the Game of Life? I have a feeling that what they mean to say is "modify your program to exit when the same state is reached twice within a 4 generation window" which seems to me like an entirely different matter than to detect if the pattern will truly repeat itself forever.
EDIT:
Here's what the specification says: You are to modify the program to detect a repetition of a previous pattern. Your program should be able to detect repeating patterns with periods of up to four generations. When such a repetitions is discovered, the program should exit with a different message:
Period detected (4): exiting
replacing the "Finished" message, with the length of the period indicated by the number in brackets. The repeated pattern should be printed before exiting.