Cellular Automata
Cellular Automaton (복수형 : Cellular Automata) 는 계산가능성 이론 (Computability Theory) 과 수학 (Mathematics) 에서 연구되는 이산 (discrets) 모델이다. 무한하고 규칙적인 격자 (grid) 형태의 세포 (cell) 로 구성되는데, 각 cell 안에는 유한한 개수의 상태 (states) 중 하나를 가진다. 그 격자는 유한한 어떤 차원 (dimension) 에도 있을 수 있다. 시간 또한 discrete 이며, 시간 t 에서의 cell 의 상태는 시간 t-1 에서의 이웃 (neighborhood) 이라고 불리는 유한한 수의 cell 들의 상태의 함수이다. 이러한 이웃들은 어떠한 특별하게 관련되는 cell 들 중에서 선택한 것이며, 변하지 않는다 (cell 스스로가 그 이웃들 가운데 있더라도, 스스로는 이웃이라고 하지 않는다). 모든 cell 은, 이웃들의 값 (value) 에 기초해서, update를 위한 같은 규칙을 가진다. 그 규칙들이 전체 격자에 적용될 때마다 새로운 세대 (generation) 가 만들어진다. .... (Wikipedia : Cellular Automaton ★★★)
John von Neumann 은 복사기 위에 글쓰인 종이를 올려두면 글쓰인 종이가 복사되어 나오지만, 진정한 복사기란 복사기 자신을 복제하는 기계라야 한다는 생각을 하였다. 그는 자기복제 기계를 1940 연대에 프로그램하였다 (Theory of Self-Reproducing Automata, edited by Burks, Univ. of Illinois Press. 1966). 그의 생각은 세포 자동자 (Cellular Automata, CA) 로 발전하고 John Conway 가 생명 게임 (Game of Life) 을 만들어 더욱 유명해진다. 생명 게임은 CA 의 가장 훌륭한 예이다.
세포 한 격자를 만들자. 각 세포에게 유한 개수의 가능한 상태를 허용하자. 예를 들어 두 상태 세포는 켬 또는 끔, 생 또는 사, 적 또는 청의 상태에 있을 수 있다. 네 가지 상태 세포는 적·황·녹·청 상태에 있거나, 상·하·좌·우로 움직일 수 있다. 각 시간 단계, 또는 세대는 그 세포의 현 상태와 인접한 이웃들의 상태에 근거한 일단의 규칙들에 따라서 변화한다. 이러한 시스템은 자동자로서, 일단 시작하면 내장된 프로그램에 따라서 진행된다. 시스템이 세포로 구성되어 있기 때문에, 세포 자동자(Cellular Automaton), 또는 줄여서 CA라 부른다. 영어의 복수형은 Cellular Automata이다 ....... (Stephen Prata 1994)
Term :
세포자동자 (Cellular Automata) 오토마타 (Automata) 오토마타 이론 (Automata Theory) 유한상태 기계 (Finite State Machine) 튜링 기계 (Turing Machine) 인공생명 (Artificial Life) 게임 (Game)
Paper :
세포 자동자 (Cellular Automata) : Stephen Prata
셀룰라 오토마타를 이용한 수도권의 도시 성장 예측 (Cellular Automata Based Urban Growth Prediction for Seoul Metropolitan Area) : 이재원, 김용일, 정재준, 한동엽, 한국GIS학회, 2001
셀룰라 오토마타를 이용한 블록 암호 알고리즘 (A Block Cipher Algorithm based on Cellular Automata) : 이준석, 이경현, 장화식, 한국멀티미디어학회, 2002
셀룰러 오토마타 상에서 자기복제 : 위규범, 한국수학사학회, 1999
셀룰러 오토마타에 기반한 안전한 해쉬함수 (A Secure hash function based on cellular automata) : 신상욱, 이경현, 윤재우, 정보보호학회, 1998
GF(2m) 상의 셀룰라 오토마타를 이용한 VLSI 구조 (Cellular Automata based on VLSI architecture over GF(2m)) : 김현성, 이형목, 유기영, 전준철, 정보보호학회, 2002
Site :
George Maydwell's Cellular Automata Page
Conway's Game of Life : Alan Hensel : 생명게임을 위한 패턴모음 다운로드 (lifep.zip)