■

ライフゲイムで、状態を更新していくプログラムは情熱さえあれば中学生でも書けるけど（でも今の時代、グラフィックが難しいんだよな。cls とか point 命令とか懐かしい）、逆に１ステップ前の状態を推定する、ってのは難しい。ある状態が初期状態としてしかありえない「エデンの園配置」であることを示す場合なんかも、そういうことをする必要がある。多分、一般化したマインスイーパーの一つとして扱えるんじゃないかと思うけど、シラミ潰しに調べるしかなくてＮＰ完全のような気がする。

そういえば、『ライフゲイムの宇宙』ISBN:4535783837 【アマゾン】の旧版ではライフゲイムが予測不能である証明として、チューリングマシンの配置を作ってフェルマーの最終予想を解かせるような配置を作れるので、ライフゲイムが予測可能ならフェルマーの最終予想も解ける、という話が書いてあった。でもフェルマーの最終予想は解決されちゃったなぁ。