얼마 전 스팀과 스위치로 나온 퍼즐 게임 Baba is you. 적어도 내 타임라인에서 선풍적인 인기를 끌고 있는 퍼즐 게임으로, 룰을 블록화하고 그 룰과 상호작용함으로써 문제를 해결하는 신선함이 매우 돋보이는 게임이다. 그와 동시에 난이도가 꽤 어렵게 설정되어있어 퍼즐러로서의 도전심을 자극하고 있기도 함.
이 Baba is you로 elementary cellular automaton rule 110을 구현한 영상을 보게 되었다. Elementary cellular automaton이란게 뭐냐면 콘웨이의 생명게임과 비슷한건데 0과 1로 이루어진 패턴이 주어져있으면 연속한 세 개의 항에 따라 다음 패턴이 어떻게 정해지는지를 결정하는 룰을 뜻한다. Rule 110은 다음과 같은 규칙.
즉 
Source: http://mathworld.wolfram.com/Rule110.html
이 rule 110이 튜링완전(Turing-complete)이기 때문에[1] 이걸 구현한 바바이즈유 역시 튜링완전하게 된다는 것을 증명한 셈이 된다. 해당 영상을 올린 Matthew Rodriguez는 증명 스케치를 통해 어떤 방식으로 작동하는지를 설명했다. 먼저 다음 세 룰은 글로벌 룰로 고정.
CLOUD IS TELE
WALL IS STOP
TEXT IS MOVE
IS를 아래로 계속 움직이면서 다음과 같이 주어진 코드를 순차적으로 실행시키고 CLOUD로 반복문을 만드는 구조.
1. ROCK IS LOVE AND STAR AND MOON AND PILLAR
2. LOVE AND STAR AND MOON IS DOWN AND MOVE
3. MOON IS LEFT AND MOVE
4. LOVE IS RIGHT AND MOVE
5. (nothing)
6. LONELY STAR IS ROCK (010 -> 1)
7. LONELY MOON IS ROCK (001 -> 1)
8. STAR ON MOON IS GHOST
9. MOON ON GHOST IS EMPTY
10. GHOST ON LOVE IS EMPTY (111 -> 0)
11. LONELY LOVE IS EMPTY (100 -> 0)
12. GHOST AND LOVE IS ROCK (011 -> 1, 101 -> 1, 110 -> 1)
13. STAR AND MOON IS EMPTY
대략적으로 설명하자면, ROCK이 1들의 포지션이고 이를 기록하는건 PILLAR이며 나머지 ROCK, LOVE, STAR, MOON(그리고 GHOST)은 중간 변수라 볼 수 있다. 1에서 각각의 ROCK이 LOVE(이하 L), STAR(이하 S), MOON(이하 M), PILLAR를 생성하고, 2, 3, 4를 통해 M은 좌하단, S는 하단, L은 우하단으로 움직인다. 5는 4에서 지정한 L의 움직임을 실행할 수 있게 비워둠. 그러면 MSL로 가득한 줄에서, 한 칸에 L, S, M이 있다는 것은 각각 그 좌상단, 상단, 우상단에 1이 있다는 것을 의미한다. 이 정보들을 이용해 하나씩 처리해나가는 식. 예컨대, LONELY S는 (LONELY는 다른 오브젝트와 겹치지 않음을 뜻함) 그 칸에 S는 있지만 L, M은 없으므로 그 바로 위가 010을 뜻해 바로 1로 변환할 수 있고, 비슷하게 LONELY M은 바로 위가 001임을 뜻해 바로 1로 변환할 수 있다.
References
[1] M. Cook, “Universality in Elementary Cellular Automata” Complex Systems, 15: 1-40. https://www.complex-systems.com/abstracts/v15_i01_a01/
udaqueness 