Introduction to
Logic Programming

Example - Game of Life

The Game of Life is a cellular automaton devised by the British mathematician John Conway in 1970. The universe of the game is a two-dimensional orthogonal grid of square cells, each of which is in one of two possible states - alive (shown in black) or dead (shown in white). Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. On each step, the next state is determined by applying the following rules.

  • Any live cell with fewer than two live neighbors dies, as if caused by underpopulation.
  • Any live cell with two or three live neighbors lives on to the next generation.
  • Any live cell with more than three live neighbors dies, as if by overpopulation.
  • Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Press Play to allow the system to operate on its own. Press Pause to pause operation. Press Step to advance one step.


Changing the initial state of the system can change the way the system evolves. In some cases, the system reaches quiescence, i.e. nothing changes from step to step. In some cases, the system oscillates. With an infinite universe, it is possible for a system to run forever without repeating any state.

With the game paused, create a new state by clicking cells to toggle their statuses between live and dead. Once you are done, click Play to see what happens with your new state. Reload the page to return to the initial state.

Now, let's see how we can describe this system using operation definitions.

tick :: index(M) & index(N) & ~value(cell(M,N),on) & evaluate(countofall(Y,support(cell(M,N),Y)),3) ==> value(cell(M,N),on) tick :: value(X,on) & evaluate(countofall(Y,support(X,Y)),N) & bad(N) ==> ~value(X,on)

Of course, we must also define the concepts used in these transition rules.

support(X,cell(M,N)) :- kingmove(X,cell(M,N)) & value(cell(M,N),on) bad(N) :- max(N,1,1) bad(N) :- min(N,4,4) kingmove(cell(X1,Y),cell(X2,Y)) :- succ(X1,X2) & index(Y) kingmove(cell(X1,Y),cell(X2,Y)) :- succ(X2,X1) & index(Y) kingmove(cell(X,Y1),cell(X,Y2)) :- succ(Y1,Y2) & index(X) kingmove(cell(X,Y1),cell(X,Y2)) :- succ(Y2,Y1) & index(X) kingmove(cell(X1,Y1),cell(X2,Y2)) :- succ(X1,X2) & succ(Y1,Y2) kingmove(cell(X1,Y1),cell(X2,Y2)) :- succ(X2,X1) & succ(Y1,Y2) kingmove(cell(X1,Y1),cell(X2,Y2)) :- succ(X1,X2) & succ(Y2,Y1) kingmove(cell(X1,Y1),cell(X2,Y2)) :- succ(X2,X1) & succ(Y2,Y1)

Finally, we need some base data.

index(1) index(2) index(3) index(4) index(5) index(6) index(7) index(8) index(9) succ(1,2) succ(2,3) succ(3,4) succ(4,5) succ(5,6) succ(6,7) succ(7,8) succ(8,9)