작동 예시



작동 원리


맨 오른쪽 위에 있는거는 0부터 시작해서 틱당 1씩 증가하는 T신호를 내보내는 카운터이다.

수량비교 조합기가 T=0일 때 나무상자 신호를 1 출력한다.

2번째 줄의 산술연산 조합기들은 X=4, 7, 10, 13, 16...으로 가는 등차수열을 만들어서 3번때 줄로 넘긴다.

3번째 줄의 수량비교 조합기는 T=X 일 때 들어오는 신호를 전부 4번째 줄로 넘긴다.

4번째 줄은 들어오는 신호를 전부 합산해서 정리한다.



맨 밑에서 두 번째의 산술연산 조합기는 들어오는 신호 mod 2를 해서 수량비교 조합기로 보냄.

수량비교 조합기는 나무상자 신호가 0이 아닐 때 들어오는 신호를 하나는 1번째 줄로, 하나는 3번째 줄로 내 보냄.


그러면 왜 이게 시에르핀스키 삼각형이 되는가?


그걸 이해하려면 우선 파스칼의 삼각형에 대해 알아야 한다.



위의 두 칸의 합을 아래줄에 적는 방식인데,


1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

.

.

.

처음 8줄은 위와 같다.


여기서 홀수만 빨간색으로 칠해 보면


1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1


이렇게 시어르핀스키 삼각형과 같은 모양이 된다.


하지만 이러면 숫자가 너무 빠르게 커져서 40줄가량 지나면 오버플로우가 나게 된다.

그래서 산술연산 조합기로 모듈러 연산을 해 주는 것이다.




모듈러 연산의 성질에 의해 a와 b가 둘 다 짝수이거나 홀수이면 (a와 b의 차가 2k면)

a≡b (mod 2)가 된다.

그냥 더하든 더하고 2로 나누던 가장 중요한 성질인 홀짝은 보존되는 것이다.


이렇게 하면 세포 자동자 Rule 90을 만든 것이 된다.

그러므로 시어르핀스키 삼각형이 나오게 된다.


그러면 틱별로 작동 원리를 다시 분석해 보자.



1틱 후에 1열로 나무상자 신호가 1 흘러들어간다.

2틱 후에는 나무상자 신호가 0과 더해져 나무상자 신호 1개가 1열의 출력으로 흘러나간다.



3틱 후에는 모듈러 연산을 거치고,

4틱 후에는 나무상자 신호가 3열로 들어가 4열 1행의 일정신호 조합기에 저장되게 된다.


5틱 후에는 1열 1행과 2행의 조합기가 동시에 작동한다.

덧셈하고 모듈러 연산을 하는 연산이 3틱에 한 번씩 반복되면서 파스칼의 삼각형의 n번째 줄이 4열 n행의 조합기에 저장되게 된다.

그 신호는 왼쪽의 "설정해둔 신호가 1일 때에만 켜지는 조명"으로 보내져 디스플레이 된다.


청사진 : https://pastebin.com/VW6xesMz

3이나 5으로 나눈 나머지가 1일 때의 모양도 재밌으니 꼭 받아서 해 보길 바람!


참고한 글 :

위키백과 '시어르핀스키 삼각형'

위키백과 'Rule 90'

위키백과 '파스칼의 삼각형'

모듈러 연산의 성질