從生命遊戲到點燈遊戲的數學性質研究

Martin Gardner 在1970年提出了由劍橋的約翰康威教授所設計的「生命遊戲(Conway’s Game of Life)」，引發了資訊科學上一連串的研究，後來Sutner將其轉成了σ-automaton的數學模型，也開啟了數學研究的一個大門。另一方面Tiger electronic於1995年生產了light out遊戲，玩家利用light chasing解開它，1998年Anderson與Feil利用線性方程來破解它。2004年Chuah與Hu發現了light out與李代數結構的等價有關。因為網路的發達，這三者的關係開始被觀注，引發了代數、圖論與資訊科學上不少的火花。本研究再針對Lights out的性質做討論，有四個結果，第一個計算整個轉換矩陣的時間由O(n)減少到O(log n)；第二個是求出此矩陣的一般式，也就是單算矩陣中的某個元素的話， 也能加快，第三個是當n小的時候，常數倍數的改進，第四個是計算其週期性質，與可解性，亦即當n,m為多少時，必定有解。