차이점

이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.

차이 보기로 연결

초등셀룰러오토마타 [2011-12-30 04:32] (현재)
lifthrasiir 새로 만듦
줄 1: 줄 1:
 +====== 초등 셀룰러 오토마타 ======
  
 +Elementary cellular automaton. 1차원으로 배열된, 오로지 두 개의 상태(0과 1)만 가질 수 있는 공간으로 만들 수 있는 가장 간단한 [[셀룰러오토마타]]들. 매 세대마다 각 공간은 주변에 위치한 두 공간 및 자기 자신의 값에 따라 지정된 값으로 변경되는데, 이러한 규칙이 2<sup>3</sup> = 8개 필요하기 때문에 가능한 초등 셀룰러 오토마타는 총 2<sup>8</sup> = [[256]]개이다.
 +
 +초등 셀룰러 오토마타는 흔히 하나의 숫자로 표현하는데, 이 숫자는 [[이진법]]으로 나타냈을 때 8개의 규칙에 대응하는 결과값이 각 비트에 나타나도록 구성되어 있다. 예를 들어, Rule 110의 경우 다음과 같은 규칙으로부터 유래한다.
 +
 +|  **이전 상태** | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
 +|    **새 상태** |  0  |  1  |  1  |  0  |  1  |  1  |  1  |  0  |
 +
 +새 상태에 해당하는 비트를 모두 모으면 01101110<sub>2</sub> = 110이 된다. 따라서 가능한 오토마타는 Rule 0부터 Rule 255까지인데, 규칙들에서 0과 1을 모두 뒤집을 경우와 규칙들을 세로로 반전할 경우 실질적으로는 같은 오토마타가 나오기 때문에 이를 제외한 88가지만을 고려하면 된다.
 +
 +초등 셀룰러 오토마타는 매우 단순화된 계산 모델임에도 불구하고, 적절한 규칙과 적절한 초기 상태만 있으면 [[튜링완전]]한 계산을 할 수 있다는 것이 알려져 있다. (앞에서 말한 Rule 110이 그러한 규칙으로 알려져 있다.) 이런 특성 때문에 이러한 초등 셀룰러 오토마타를 "범용적"(universal)이라고 하기도 한다.
 +
 +===== 목록 =====
 +
 +다음은 중요한 초등 셀룰러 오토마타의 목록이다.
 +
 +  * [[Rule 30]] --- 매우 랜덤한 결과를 내 놓으며, [[난수생성]]에 흔히 쓰인다.
 +  * [[Rule 110]] --- 적절한 초기 상태를 주면 튜링 완전한 것으로 알려져 있다.
 +
 +{{tag>수학 목록}}

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-12-30 04:32 | 작성자 lifthrasiir