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)