Æ©¸µ ±â°è

 

Çü½Ä ¾ð¾î¿Í ¿ÀÅ丶Ÿ : Peter Linz Àú¼­, ÀåÁ÷Çö. ±èÀÀ¸ð. ¾ö¿µÀÍ. Çѱ¤·Ï °ø¿ª, »çÀÌÅع̵ð¾î, 2001 (¿ø¼­ : An Introduction to Formal Languages and Automata. 3rd ed, Jones and Bartlett. 2001), Page 233~260

 

1. Ç¥ÁØ Æ©¸µ ±â°è

     (1) Æ©¸µ ±â°èÀÇ Á¤ÀÇ

     (2) ¾ð¾î ½ÂÀαâ·Î¼­ÀÇ Æ©¸µ ±â°è

     (3) º¯È¯±â·Î¼­ÀÇ Æ©¸µ ±â°è

     ¿¬½À¹®Á¦

2. º¹ÀâÇÑ Å½ºÅ©¸¦ À§ÇÑ Æ©¸µ ±â°è °áÇÕ

     ¿¬½À¹®Á¦

3. Æ©¸µ ¸íÁ¦

     ¿¬½À¹®Á¦

 

¾Õ¼­ÀÇ ³íÀÇ¿¡¼­, ¿ì¸®´Â ¸î¸î ±âº»ÀûÀÎ °³³äµé, ƯÈ÷ Á¤±Ô ¾ð¾î¿Í ¹®¸Æ-ÀÚÀ¯ ¾ð¾îÀÇ °³³ä°ú À¯ÇÑ ¿ÀÅ丶Ÿ¿Í Ǫ½Ã´Ù¿î ½ÂÀαâ¿ÍÀÇ ¿¬°üµéÀ» ´Ù·ç¾ú´Ù. ¿ì¸®´Â Á¤±Ô ¾ð¾î°¡ ¹®¸Æ-ÀÚÀ¯ ¾ð¾îÀÇ ÁøºÎºÐ ÁýÇÕÀÌ°í, µû¶ó¼­ Ǫ½Ã´Ù¿î ¿ÀÅ丶Ÿ°¡ À¯ÇÑ ¿ÀÅ丶Ÿº¸´Ù ´õ °­·ÂÇÏ´Ù´Â °ÍÀ» ¹àÇô³Â´Ù. ¶ÇÇÑ ¿ì¸®´Â ¹®¸Æ-ÀÚÀ¯ ¾ð¾î°¡, ÇÁ·Î±×·¡¹Ö ¾ð¾îÀÇ ¿¬±¸¿¡ ±âÃÊ°¡ µÇÁö¸¸, ¹üÀ§¿¡ À־ Á¦ÇѵǴ °ÍÀ» È®ÀÎÇÏ¿´´Ù. ÀÌ·¯ÇÑ »ç½ÇÀº {anbncn} °ú {ww} ¿Í °°Àº ¸î¸î °£´ÜÇÑ ¾ð¾î°¡ ¹®¸Æ-ÀÚÀ¯ ¾ð¾î°¡ ¾Æ´ÔÀ» ¹àÈûÀ¸·Î½á ¾ÕÀå¿¡¼­ ¸í¹éÇØÁ³´Ù. ÀÌ·± »ç½ÇÀº ¿ì¸®·Î ÇÏ¿©±Ý ¹®¸Æ-ÀÚÀ¯ ¾ð¾î¸¦ ´É°¡ÇÏ´Â °ÍÀ» ã¾Æº¸°Ô ÇÏ°í ÀÌ ¿¹µéÀ» Æ÷ÇÔÇÏ´Â »õ·Î¿î ¾ð¾î±ºÀ» ¾î¶»°Ô Á¤ÀÇÇÒ ¼ö ÀÖÀ»Áö¸¦ »ìÆ캸°Ô ÇÑ´Ù. ±×·¸°Ô Çϱâ À§ÇÏ¿©, ¿ì¸®´Â ¿ÀÅ丶ŸÀÇ ÀϹÝÀûÀÎ ±×¸²À» ´Ù½Ã º¸±â·Î ÇÏÀÚ. À¯ÇÑ ¿ÀÅ丶Ÿ¸¦ Ǫ½Ã´Ù¿î ¿ÀÅ丶Ÿ¿Í ºñ±³ÇØ º¸¸é, Àӽà ÀúÀåÀå¼ÒÀÇ Æ¯¼ºÀÌ µÑ »çÀÌÀÇ Â÷À̸¦ ¸¸µé¾î ³¿À» º¸¾Ò´Ù. ¸¸¾à ÀúÀåÀå¼Ò°¡ ¾ø´Ù¸é ¿ì¸®´Â À¯ÇÑ ¿ÀÅ丶Ÿ¸¦ °®°Ô µÇ°í, ¸¸¾à ÀúÀåÀå¼Ò°¡ ½ºÅÃÀÌ¸é ¿ì¸®´Â ´õ °­·ÂÇÑ Çª½Ã´Ù¿î ¿ÀÅ丶Ÿ¸¦ °®°Ô µÈ´Ù. ÀÌ·¯ÇÑ °üÂûµéÀ» ÇÕÃļ­, ¸¸¾à ¿ÀÅ丶Ÿ¿¡ Á»´õ À¯¿¬ÇÑ ÀúÀåÀå¼Ò¸¦ ºÎ¿©ÇÑ´Ù¸é, ¿ì¸®´Â ´õ¿í °­·ÂÇÑ ¾ð¾î±ºÀ» ¹ß°ßÇÏ´Â °ÍÀ» ±â´ëÇÒ ¼ö ÀÖÀ» °ÍÀÌ´Ù. ¿¹¸¦ µé¾î, ±×¸² 1ÀÇ ÀϹÝÀûÀÎ ±¸Á¶¿¡¼­, ¸¸¾à ¿ì¸®°¡ µÎ °³ÀÇ ½ºÅÃ, ¼¼ °³ÀÇ ½ºÅÃ, Å¥, ¶Ç´Â ´Ù¸¥ ÀúÀåÀåÄ¡¸¦ »ç¿ëÇÑ´Ù¸é ¾î¶»°Ô µÉ±î? °¢°¢ÀÇ ÀúÀåÀåÄ¡´Â »õ·Î¿î Á¾·ùÀÇ ¿ÀÅ丶Ÿ¸¦ Á¤ÀÇÇÏ°í ±×°ÍÀ» ÅëÇÏ¿© »õ·Î¿î ¾ð¾î±ºÀ» Á¤ÀÇÇÒ °ÍÀΰ¡? ÀÌ·¯ÇÑ Á¢±ÙµéÀº ¸¹Àº Áú¹®µéÀ» Á¦±âÇÏÁö¸¸, ±×µé ´ëºÎºÐÀº Èï¹Ì°¡ ¾ø´Â °ÍÀ¸·Î ÆǸíµÇ¾ú´Ù. ¿ÀÅ丶ŸÀÇ °³³äÀÌ ¾îµð±îÁö È®´ëµÉ ¼ö ÀÖÀ»±î ÇÏ´Â ´õ ¾ß½ÉÂù Áú¹®°ú »ý°¢À» ÇÏ´Â °ÍÀÌ ´õ ±³À°ÀûÀÌ´Ù. ¿ì¸®´Â °¡Àå °­·ÂÇÑ ¿ÀÅ丶Ÿ¿Í °è»êÀÇ ÇÑ°è¿¡ ´ëÇÏ¿© ¾î¶»°Ô ¸»ÇÒ ¼ö ÀÖÀ»±î? ÀÌ Áú¹®Àº Æ©¸µ ±â°è (Turing machine) ÀÇ ±âÃÊÀûÀÎ °³³äÀ» À̲ø¾î ³Â°í, À̾, ±â°èÀûÀÎ ¶Ç´Â ¾Ë°í¸®ÁòÀûÀÎ °è»êÀÇ °³³äÀÇ Á¤È®ÇÑ Á¤ÀǸ¦ À̲ø¾î ³Â´Ù.

¿ì¸®´Â ¿ì¸®ÀÇ °øºÎ¸¦ Æ©¸µ ±â°èÀÇ °ø½ÄÀûÀÎ Á¤ÀǷκÎÅÍ ½ÃÀÛÇÏ¿©, ¸î¸î °£´ÜÇÑ ÇÁ·Î±×·¥À» ÇÔÀ¸·Î½á ¹«¾ùÀÌ ¿¬°üµÇ¾î Àִ°¡¿¡ ´ëÇÑ ´À³¦À» ¹ßÀü½ÃÄÑ º»´Ù. ±× ´ÙÀ½À¸·Î, Æ©¸µ ±â°è°¡ ¾ÆÁÖ ¿ø½ÃÀûÀε¥ ¹ÝÇÏ¿©, ±× °³³äÀÌ ¾ÆÁÖ º¹ÀâÇÑ ÀýÂ÷±îÁöµµ ¸Á¶óÇÒ ¼ö ÀÖÀ» Á¤µµ·Î ÃæºÐÈ÷ ±¤¹üÀ§ÇÏ´Ù´Â °ÍÀ» ³íÇÑ´Ù. ±× ³íÀÇ´Â, ÇöÀçÀÇ ÄÄÇ»ÅͷΠó¸®µÉ ¼ö ÀÖ´Â °Íµé°ú °°Àº ¸ðµç °è»ê ÀýÂ÷´Â Æ©¸µ ±â°è¿¡¼­ ½ÇÇàµÉ ¼ö ÀÖ´Ù°í ÁÖÀåÇÏ´Â, Æ©¸µ ¸íÁ¦(Turing thesis)·Î ÀýÁ¤¿¡ À̸¥´Ù.

1. Ç¥ÁØ Æ©¸µ ±â°è

¿ì¸®´Â º¹ÀâÇÏ°í Á¤±³ÇÑ ÀúÀåÀå¼Ò¸¦ °®´Â ´Ù¾çÇÑ ¿ÀÅ丶Ÿ¸¦ »ó»óÇÒ ¼ö ÀÖÁö¸¸, Æ©¸µ ±â°èÀÇ ÀúÀåÀå¼Ò´Â ½ÇÁ¦·Î ¾ÆÁÖ °£´ÜÇÏ´Ù. ±× ÀúÀåÀå¼Ò´Â ¼¿(cell)µéÀÇ 1Â÷¿ø ¹è¿­·Î ±¸Ã¼È­ÇÒ ¼ö ÀÖ´Ù. °¢ ¼¿Àº ÇϳªÀÇ ½Éº¼À» ÀúÀåÇÒ ¼ö ÀÖ´Ù. ÀÌ ¹è¿­Àº ¾çÂÊÀ¸·Î ¹«ÇÑÈ÷ È®ÀåµÇ°í µû¶ó¼­ ¹«ÇÑÇÑ ¾çÀÇ Á¤º¸¸¦ ÀúÀåÇÒ ¼ö ÀÖ´Ù. ±× Á¤º¸´Â ¾Æ¹« ¼ø¼­·Î ÀÐÇôÁú ¼ö ÀÖ°í ¹Ù²ð ¼ö ÀÖ´Ù. ¿ì¸®´Â ±×·± ÀúÀåÀå¼Ò¸¦, ½ÇÁ¦ ÄÄÇ»ÅÍ¿¡¼­ »ç¿ëµÇ´Â ÀÚ¼º Å×ÀÌÇÁ¿Í À¯»çÇϱ⠶§¹®¿¡, Å×ÀÌÇÁ (tape) ¶ó ÇÑ´Ù.

(1) Æ©¸µ ±â°èÀÇ Á¤ÀÇ

Æ©¸µ ±â°è´Â Àӽà ÀúÀåÀå¼Ò°¡ Å×ÀÌÇÁÀÎ ¿ÀÅ丶ŸÀÌ´Ù. ÀÌ Å×ÀÌÇÁ´Â ¼¿µé·Î ³ª´µ¾î ÀÖ°í, °¢ ¼¿Àº ÇÑ °³ÀÇ ½Éº¼À» ÀúÀåÇÒ ¼ö ÀÖ´Ù. ÀÌ Å×ÀÌÇÁ¿Í °ü·ÃÇؼ­ Àбâ-¾²±â Çìµå (read-write head) °¡ ÀÖ´Ù. ÀÌ Àбâ-¾²±â Çìµå´Â Å×ÀÌÇÁ¿¡¼­ ¿ÞÂÊ ¶Ç´Â ¿À¸¥ÂÊÀ¸·Î ¿òÁ÷ÀÏ ¼ö ÀÖ°í °¢ À̵¿¸¶´Ù ÇϳªÀÇ ½Éº¼À» ÀÐ°í ¾µ ¼ö ÀÖ´Ù. °è»ê ÀÌ·Ð °³¿äÀÇ ÀϹÝÀûÀÎ ±¸Á¶·ÎºÎÅÍ ¾à°£ ¹þ¾î³ª±â À§ÇÏ¿©, Æ©¸µ ±â°è·Î »ç¿ëÇÏ´Â ¿ÀÅ丶Ÿ´Â ÀÔ·Â ÆÄÀÏÀ̳ª Ưº°ÇÑ Ãâ·ÂÀåÄ¡¸¦ °®Áö ¾ÊÀ» °ÍÀÌ´Ù. ÇÊ¿äÇÑ ÀԷ°ú Ãâ·ÂÀº Å×ÀÌÇÁ¿¡¼­ ÀÌ·ç¾îÁú °ÍÀÌ´Ù. ¿ì¸®´Â ³ªÁß¿¡ ¼¼°¡Áö ±âÃÊ°³³ä¿¡ ÀÖ´Â ÀÌ·¯ÇÑ ÀϹÝÀûÀÎ ¸ðµ¨¿¡ ´ëÇÑ ¼öÁ¤ÀÌ º°·Î Áß¿äÇÏÁö ¾Ê´Ù´Â °ÍÀ» »ìÆ캼 °ÍÀÌ´Ù. ¿ì¸®´Â ¿ì¸®°¡ ³»¸®·Á´Â °á·Ð¿¡ ¾Æ¹« ¿µÇâÀ» ÁÖÁö ¾Ê°í¼­ ÀÔ·Â ÆÄÀÏÀ̳ª Ưº°ÇÑ Ãâ·Â ÀåÄ¡¸¦ À¯ÁöÇÒ ¼ö ÀÖ´Ù.

Æ©¸µ ±â°èÀÇ Á÷°üÀûÀÎ °¡½ÃÈ­¸¦ Á¦°øÇÏ´Â µµÇ¥°¡ ±×¸² 1 ¿¡ ÁÖ¾îÁ® ÀÖ´Ù. Á¤ÀÇ 1 Àº ±× °³³äÀ» ºÐ¸íÇÏ°Ô ÇÑ´Ù.

±×¸² 1

Æ©¸µ ±â°èÀÇ Á¤ÀÇ¿¡¼­, ¥Ò ¡ö ¥Ã - {¡à} ÀÓÀ» °¡Á¤ÇÑ´Ù. Áï, ÀÔ·Â ¾ËÆĺªÀº °ø¹é ½Éº¼À» Æ÷ÇÔÇÏÁö ¾Ê´Â Å×ÀÌÇÁ ¾ËÆĺªÀÇ ºÎºÐÁýÇÕÀÌ´Ù. ¾ÕÀ¸·Î °ð ¸í¹éÇØÁú ÀÌÀ¯ ¶§¹®¿¡ °ø¹é ½Éº¼µéÀº ÀԷ¿¡¼­ Á¦¿ÜÇÑ´Ù. ÀüÀÌ ÇÔ¼ö´Â ´ÙÀ½°ú °°ÀÌ Á¤ÀǵȴÙ.

ÀϹÝÀûÀ¸·Î, ¥ä ´Â Q × ¥Ã ¿¡ ´ëÇÑ ºÎºÐ ÇÔ¼ö (partial function) ÀÌ´Ù. ÀÌ¿¡ ´ëÇÑ Çؼ®Àº Æ©¸µ ±â°è°¡ ÀÛµ¿ÇÏ´Â ¿øÄ¢À» Á¦½ÃÇÑ´Ù. ¥ä ÀÇ ÀμöµéÀº Á¦¾î À¯´ÖÀÇ ÇöÀç »óÅÂ¿Í ÇöÀç ÀÐÇôÁö´Â Å×ÀÌÇÁ ½Éº¼ÀÌ´Ù. ±× °á°ú´Â Á¦¾î À¯´ÖÀÇ »õ·Î¿î »óÅÂ, Àü¿¡ ÀÖ´ø ½Éº¼À» ±³Ã¼ÇÏ´Â »õ·Î¿î Å×ÀÌÇÁ ½Éº¼°ú À̵¿ ½Éº¼ (move symbol) L ¶Ç´Â R ÀÌ´Ù. À̵¿ ½Éº¼Àº Å×ÀÌÇÁ¿¡ »õ·Î¿î ½Éº¼ÀÌ ¾²¿©Áø ÈÄ Àбâ-¾²±â Çìµå°¡ ¿ÞÂÊ ¶Ç´Â ¿À¸¥ÂÊÀ¸·Î À̵¿ÇÏ´ÂÁö¸¦ ³ªÅ¸³½´Ù.

±×¸² 2 (a) À̵¿ Àü°ú (b) À̵¿ ÈÄÀÇ »óȲ.

±×¸² 3 ÀÏ·ÃÀÇ À̵¿µé

Æ©¸µ ±â°è¿¡ ´ëÇÑ ¿©·¯ ´Ù¸¥ Á¤ÀǵéÀ» ¸¸µé ¼ö Àֱ⠶§¹®¿¡, ¿ì¸®°¡ Ç¥ÁØ Æ©¸µ ±â°è (standard Turing machine) ¶ó°í ºÎ¸£´Â ¸ðµ¨ÀÇ ÁÖµÈ Æ¯Â¡À» ¿ä¾àÇÒ ÇÊ¿ä°¡ ÀÖ´Ù.

¿ø·¡ ÀÌµé °ü·ÊµéÀº °è¼ÓµÇ´Â ³íÀÇÀÇ ÆíÀǸ¦ À§ÇÏ¿© ¼±ÅõǾú´Ù. Æ©¸µ ±â°èÀÇ ´Ù¸¥ ¹öÀüµéÀ» »ìÆ캸°í ¿ì¸®ÀÇ Ç¥ÁØ ¸ðµ¨°úÀÇ °ü°è¸¦ ³íÀÇÇÒ °ÍÀÌ´Ù.

Æ©¸µ ±â°èÀÇ Çü»óµéÀ» Ç¥½ÃÇϱâ À§ÇÏ¿©, ¼ø°£Àû ¹¦»çÀÇ °³³äÀ» »ç¿ëÇÑ´Ù. ¸ðµç Çü»óÀº Á¦¾î À¯´ÖÀÇ ÇöÀç »óÅÂ, Å×ÀÌÇÁÀÇ ³»¿ë°ú Àбâ-¾²±â ÇìµåÀÇ À§Ä¡·Î ¿ÏÀüÈ÷ °áÁ¤µÈ´Ù. ¿ì¸®´Â ´ÙÀ½°ú °°Àº Ç¥±â¸¦ »ç¿ëÇÒ °ÍÀÌ´Ù.

¶Ç´Â

±×¸² 4

ÀÌ Ç¥±â´Â ±×¸² 4¿¡ ³ªÅ¸³ª ÀÖ´Â Å×ÀÌÇÁ¸¦ °¡Áö°í »óÅ q ¿¡ ÀÖ´Â ±â°èÀÇ ¼ø°£Àû ¹¦»çÀÌ´Ù. ½Éº¼µé a1, ..., an Àº Å×ÀÌÇÁÀÇ ³»¿ëÀ» ³ªÅ¸³»°í, ¹Ý¸é¿¡ q ´Â Á¦¾î À¯´ÖÀÇ »óŸ¦ Á¤ÀÇÇÑ´Ù. ÀÌ °ü·Ê´Â Àбâ-¾²±â ÇìµåÀÇ À§Ä¡°¡ q ¹Ù·Î µÚ¿¡ ÀÖ´Â ½Éº¼À» Æ÷ÇÔÇÏ°í ÀÖ´Â ¼¿ÀÌ µÇµµ·Ï ¼±ÅõǾú´Ù.
¼ø°£ÀûÀÎ ¹¦»ç´Â ´ÜÁö Àбâ-¾²±â ÇìµåÀÇ ¿À¸¥ÂÊ°ú ¿ÞÂÊ¿¡ ÀÖ´Â À¯ÇÑÇÑ ¾çÀÇ Á¤º¸¸¸À» º¸¿©ÁÖ°í ÀÖ´Ù. Å×ÀÌÇÁÀÇ Æ¯º°È÷ Ç¥±âÇÏÁö ¾ÊÀº ºÎºÐÀº ¸ðµÎ °ø¹é ½Éº¼µéÀ» Æ÷ÇÔÇÏ°í ÀÖ´Ù°í °¡Á¤ÇÑ´Ù. Åë»óÀûÀ¸·Î ±×·¯ÇÑ °ø¹é ½Éº¼µéÀº ¾Æ¹« °ü°è°¡ ¾ø°í ¼ø°£Àû ¹¦»ç¿¡´Â ¸íÈ®ÇÏ°Ô º¸¿©ÁöÁö ¾Ê´Â´Ù. ¸¸¾à °ø¹é ½Éº¼ÀÇ À§Ä¡°¡ ³íÀÇ¿¡ °ü°è°¡ ÀÖ´Ù¸é, °ø¹é ½Éº¼ÀÌ ¼ø°£Àû ¹¦»ç¿¡ ³ªÅ¸³¯ ¼ö ÀÖ´Ù. ¿¹¸¦ µé¸é, ¼ø°£Àû ¹¦»ç q ¡à w ´Â Àбâ-¾²±â Çìµå°¡ w ÀÇ Ã¹ ½Éº¼ ¹Ù·Î ¿ÞÂÊ ¼¿¿¡ ÀÖ°í ÀÌ ¼¿Àº °ø¹é ½Éº¼À» Æ÷ÇÔÇÏ°í ÀÖÀ½À» ³ªÅ¸³½´Ù.

¾ÕÀ¸·ÎÀÇ ³íÀǸ¦ À§ÇÏ¿©, ¹æ±Ý ¸¸µé¾îÁø ´Ù¾çÇÑ °üÂûÀ» °ø½ÄÀûÀÎ ¹æ½ÄÀ¸·Î ¿ä¾àÇÏ´Â °ÍÀÌ Æí¸®ÇÏ´Ù.

¿¹Á¦ 3 Àº ºüÁ®³ª¿Ã ¼ö ¾ø´Â ³¡ÀÌ ¾ø´Â ·çÇÁ¿¡ ÁøÀÔÇϸ鼭 Æ©¸µ ±â°è°¡ ÀüÇô Á¤ÁöÇÏÁö ¾ÊÀ» °¡´É¼ºÀ» º¸¿©ÁØ´Ù. ÀÌ »óȲÀº Æ©¸µ ±â°è¸¦ ³íÀÇÇÏ´Â µ¥ À־ ±âº»ÀûÀÎ ¿ªÇÒÀ» ÇÑ´Ù. µû¶ó¼­ ÀÌ¿¡ ´ëÇØ Æ¯º°ÇÑ Ç¥±â¸¦ »ç¿ëÇÑ´Ù. ¿ì¸®´Â ±× »óȲÀ» ´ÙÀ½°ú °°ÀÌ Ç¥ÇöÇÑ´Ù.

ÀÌ´Â ±â°è°¡ Ãʱâ Çü»ó ¿¡¼­ºÎÅÍ ½ÃÀÛÇÏ¿© ÀüÇô Á¤ÁöÇÏÁö ¾ÊÀ½À» °¡¸®Å²´Ù.

(2) ¾ð¾î ½ÂÀαâ·Î¼­ÀÇ Æ©¸µ ±â°è

Æ©¸µ ±â°è´Â ´ÙÀ½ÀÇ Àǹ̷μ­ ½ÂÀαâ·Î º¼ ¼ö ÀÖ´Ù. ÇÑ ¹®ÀÚ¿­ w °¡ Å×ÀÌÇÁ¿¡ ÀûÇô ÀÖ´Ù. »ç¿ëµÇÁö ¾ÊÀº ºÎºÐÀº °ø¹é ½Éº¼µé·Î ä¿öÁ® ÀÖ´Ù. ±â°è´Â Àбâ-¾²±â Çìµå°¡ w ÀÇ °¡Àå ¿ÞÂÊ ½Éº¼¿¡ À§Ä¡ÇÏ¿© ÀÖ°í Ãʱ⠻óÅ ¿¡¼­ ½ÃÀ۵ȴÙ. ÀÏ·ÃÀÇ À̵¿ ÈÄ¿¡, ¸¸¾à Æ©¸µ ±â°è°¡ Á¾·á »óÅ¿¡ ³õÀÌ°í Á¤ÁöÇϸé, w °¡ ½ÂÀÎµÈ °ÍÀ¸·Î °£ÁֵȴÙ.

ÀÌ Á¤ÀÇ´Â ½ÃÀÛ¿¡ ÀÔ·Â w °¡ Å×ÀÌÇÁ¿¡ ÀûÇôÀÖ°í ¾çÂÊÀº °ø¹é ½Éº¼·Î ä¿öÁ® ÀÖÀ½À» °¡¸®Å²´Ù. °ø¹é ½Éº¼À» ÀԷ¿¡¼­ Á¦¿Ü½ÃÅ°´Â ÀÌÀ¯°¡ ÀÌÁ¦´Â ¸í¹éÇØÁø´Ù. ÀÌ´Â ¸ðµç ÀÔ·ÂÀº ¿À¸¥ÂÊ ¿ÞÂÊÀÌ °ø¹é ½Éº¼µé·Î ä¿öÁ® ÀÖ´Â Å×ÀÌÇÁÀÇ Àß Á¤ÀÇµÈ ¿µ¿ªÀ¸·Î Á¦ÇѵǾî ÀÖÀ½À» È®½ÇÇÏ°Ô ÇÑ´Ù. ÀÌ·¯ÇÑ °ü·Ê°¡ ¾øÀÌ´Â, ±â°è´Â ÀÔ·ÂÀ» ã¾Æº¸¾Æ¾ß ÇÏ´Â ¿µ¿ªÀ» ÇÑÁ¤ÇÒ ¼ö°¡ ¾ø´Ù. ¾ó¸¶³ª ¸¹Àº °ø¹é ½Éº¼µéÀ» º¸µçÁö °£¿¡, Å×ÀÌÇÁÀÇ ´Ù¸¥ °÷¿¡ °ø¹é ½Éº¼ÀÌ ¾Æ´Ñ ÀÔ·ÂÀÌ ÀÖ´Ù´Â °ÍÀ» È®½ÅÇÒ ¼ö°¡ ¾ø´Ù.

Á¤ÀÇ 3 Àº w ¡ô L(M) ÀÏ °æ¿ì ¹«½¼ ÀÏÀÌ ÀϾ¾ß ÇÏ´ÂÁö¸¦ ¸»ÇÏ°í ÀÖ´Ù. ÀÌ´Â ´Ù¸¥ ÀԷ¿¡ ´ëÇÑ °á°ú¿¡ ´ëÇؼ­´Â ¾Æ¹« °Íµµ ¸»ÇÏÁö ¾Ê°í ÀÖ´Ù. w °¡ L(M) ¿¡ ¼ÓÇÏÁö ¾ÊÀ» °æ¿ì, µÎ °¡Áö °¡¿îµ¥ Çϳª°¡ ÀϾ´Ù. ±â°è°¡ Á¾·á »óÅ°¡ ¾Æ´Ñ »óÅ¿¡¼­ Á¤ÁöÇϰųª ¶Ç´Â ¹«ÇÑ ·çÇÁ¿¡ µé¾î°¡¼­ ÀüÇô Á¤ÁöÇÏÁö ¾ÊÀ» ¼ö ÀÖ´Ù. M ÀÌ Á¤ÁöÇÏÁö ¾Ê´Â ¸ðµç ¹®ÀÚ¿­Àº Á¤ÀÇ¿¡ ÀÇÇÏ¿© L(M) ¿¡ ¼ÓÇÏÁö ¾Ê´Â´Ù.

´õ º¹ÀâÇÑ ¾ð¾îÀÇ ÀνÄÀº ´õ¿í ¾î·Æ´Ù. Æ©¸µ ±â°è´Â ¿ø½ÃÀûÀÎ ¸í·ÉµéÀ» °¡Áö°í ÀÖÀ¸¹Ç·Î, ¿ì¸®°¡ °í±Þ ¾ð¾î¸¦ °¡Áö°í ½±°Ô ÇÁ·Î±×·¥ÇÒ ¼ö ÀÖ´Â °è»êµéÀº Æ©¸µ ±â°è¿¡¼­´Â ÀÚÁÖ ¹ø°Å·Î¿öÁø´Ù. ±×·¡µµ ´ÙÀ½ÀÇ ¿¹Á¦µé¿¡¼­ º¸¿©ÁöµíÀÌ, ÇÁ·Î±×·¥Àº ¿©ÀüÈ÷ °¡´ÉÇÏ°í, ±× °³³äÀº ÀÌÇØÇϱ⠽±´Ù.

ÀÌ ¿¹Á¦·ÎºÎÅÍ ¿ì¸®°¡ ³»¸± ¼ö ÀÖ´Â °á·ÐÀº Æ©¸µ ±â°è´Â ¹®¸Æ-ÀÚÀ¯ ¾ð¾î°¡ ¾Æ´Ñ ¾ð¾î¸¦ ÀνÄÇÒ ¼ö ÀÖ´Ù´Â °ÍÀÌ´Ù. ÀÌ°ÍÀÌ Æ©¸µ ±â°Ô°¡ Ǫ½Ã´Ù¿î ¿ÀÅ丶Ÿº¸´Ù ´õ °­·ÂÇϴٴ ù Áõ°ÅÀÌ´Ù.

(3) º¯È¯±â·Î¼­ÀÇ Æ©¸µ ±â°è

¿ì¸®´Â Áö±Ý±îÁö º¯È¯±â (transducer) ¸¦ °øºÎÇÒ ÀÌÀ¯°¡ °ÅÀÇ ¾ø¾ú´Ù. ¾ð¾î À̷п¡¼­, ½ÂÀαⰡ »ç½Ç»ó ÀûÀýÇÏ´Ù. ±×·¯³ª ¿ì¸®°¡ °ð º¸°Ô µÉ °Í°ú °°ÀÌ, Æ©¸µ ±â°è´Â ¾ð¾î ½ÂÀαâ·Î¼­ Èï¹ÌÀÖÀ» »Ó¸¸ ¾Æ´Ï¶ó ÀϹÝÀûÀÎ µðÁöÅÐ ÄÄÇ»ÅÍ¿¡ ´ëÇÑ °£´ÜÇÑ Ãß»óÀû ¸ðµ¨À» ¿ì¸®¿¡°Ô Á¦½ÃÇÑ´Ù. ÄÄÇ»ÅÍÀÇ ÁÖ¿äÇÑ ¸ñÀûÀÌ ÀÔ·ÂÀ» Ãâ·ÂÀ¸·Î º¯È¯½ÃÅ°´Â °ÍÀ̱⠶§¹®¿¡, ÄÄÇ»ÅÍ´Â º¯È¯±â·Î¼­ ÀÛµ¿ÇÑ´Ù. ¸¸¾à Æ©¸µ ±â°è¸¦ »ç¿ëÇÏ¿© ÄÄÇ»ÅÍÀÇ ¸ðµ¨À» ¸¸µé±â¸¦ ¿øÇÑ´Ù¸é, ¿ì¸®´Â ÀÌ Çؼ®À» ´õ ¾ö¹ÐÈ÷ »ìÆ캸¾Æ¾ß¸¸ ÇÑ´Ù.

°è»ê¿¡ ´ëÇÑ ÀÔ·ÂÀº Ãʱ⿡ Å×ÀÌÇÁ¿¡ ÀÖ´Â °ø¹é ½Éº¼ÀÌ ¾Æ´Ñ ¸ðµç ½Éº¼µéÀÌ´Ù. °è»êÀÇ Á¾°á¿¡¼­, Ãâ·ÂÀº ±×¶§ Å×ÀÌÇÁ¿¡ ÀÖ´Â ¸ðµç °ÍÀÌ´Ù. µû¶ó¼­, ¿ì¸®´Â Æ©¸µ ±â°è º¯È¯±â M À» ¾Æ·¡¿Í °°ÀÌ Á¤ÀÇµÈ ÇÔ¼ö f ÀÇ ±¸ÇöÀ¸·Î °£ÁÖÇÒ ¼ö ÀÖ´Ù.

ÀÌ °æ¿ì, M Àº ¾î¶² Á¾·á »óÅ ¿¡ ´ëÇÏ¿©, ¾Æ·¡¿Í °°Àº °è»êÀ» ¼öÇàÇÒ ¼ö ÀÖ¾î¾ß ÇÑ´Ù.

¿ì¸®°¡ °ð ÁÖÀåÇÏ·Á´Â °Íó·³, ¸ðµç ÀϹÝÀûÀÎ ¼öÇÐÀûÀÎ ÇÔ¼öµéÀº, ¾ó¸¶³ª º¹ÀâÇÏµç °£¿¡, Æ©¸µ-°è»ê°¡´ÉÇÏ´Ù. ¿ì¼±, µ¡¼À°ú »ê¼ú ºñ±³¿Í °°Àº, ¸î¸î °£´ÜÇÑ ¿¬»êµéÀ» »ìÆ캸ÀÚ.

¼ö¸¦ ´õÇÏ´Â °ÍÀº ¸ðµç ÄÄÇ»ÅÍÀÇ ±âº»ÀûÀÎ ¿¬»ê °¡¿îµ¥ ÇϳªÀÌ´Ù. ±âº»ÀûÀÎ ¿¬»êµéÀº ´õ º¹ÀâÇÑ ¿¬»êµéÀ» ÇÕ¼ºÇÏ´Â µ¥ ÀϺκÐÀ¸·Î ¿ªÇÒÀ» ÇÑ´Ù. ´Ù¸¥ ±âÃÊ ¿¬»êµéÀº ¹®ÀÚ¿­ º¹»ç¿Í ´Ü¼ø ºñ±³µéÀÌ´Ù. ÀÌµé ¿ª½Ã Æ©¸µ ±â°è¿¡¼­ ½±°Ô ¼öÇàµÉ ¼ö ÀÖ´Ù.

¿¬½À¹®Á¦

1. °í±Þ ÇÁ·Î±×·¡¹Ö ¾ð¾î·Î Æ©¸µ ±â°è ½Ã¹Ä·¹ÀÌÅÍ (simulator) ¸¦ ÀÛ¼ºÇ϶ó. ÀÛ¼ºÇÑ ½Ã¹Ä·¹ÀÌÅÍ´Â Æ©¸µ ±â°èÀÇ ¹¦»ç¸¦, Ãʱâ Çü»ó°ú ÇÔ²², ÀÔ·ÂÀ¸·Î ¹Þ°í, °è»êÀÇ °á°ú¸¦ Ãâ·ÂÀ¸·Î »ý¼ºÇÏ¿©¾ß ÇÑ´Ù.

2. ¸¹¾Æ¾ß ¼¼ °³ÀÇ »óŵéÀ» °¡Áö°í ¾ð¾î L(a(a + b)*) À» ½ÂÀÎÇÏ´Â Æ©¸µ ±â°è¸¦ ¼³°èÇ϶ó. ¥Ò = {a, b} ÀÓÀ» °¡Á¤¤¾³ª´Ù. °°Àº ¾ð¾î¸¦ ½ÂÀÎÇÏ´Â µÎ °³ »óŸ¦ °¡Áö´Â Æ©¸µ ±â°è°¡ Á¸ÀçÇϴ°¡?

3. ¿¹Á¦ 7 ÀÇ Æ©¸µ ±â°è°¡ ÀÔ·Â aba ¿Í aaabbbb °¡ ÁÖ¾îÁú °æ¿ì ¹«¾ùÀ» ÇÏ´ÂÁö¸¦ °áÁ¤Ç϶ó.

4. ¿¹Á¦ 7 ÀÇ Æ©¸µ ±â°è°¡ ¹«ÇÑ ·çÇÁ¿¡ µé¾î°¡°Ô µÇ´Â ÀÔ·ÂÀÌ Àִ°¡?

5. ¾î¶² ¾ð¾î°¡ ¾Æ·¡¿Í °°ÀÌ Á¤ÀÇµÈ Æ©¸µ ±â°è M = ({q0, q1, q2, q3}, {a, b}, {a, b, ¤±}, ¥ä, q0, ¤±, {q3}) ¿¡ ÀÇÇÏ¿© ½ÂÀεǴ°¡?

6. ¸¸¾à ¹®ÀÚ¿­ w °¡ 1 ÀÌ ¾Æ´Ñ ½Éº¼À» Æ÷ÇÔÇÒ °æ¿ì ¿¹Á¦ 10 ¿¡¼­ ¾î¶² ÀÏÀÌ ÀϾ °ÍÀΰ¡?

7. ¾ËÆĺª {a, b} ¿¡ ´ëÇÑ ´ÙÀ½ ¾ð¾îµéÀ» ½ÂÀÎÇÏ´Â Æ©¸µ ±â°è¸¦ ±¸¼ºÇ϶ó.

        (a) L = L(aba*b)

        (b) L = {w : |w| ´Â ¦¼öÀÌ´Ù}

        (c) L = {w : |w| ´Â 3 ÀÇ ¹è¼öÀÌ´Ù}

        (d) L = {anbm : n ¡Ã 1, n ¡Á m}

        (e) L = {w : na(w) = nb(w)}

        (f) L = {anbman+m : n ¡Ã 0, m ¡Ã 1}

        (g) L = {anbnanbn : n ¡Ã 0}

        (h) L = {anb2n : n ¡Ã 1}

    °¢ ¹®Á¦¿¡ ´ëÇÏ¿©, ¥ä ¸¦ ÀÚ¼¼È÷ ¿ÏÀüÇÏ°Ô ÀÛ¼ºÇÏ°í ¿©·¯ ¿¹µéÀ» ÃßÀûÇÏ¿© Á¦½ÃµÈ ´äÀ» È®ÀÎÇ϶ó.

8. ´ÙÀ½ÀÇ ¾ð¾î¸¦ ½ÂÀÎÇÏ´Â Æ©¸µ ±â°è¸¦ ¼³°èÇ϶ó.

        L = {ww : w ¡ô {a, b}+}

9. ´ÙÀ½ÀÇ ÇÔ¼ö¸¦ °è»êÇÏ´Â Æ©¸µ ±â°è¸¦ ±¸¼ºÇ϶ó.

        f(w) = wR

    ¿©±â¼­ w ¡ô {0, 1}+ ÀÌ´Ù.

10. ±æÀÌ°¡ ¦¼öÀÎ ¹®ÀÚ¿­ÀÇ Áß°£À» ã¾Æ³»´Â Æ©¸µ ±â°è¸¦ ¼³°èÇ϶ó. ¸íÈ®ÇÏ°Ô, ¸¸ÀÏ ÀÔ·Â ¹®ÀÚ¿­ÀÌ À̸é (¿©±â¼­ ÀÌ´Ù), Æ©¸µ ±â°è´Â ¹®ÀÚ¿­ À» Ãâ·ÂÇÏ¿©¾ß ÇÑ´Ù, ¿©±â¼­ c ¡ô ¥Ã - ¥Ò ÀÌ´Ù.

11. ÀÏÁø¹ýÀ¸·Î ÁÖ¾îÁø ¾çÀÇ Á¤¼öµé x ¿Í y ¿¡ ´ëÇÑ ´ÙÀ½ÀÇ ÇÔ¼ö¸¦ °è»êÇÏ´Â Æ©¸µ ±â°è¸¦ ¼³°èÇ϶ó.

        (a) f(x) = 3x

        (b) f(x, y) = x - y        x > y
                 = 0             x ¡Â y

        (c) f(x, y) = 2x + 3y

        (d) f(x) = ,               ¸¸ÀÏ x °¡ ¦¼öÀ̸é

                   = ,           ¸¸ÀÏ x °¡ Ȧ¼öÀ̸é

        (e) f(x) = x mod 5

        (f) f(x) = , ¿©±â¼­ ´Â º¸´Ù À۰ųª °°Àº °¡Àå Å« Á¤¼ö¸¦ ³ªÅ¸³½´Ù.

12. °ø¹é ½Éº¼À̳ª 1 À» Æ÷ÇÔÇÏ°í ÀÖ´Â ÀÓÀÇÀÇ ¼¿¿¡¼­ ½ÃÀÛÇÒ °æ¿ì, Å×ÀÌÇÁ°¡ ¾î´À °÷¿¡µçÁö 0 À» °¡Áö°í ¿ÀÁ÷ ±×·² ¶§¿¡¸¸ Á¤ÁöÇÏ´Â ¥Ã = {0, 1, ¤±} ÀÎ Æ©¸µ ±â°Ô¸¦ ¼³°èÇ϶ó.

13. ¿¹Á¦ 8 ¿¡ ´ëÇÑ ¿ÏÀüÇÑ Çظ¦ ÀÛ¼ºÇ϶ó.

14. ¿¹Á¦ 10 ÀÇ Æ©¸µ ±â°è°¡ ÀÔ·Â 111 ÀÌ ÁÖ¾îÁ³À» °æ¿ì °ÅÃÄ°¡¾ß ÇÒ ÀÏ·ÃÀÇ ¼ø°£Àû ¹¦»çµéÀ» Á¦½ÃÇ϶ó. ¸¸¾à ÀÌ ±â°è°¡ Å×ÀÌÇÁ¿¡ 110 À» °¡Áö°í ½ÃÀÛÇÒ °æ¿ì ¾î¶»°Ô µÉ °ÍÀΰ¡?

15. ¿¹Á¦ 10 ÀÇ Æ©¸µ ±â°è°¡ ½ÇÁ¦·Î ÁöÀûÇÑ °è»êÀ» ¼öÇàÇÑ´Ù´Â ³³µæµÉ ¼ö ÀÖ´Â ³íÁõÀ» Á¦½ÃÇ϶ó.

16. ¿¹Á¦ 11 ÀÇ ¸ðµç ¼¼ºÎ»çÇ×µéÀ» ¿Ï¼ºÇ϶ó.

17. ¿¹Á¦ 9 ¿¡¼­ ¿ì¸®´Â x ¿Í y ¸¦ ÀÌÁø¹ýÀ¸·Î Ç¥ÇöÇϱâ·Î °áÁ¤ÇÏ¿´´Ù°í ÇÏÀÚ. Áö½ÃµÈ °è»êÀ» ÀÌÁø¹ý Ç¥Çö¿¡¼­ ÇÏ´Â Æ©¸µ ±â°è ÇÁ·Î±×·¥À» ÀÛ¼ºÇ϶ó.

18. ¸¸¾à x ¿Í y °¡ ½ÊÁø¹ýÀ¸·Î Ç¥ÇöµÇ¾ú´Ù¸é ¿¹Á¦ 9 °¡ ¾î¶»°Ô ÇØ°áµÇ´ÂÁö¸¦ °³·«ÀûÀ¸·Î ¼³¸íÇ϶ó.

19. ÀÌ ÀýÀÇ ¸ðµç ¿¹Á¦µéÀÇ Æ©¸µ ±â°èµéÀÌ ¿ÀÁ÷ ÇϳªÀÇ Á¾·á »óŸ¸À» °¡Áö´Â °ÍÀ» ¾Ë¾ÆÂ÷¸± ¼ö ÀÖÀ» °ÍÀÌ´Ù. ÀϹÝÀûÀ¸·Î ¸ðµç Æ©¸µ ±â°è¿¡ ´ëÇÏ¿© °°Àº ¾ð¾î¸¦ ½ÂÀÎÇÏ´Â Á¾·á »óŸ¦ ¿ÀÁ÷ Çϳª¸¸ °¡Áö´Â ¶Ç ´Ù¸¥ Æ©¸µ ±â°è°¡ Á¸ÀçÇÏ´Â °ÍÀÌ »ç½ÇÀΰ¡?

20. Á¤ÀÇ 2 ´Â Æ©¸µ ±â°è¿¡ ÀÇÇÏ¿© ½ÂÀεǴ ¾ð¾î¿¡¼­ ºó ¹®ÀÚ¿­À» Á¦¿Ü½ÃÄ×´Ù. ¥ë ¸¦ Æ÷ÇÔÇÏ´Â ¾ð¾î°¡ ½ÂÀ뵃 ¼ö ÀÖµµ·Ï Á¤ÀǸ¦ ¼öÁ¤Ç϶ó.

2. º¹ÀâÇÑ Å½ºÅ©¸¦ À§ÇÑ Æ©¸µ ±â°è °áÇÕ

¿ì¸®´Â ¸ðµç ÄÄÇ»ÅÍ¿¡¼­ ã¾ÆÁú ¼ö ÀÖ´Â ¸î¸î Áß¿äÇÑ ¿¬»êµéÀÌ Æ©¸µ ±â°è¿¡¼­ ¾î¶»°Ô ¼öÇàµÉ ¼ö ÀÖ´ÂÁö¸¦ ºÐ¸íÇÏ°Ô º¸¿´´Ù. µðÁöÅÐ ÄÄÇ»ÅÍ¿¡¼­, ±×·¯ÇÑ ±âÃÊÀûÀÎ ¿¬»êµéÀÌ ´õ¿í º¹ÀâÇÑ ¸í·É¾îµéÀ» ±¸¼ºÇÏ´Â ¿ä¼Ò°¡ µÇ±â ¶§¹®¿¡, ¾î¶»°Ô ÀÌµé ±âÃÊ ¿¬»êµéÀÌ Æ©¸µ ±â°è¿¡¼­ Â¥¸ÂÃß¾îÁú ¼ö ÀÖ´ÂÁö »ìÆ캸±â·Î ÇÏÀÚ. Æ©¸µ ±â°èµéÀÌ ¾î¶»°Ô °áÇÕµÉ ¼ö ÀÖ´ÂÁö¸¦ º¸À̱â À§ÇÏ¿©, ¿ì¸®´Â ÇÁ·Î±×·¡¹Ö¿¡¼­ÀÇ º¸ÆíÀûÀÎ °ü½ÀÀ» µû¸¥´Ù. ¿ì¸®´Â °í±Þ ¹¦»ç·ÎºÎÅÍ ½ÃÀÛÇÏ¿©, ¿ì¸®´Â ÇÁ·Î±×·¥ÀÌ ¿ì¸®°¡ ÀÛ¾÷ÇÏ´Â ½ÇÁ¦ ¾ð¾î·Î ÀÛ¼ºµÉ ¶§±îÁö °è¼ÓÇؼ­ ´Ùµë¾î °£´Ù. Æ©¸µ ±â°è´Â °í±Þ ¼öÁØ¿¡¼­ ÀÛ¾÷ÇÏ´Â ½ÇÁ¦ ¾ð¾î·Î ÀÛ¼ºµÉ ¶§±îÁö °è¼ÓÇؼ­ ´Ùµë¾î °£´Ù. Æ©¸µ ±â°è´Â °í±Þ ¼öÁØ¿¡¼­ ¿©·¯ °¡Áö ¹æ¹ýÀ¸·Î ±â¼úµÉ ¼ö ÀÖ´Ù. ºí·Ï µµÇ¥ (block diagram) ¿Í ÀÇ»çÄÚµå (pseudocode) ´Â ¾ÕÀ¸·ÎÀÇ ³íÀÇ¿¡¼­ °¡Àå ÀÚÁÖ »ç¿ëÇÏ°Ô µÉ µÎ °¡Áö ¹æ¹ýÀÌ´Ù. ºí·Ï µµÇ¥¿¡¼­, °è»êµéÀº »óÀÚ (box) ¾È¿¡ ³õÀδÙ. »óÀÚ ¾È¿¡ ±× °è»êÀÇ ±â´ÉÀÌ ¼³¸íµÈ´Ù. ±×·¯³ª ³»ºÎÀûÀÎ ¼¼ºÎ»çÇ×µéÀº º¸¿©ÁöÁö ¾Ê´Â´Ù. ±×·¯ÇÑ »óÀÚµéÀ» »ç¿ëÇÏ¿©, ±× °è»êµéÀÌ ½ÇÁ¦·Î ±¸¼ºµÉ ¼ö ÀÖ´Ù´Â °ÍÀ» ¾Ï½ÃÀûÀ¸·Î ÁÖÀåÇÑ´Ù. ù ¹ø° ¿¹·Î¼­, ¿¹Á¦ 9 ¿Í 11 ÀÇ ±â°èµéÀ» °áÇÕÇØ º»´Ù.

±×¸² 5

Æ©¸µ ±â°è¸¦ °í±Þ ¼öÁØÀ¸·Î º¸ÀÌ´Â ¶Ç ´Ù¸¥ À¯¿ëÇÑ ¹æ¹ýÀº ÀÇ»çÄÚµå (pseudocode) ¿Í ¿¬°üµÈ °ÍÀÌ´Ù. ÄÄÇ»ÅÍ ÇÁ·Î±×·¡¹Ö¿¡¼­, ÀÇ»çÄÚµå´Â ¿ì¸®°¡ ÀÌÇØÇÒ ÇÊ¿ä°¡ ÀÖ´Â Àǹ̸¦ Ç¥ÇöÇÏ´Â ¼­¼úÀûÀÎ ¹®±¸¸¦ »ç¿ëÇÏ¿© °è»êÀÇ À±°ûÀ» ³ªÅ¸³»´Â ¹æ¹ýÀÌ´Ù. ÀÌ ¼­¼úÀº ÄÄÇ»ÅÍ¿¡¼­´Â »ç¿ëµÉ ¼ö ¾øÁö¸¸, ¿ì¸®´Â ÀÌ ¼­¼úÀÌ ÇÊ¿äÇÒ ¶§ ÀûÀýÇÑ ¾ð¾î·Î ¹ø¿ªµÉ ¼ö ÀÖ´Ù°í °¡Á¤ÇÑ´Ù. ÀÇ»çÄÚµåÀÇ °£´ÜÇÑ ÇÑ Á¾·ù´Â, ¿¹·Î¼­, ¸ÅÅ©·Î¸í·É¾îÀÇ °³³äÀ» µé ¼ö ÀÖ´Ù. ¸ÅÅ©·Î¸í·É¾î´Â ÀÏ·ÃÀÇ Àú±Þ ¹®Àåµé (lower level statements) ¿¡ ´ëÇÑ ´ÜÀÏ-¹®Àå ¾à¾î (single-statement shorthand) ÀÌ´Ù. ¿ì¼± ¸ÅÅ©·Î¸í·É¾î¸¦ Àú±Þ ¾ð¾î¸¦ »ç¿ëÇÏ¿© Á¤ÀÇÇÑ´Ù. ¿ì¸®´Â ¸ÅÅ©·Î¸í·É¾î°¡ ÀÖ´Â °÷¸¶´Ù ¿¬°üµÈ Àú±Þ Äڵ尡 ´ëüµÈ´Ù´Â °¡Á¤ÇÏ¿¡ ÇÁ·Î±×·¥¿¡¼­ ¸ÅÅ©·Î¸í·É¾î¸¦ »ç¿ëÇÑ´Ù. ÀÌ °³³äÀº Æ©¸µ ±â°è ÇÁ·Î±×·¥¿¡¼­ ¾ÆÁÖ À¯¿ëÇÏ´Ù.

ÇÑ °ÉÀ½ ´õ ³ª¾Æ°¡¼­, ¿ì¸®´Â ¸ÅÅ©·Î¸í·É¾î¸¦ ºÎÇÁ·Î±×·¥À¸·Î ±³Ã¼ÇÒ ¼ö ÀÖ´Ù. ÀϹÝÀûÀ¸·Î, ¸ÅÅ©·Î¸í·É¾î´Â ¸Å¹ø ³ªÅ¸³¯ ¶§¸¶´Ù ½ÇÁ¦ ÄÚµå·Î ±³Ã¼µÈ´Ù, ¹Ý¸é¿¡ ºÎÇÁ·Î±×·¥Àº ÇÊ¿äÇÒ ¶§¸¶´Ù ¹Ýº¹ÀûÀ¸·Î È£ÃâµÇ´Â ÇϳªÀÇ ÄÚµåÀÌ´Ù. À̸¦ ±×·² µíÇÏ°Ô ¸¸µé±â À§ÇÏ¿©, Æ©¸µ ±â°è°¡ ¾î¶»°Ô ´Ù¸¥ Æ©¸µ ±â°è¿¡ ÀÇÇÏ¿© ¹Ýº¹ÀûÀ¸·Î È£ÃâµÉ ¼ö ÀÖ´Â ºÎÇÁ·Î±×·¥Ã³·³ »ç¿ëµÉ ¼ö ÀÖ´ÂÁö¸¦ ´ë·«ÀûÀ¸·Î ¼³¸íÇØ º¸ÀÚ. ÀÌ´Â »õ·Î¿î ±â´ÉÀÌ ÇÊ¿äÇÏ´Ù. ºÎÇÁ·Î±×·¥À¸·ÎºÎÅÍ ±Íȯ½Ã È£ÃâÇÑ ÇÁ·Î±×·¥ÀÇ Çü»óÀ» Àç»ý¼ºÇÒ ¼ö ÀÖµµ·Ï ±× Çü»ó¿¡ ´ëÇÑ Á¤º¸¸¦ ÀúÀåÇÏ´Â ´É·Â, ¿¹¸¦ µé¾î, »óÅ ¿¡ ÀÖ´Â ±â°è A °¡ ±â°è B ¸¦ È£ÃâÇÑ´Ù°í ÇÏÀÚ. B °¡ ³¡³µÀ» ¶§, ¿ì¸®´Â »óÅ ¿¡¼­ ÇÁ·Î±×·¥ A ¸¦, Àбâ-¾²±â Çìµå´Â ¿ø·¡ÀÇ À§Ä¡¿¡¼­ (Çìµå´Â B ÀÇ ÀÛ¾÷Áß¿¡ ¿òÁ÷¿´À» °ÍÀÌ´Ù), ´Ù½Ã ½ÃÀÛÇÏ°íÀÚ ÇÑ´Ù. ´Ù¸¥ °æ¿ì¿¡´Â, A °¡ »óÅ ¿¡¼­ B ¸¦ È£ÃâÇÒ ¼öµµ ÀÖÀ» °ÍÀÌ´Ù. ±× °æ¿ì¿¡´Â Á¦¾î´Â ·Î µ¹¾Æ¿Í¾ß ÇÒ °ÍÀÌ´Ù. Á¦¾î À̵¿ ¹®Á¦¸¦ ÇØ°áÇϱâ À§ÇÏ¿©, ¿ì¸®´Â A ·ÎºÎÅÍ B ·Î ±×¸®°í ¶Ç ¿ªÀ¸·Î Á¤º¸¸¦ Àü´ÞÇÒ ¼ö ÀÖ¾î¾ß ÇÏ°í, Á¦¾î°¡ B ·ÎºÎÅÍ µ¹¾Æ¿ÔÀ» ¶§ A ÀÇ Çü»óÀ» Àç»ý¼ºÇÒ ¼ö ÀÖ°í Àӽ÷Πº¸·ùµÈ A ÀÇ °è»êÀÌ B ÀÇ ½ÇÇàÀ¸·Î ¿µÇâÀ» ¹ÞÁö ¾Ê´Â´Ù´Â °ÍÀ» º¸ÀåÇÒ ¼ö ÀÖ¾î¾ß ÇÑ´Ù. À̸¦ ÇØ°áÇϱâ À§ÇÏ¿©, ±×¸² 6 ¿¡¼­ º¸¿©Áø °Í°ú °°ÀÌ Å×ÀÌÇÁ¸¦ ¿©·¯ ¿µ¿ªÀ¸·Î ³ª´­ ¼ö ÀÖ´Ù.

±×¸² 6

A °¡ B ¸¦ È£ÃâÇϱâ Àü¿¡, A ´Â B °¡ ÇÊ¿äÇÑ Á¤º¸¸¦ (¿¹¸¦ µé¸é, A ÀÇ ÇöÀç »óÅÂ, B ¿¡ ´ëÇÑ Àμöµé) Å×ÀÌÇÁÀÇ ÇÑ ¿µ¿ª T ¿¡ Àû´Â´Ù. A ´Â »óŸ¦ B ÀÇ ½ÃÀÛ »óÅ·Π¿Å±èÀ¸·Î½á Á¦¾î¸¦ B ·Î Àü´ÞÇÑ´Ù. ¿Å±ä ÈÄ¿¡, B ´Â ÀÔ·ÂÀ» ã±â À§ÇÏ¿© T ¸¦ »ç¿ëÇÑ´Ù. B ÀÇ ÀÛ¾÷°ø°£Àº T ¿Í A ÀÇ ÀÛ¾÷ °ø°£°ú´Â ºÐ¸®µÇ¾î ÀÖ´Ù. µû¶ó¼­ ¾î¶² ¹æÇصµ ¹ß»ýÇÒ ¼ö ¾ø´Ù. B °¡ ÀÛ¾÷À» ¸¶ÃÆÀ» ¶§, B ´Â °ü·ÃµÈ °á°ú¸¦, A °¡ °á°ú¸¦ ã±â¸¦ ±â´ëÇÏ´Â, T ·Î µ¹·ÁÁÙ °ÍÀÌ´Ù. ÀÌ´Â ÁøÂ¥ ÄÄÇ»ÅÍ¿¡¼­ ÇÁ·Î±×·¥ÀÌ È£ÃâµÉ ¶§ ½ÇÁ¦·Î ÀϾ´Â °Í°ú ¾ÆÁÖ À¯»çÇÏ´Ù´Â °ÍÀ» À¯ÀÇÇ϶ó.

À̵é ÀÇ»çÄڵ带 ¾î¶»°Ô ½ÇÁ¦ÀÇ Æ©¸µ ±â°è ÇÁ·Î±×·¥À¸·Î ¹ø¿ªÇÏ´ÂÁö¸¦ (Àû¾îµµ ÀÌ·ÐÀûÀ¸·Î¶óµµ) ¾Ë°í ÀÖ´Ù¸é, Æ©¸µ ±â°è¸¦ ÀÇ»çÄÚµå·Î ÇÁ·Î±×·¥ÇÒ ¼ö ÀÖ´Ù.

±×¸² 7

ÀÌ ¿¹Á¦µéÀÇ ¼­¼úÀûÀÎ ¼ºÁú¿¡µµ ºÒ±¸ÇÏ°í, Æ©¸µ ±â°è°¡, ¿øÄ¢ÀûÀ¸·Î ´Ù¼Ò ¿ø½ÃÀûÀÌÁö¸¸, ¾ÆÁÖ °­·ÂÇÏ°Ô ¸¸µé±â À§ÇÏ¿© ¿©·Á °¡Áö ¹æ¹ýÀ¸·Î °áÇÕµÉ ¼ö ÀÖ´Ù´Â °ÍÀ» ÃßÃø (conjecture) ÇÏ°Ô Çϱâ À§ÇÏ¿© ³Ê¹« ¾ïÁö¸¦ ºÎ¸° °ÍÀº ¾Æ´Ï´Ù. Á¦½ÃµÈ ¿¹µéÀÌ ¸ðµç °ÍÀ» Áõ¸íÇÏ¿´´Ù°í ÁÖÀåÇÒ ¸¸Å­ ÀϹÝÀûÀÌ°í ÀÚ¼¼ÇÏÁö´Â ¾ÊÁö¸¸, Æ©¸µ ±â°è°¡ ¾î¶² ¾ÆÁÖ º¹ÀâÇÑ ÀϵéÀ» ÇÒ ¼ö ÀÖ´Ù´Â °ÍÀÌ ÀÌ ½ÃÁ¡¿¡¼­´Â ±×·² µíÇÏ¿©¾ß ÇÒ °ÍÀÌ´Ù.

¿¬½À¹®Á¦

1. ¿¹Á¦ 14 ¿¡ ´ëÇÑ ¿ÏÀüÇÑ Çظ¦ ÀÛ¼ºÇ϶ó.

2. ¾çÀÇ Á¤¼ö¿Í À½ÀÇ Á¤¼ö¸¦ Ç¥ÇöÇÏ´Â °ü·Ê¸¦ ¼º¸³Ç϶ó. Á¦½ÃÇÑ °ü·Ê¸¦ »ç¿ëÇÏ¿©, x - y ¸¦ °è»êÇϱâ À§ÇÑ °¨»ê±â (subtracter) ÀÇ ±¸¼ºÀ» °³·«ÀûÀ¸·Î º¸¿©¶ó.

3. °¡»ê±â, °¨»ê±â, º¹»ç±â, ¶Ç´Â ½Â»ê±â (multiplier) µéÀ» ÀÌ¿ëÇÏ¿©, ¸ðµç ¾çÀÇ Á¤¼ö n ¿¡ ´ëÇÑ ¾Æ·¡ÀÇ ÇÔ¼öµéÀ» °è»êÇÏ´Â Æ©¸µ ±â°èµé¿¡ ´ëÇÑ ºí·Ï µµÇ¥¸¦ ±×·Á¶ó.

        (a) f(n) = n(n + 1)

        (b) f(n) =

        (c) f(n) =

        (d) f(n) = n!

        (e) f(n) =

4. ¸ðµç ¿¡ ´ëÇÏ¿© ´ÙÀ½°ú °°ÀÌ Á¤ÀÇµÈ ÇÔ¼ö f ÀÇ ±¸ÇöÀ» °³·«ÀûÀ¸·Î º¸¿©ÁÖ±â À§ÇÏ¿© ºí·Ï µµÇ¥¸¦ »ç¿ëÇ϶ó.

        

    ¿©±â¼­, ¸¸¾à ¾î¶² µÎ w µµ ±æÀÌ°¡ °°Áö ¾Ê´Ù¸é, i ´Â À» ¸¸Á·ÇÏ°í, ±× ¿ÜÀÇ °æ¿ì, i = 0 ÀÌ´Ù.

5. {a, b} ¿¡ ´ëÇÑ ´ÙÀ½ÀÇ ¾ð¾îµéÀ» ½ÂÀÎÇÏ´Â Æ©¸µ ±â°èµé¿¡ ´ëÇÑ "°í±Þ-¼öÁØ (high-level)" À¸·Î ¼³¸íÇ϶ó. °¢ ¹®Á¦¿¡ ´ëÇÏ¿©, ±¸ÇöÇϱ⿡ ÇÕ¸®ÀûÀ¸·Î ½±´Ù°í »ý°¢µÇ´Â ÀûÀýÇÑ ¸ÅÅ©·Î¸í·É¾îµéÀÇ ÁýÇÕÀ» Á¤ÀÇÇÏ¿© ´äÀ» »ç¿ëÇ϶ó.

        (a)

        (b)

        (c) (a) ¿¡¼­ÀÇ ¾ð¾îÀÇ ¿©ÁýÇÕ

        (d)

        (e) L = {an : n Àº ¼Ò¼öÀÌ´Ù}

6. Æ©¸µ ±â°è¿¡¼­ À¯¸®¼ö¸¦ Ç¥ÇöÇÏ´Â ¹æ¹ýÀ» Á¦¾ÈÇÏ°í, À¯¸®¼öµéÀ» ´õÇÏ°í »©´Â ¹æ¹ýµéÀ» °³·«ÀûÀ¸·Î ¼³¸íÇ϶ó.

7. º¸ÅëÀÇ ½ÊÁø¹ýÀ¸·Î ÁÖ¾îÁø ¾çÀÇ Á¤¼öµé x ¿Í y ÀÇ µ¡¼À°ú °ö¼ÀÀ» ¼öÇàÇÒ ¼ö ÀÖ´Â Æ©¸µ ±â°èÀÇ ±¸¼ºÀ» °³·«ÀûÀ¸·Î ¼³¸íÇ϶ó.

8. ¾Æ·¡ÀÇ ¸ÅÅ©·Î¸í·É¾î¸¦ ±¸ÇöÇ϶ó.

        

    ÀÌ ¸ÅÅ©·Î¸í·É¾î´Â ±â°è°¡ Çö À§Ä¡ÀÇ ¿À¸¥ÂÊÀ¸·Î ù ¹ø°·Î ³ªÅ¸³ª´Â ½Éº¼ a ¸¦ ã´Â °ÍÀ» ³ªÅ¸³½´Ù. ¸¸¾à °ø¹é ½Éº¼ ÀÌÀü¿¡ a ¸¦ ¸¸³­´Ù¸é, ±â°è´Â »óÅ ¿¡ ³õÀÌ°í, ±×·¸Áö ¾ÊÀ¸¸é, ±â°è´Â »óÅ ¿¡ ³õÀδÙ.

10. ¿¬½À¹®Á¦ 8 ÀÇ ¸ÅÅ©·Î¸í·É¾î searchright ¸¦ »ç¿ëÇÏ¿© °¡Àå ¿ÞÂÊ¿¡ ÀÖ´Â a ÀÇ ¹Ù·Î ¿ÞÂÊ¿¡ ÀÖ´Â ½Éº¼À» °ø¹é ½Éº¼·Î ±³Ã¼ÇÏ´Â Æ©¸µ ±â°è ÇÁ·Î±×·¥À» ÀÛ¼ºÇ϶ó. ¸¸¾à ÀÔ·ÂÀÌ a ¸¦ Æ÷ÇÔÇÏ°í ÀÖÁö ¾Ê´Ù¸é, °¡Àå ¿À¸¥ÂÊÀÇ °ø¹éÀÌ ¾Æ´Ñ ½Éº¼À» b ·Î ±³Ã¼ÇÑ´Ù.

3. Æ©¸µ ¸íÁ¦

¾Õ¼­ÀÇ ³íÀÇ´Â Æ©¸µ ±â°è°¡ ¾î¶»°Ô °£´ÜÇÑ ºÎºÐµé·ÎºÎÅÍ ±¸¼ºµÉ ¼ö Àִ°¡¸¦ º¸¿©ÁÖ¾úÀ» »Ó ¾Æ´Ï¶ó, Àú±Þ-¼öÁØ ¿ÀÅ丶Ÿ¸¦ °¡Áö°í ÀÛ¾÷ÇÏ´Â °Í¿¡ ´ëÇÑ ºÎÁ¤ÀûÀÎ °ßÇظ¦ º¸¿©ÁÖ¾ú´Ù. ºí·Ï µµÇ¥³ª ÀÇ»çÄڵ带 ´ëÀÀµÇ´Â Æ©¸µ ±â°è·Î ¹ø¿ªÇÏ´Â °ÍÀÌ ¾ÆÁÖ ÀÛÀº »ó»ó·Â ¶Ç´Â ¿µ¸®ÇÔÀ» ¿äÇÏ´Â °Í¿¡ ¹ÝÇÏ¿©, ½ÇÁ¦·Î ±×·¸°Ô ÇÏ´Â °ÍÀº ¸¹Àº ½Ã°£ÀÌ °É¸®°í, ½Ç¼öÇϱ⠽±°í ¿ì¸®ÀÇ ÀÌÇØ¿¡ Å« µµ¿òÀÌ µÇÁö ¾Ê´Â´Ù. Æ©¸µ ±â°èÀÇ ¸í·É¾îµéÀÇ ÁýÇÕÀº ¾ÆÁÖ Á¦¾àÀûÀ̾ Æò¹üÇÏÁö ¾ÊÀº ¹®Á¦µé¿¡ ´ëÇÑ ³íÀÇ, Çعý, ¶Ç´Â Áõ¸íÀÌ ¾ÆÁÖ Áö·çÇÏ´Ù.

¿ì¸®´Â Áö±Ý ³­°ü¿¡ ³õ¿© ÀÖ´Ù. ¿ì¸®´Â Æ©¸µ ±â°è°¡ ¸íÈ®ÇÑ ÇÁ·Î±×·¥µéÀÌ ¸¶·ÃµÈ °£´ÜÇÑ ¿¬»êµé»Ó ¾Æ´Ï¶ó, ºí·Ï µµÇ¥³ª ÀÇ»çÄÚµå·Î ¼³¸íµÉ ¼ö ÀÖ´Â ´õ¿í º¹ÀâÇÑ ÀýÂ÷µéµµ ¼öÇàÇÒ ¼ö ÀÖ´Ù°í ÁÖÀåÇÏ°í ½Í´Ù. ¹Ý´ë Àǻ翡 ´ëÇÏ¿© ÀÌ ÁÖÀåÀ» ÁöÅ°±â À§ÇÏ¿©, °ü·ÃµÈ ÇÁ·Î±×·¥À» ¸íÈ®ÇÏ°Ô º¸¿©¾ß ÇÑ´Ù. ±×·¯³ª ±×·¯´Â °ÍÀº À¯ÄèÇÏÁö ¾Ê°í Á¤½ÅÀ» »ê¸¸ÇÏ°Ô ÇÑ´Ù. µû¶ó¼­ °¡´ÉÇϸé ÇÇÇØ¾ß ÇÑ´Ù. ¾î¶»°Ô Çؼ­µçÁö, ¿ì¸®´Â Àú±Þ-¼öÁØÀÇ ±ä Äڵ带 ÀÛ¼ºÇÏÁö ¾Ê°í¼­ Æ©¸µ ±â°è¿¡ ´ëÇÑ »ó´çÈ÷ ¾ö¹ÐÇÑ ³íÀǸ¦ ÇÒ ¼ö ÀÖ´Â ¹æ¹ýÀ» ãÀ¸·Á ÇÑ´Ù. ºÒÇàÇÏ°Ôµµ ÀÌ ±ÃÁö¿¡¼­ ºüÁ® ³ª¿Ã ¿ÏÀüÇÏ°Ô ¸¸Á·ÇÒ ¹æ¹ýÀº ¾ø´Ù. ¿ì¸®°¡ ÇÒ ¼ö ÀÖ´Â ÃÖ¼±ÀÇ ¹æ¹ýÀº Àû´çÇÑ Å¸Çù¿¡ µµ´ÞÇÏ´Â °ÍÀÌ´Ù. ¿ì¸®°¡ ¾î¶»°Ô ±×·¯ÇÑ Å¸ÇùÀ» ÀÌ·ê ¼ö ÀÖ´ÂÁö¸¦ ¾Ë¾Æº¸±â À§ÇÏ¿©, ¿ì¸®´Â ´Ù¼Ò öÇÐÀûÀÎ ÅäÀǸ¦ Çغ¸ÀÚ.

¿ì¸®´Â ¾ÕÀýÀÇ ¿¹Á¦·ÎºÎÅÍ ¾à°£ °£´ÜÇÑ °á·ÐµéÀ» ³»¸± ¼ö ÀÖ´Ù. ù°´Â Æ©¸µ ±â°è°¡ Ǫ½Ã´Ù¿î ¿ÀÅ丶Ÿº¸´Ù´Â °­·ÂÇÏ´Ù (ÀÌ ¾ð±Þ¿¡ ´ëÇؼ­´Â, ÀÌ Àý ³¡¿¡ ÀÖ´Â ¿¬½À¹®Á¦ 2 ¸¦ º¸¾Æ¶ó). ¿¹Á¦ 8 ¿¡¼­, ¹®¸Æ-ÀÚÀ¯°¡ ¾Æ´Ñ ¾ð¾î (°á·ÐÀûÀ¸·Î, ±× ¾ð¾î¿¡ ´ëÇÑ ¾î¶² Ǫ½Ã´Ù¿î ¿ÀÅ丶Ÿµµ Á¸ÀçÇÏÁö ¾Ê´Â) ¿¡ ´ëÇÑ Æ©¸µ ±â°èÀÇ ±¸¼ºÀ» °³·«ÀûÀ¸·Î ¼³¸íÇÏ¿´´Ù. ¿¹Á¦ 9, 10 °ú 11 Àº Æ©¸µ ±â°èµéÀÌ ¸î¸î »ê¼ú ¿¬»êµéÀ» °è»êÇÏ°í, ¹®ÀÚ¿­ Á¶ÀÛÀ» ¼öÇàÇÏ°í ±×¸®°í ¸î¸î °£´ÜÇÑ ºñ±³µéÀ» ÇÒ ¼ö ÀÖÀ½À» º¸¿´´Ù. ¶ÇÇÑ ¾î¶»°Ô ¿ø½ÃÀûÀÎ ¿¬»êµéÀÌ ´õ º¹ÀâÇÑ ¹®Á¦µéÀ» ÇØ°áÇϱâ À§ÇÏ¿© °áÇÕµÉ ¼ö ÀÖ°í, ¾î¶»°Ô ¿©·¯ Æ©¸µ ±â°èµéÀÌ Á¶¸³µÉ ¼ö ÀÖ°í, ¾î¶»°Ô ÇÑ ÇÁ·Î±×·¥ÀÌ ¶Ç ´Ù¸¥ ÇÁ·Î±×·¥ÀÇ ºÎÇÁ·Î±×·¥À¸·Î ÀÛµ¿ÇÒ ¼ö ÀÖ´ÂÁö¸¦ ³íÀÇÇÏ¿´´Ù. ¾ÆÁÖ º¹ÀâÇÑ ¿¬»êµéÀÌ ÀÌ·± ½ÄÀ¸·Î ¸¸µé¾îÁú ¼ö Àֱ⠶§¹®¿¡, ¿ì¸®´Â Æ©¸µ ±â°è°¡ ´É·Â¸é¿¡¼­ ÀüÇüÀûÀÎ ÄÄÇ»ÅÍ¿¡ Á¢±ÙÇϱ⠽ÃÀÛÇÏ´Â °ÍÀÌ ¾Æ´Ñ°¡ »ý°¢ÇÒ ¼ö ÀÖ´Ù.

Æ©¸µ ±â°è°¡, ¾î¶² Àǹ̷Î, ´É·Â¸é¿¡¼­ ÀüÇüÀûÀÎ µðÁöÅÐ ÄÄÇ»ÅÍ¿Í °°À» °ÍÀ̶ó´Â ÃßÃøÀ» ÇÑ´Ù°í ÇÏÀÚ. ¾î¶»°Ô ¿ì¸®´Â ±×·¯ÇÑ °¡¼³À» Á¤´çÈ­ÇÒ ¼ö ÀÖÀ»±î? ±×°ÍÀ» Á¤´çÈ­Çϱâ À§ÇÏ¿©, ¿ì¸®´Â ÀÏ·ÃÀÇ Á¡Á¡ ´õ ¾î·Á¿î ¹®Á¦µéÀ» ÅÃÇÏ°í ±× ¹®Á¦µéÀÌ ¾î¶² Æ©¸µ ±â°è¿¡ ÀÇÇÏ¿© ¾î¶»°Ô ÇØ°áµÇ´ÂÁö¸¦ º¸ÀÏ ¼ö ÀÖÀ» °ÍÀÌ´Ù. ¶ÇÇÑ ¿ì¸®´Â ƯÁ¤ ÄÄÇ»ÅÍÀÇ ±â°è ¾ð¾î ¸í·É¾î ÁýÇÕÀ» ÅÃÇÏ°í ±× ÁýÇÕ¿¡ ¼ÓÇÑ ¸ðµç ¸í·É¾îµéÀ» ¼öÇàÇÒ ¼ö ÀÖ´Â Æ©¸µ ±â°è¸¦ ¼³°èÇÒ ¼öµµ ÀÖÀ» °ÍÀÌ´Ù. ÀÌ°ÍÀº ÀǽÉÇÒ ¿©Áöµµ ¾øÀÌ ÂüÀ»¼ºÀ» ¿ä±¸Çϳª, ¸¸¾à ¿ì¸®ÀÇ °¡¼³ÀÌ ¿Ç´Ù¸é, ¿øÄ¢ÀûÀ¸·Î ¹Ýµå½Ã °¡´ÉÇÒ °ÍÀÌ´Ù. ÀÌ ¹æÇâÀ¸·ÎÀÇ ¸ðµç ¼º°øÀº °¡¼³ÀÌ ÂüÀ̶ó´Â °Í¿¡ ´ëÇÑ ½Å³äÀ» °­ÇÏ°Ô ÇÏÁö¸¸, ¿©ÀüÈ÷ Áõ¸í¿¡ À̸£Áö´Â ¸øÇÑ´Ù. ±× ¾î·Á¿òÀº ¿ì¸®°¡ ÀüÇüÀûÀÎ µðÁöÅÐ ÄÄÇ»ÅÍ°¡ Á¤È®È÷ ¹«¾ùÀ» ÀǹÌÇÏ´ÂÁö¸¦ ¸ð¸£°í ¶ÇÇÑ ÀÚ¼¼ÇÑ Á¤ÀǸ¦ ³»¸± ¹æ¹ýÀ» °¡Áö°í ÀÖÁö ¾Ê´Ù´Â »ç½Ç¿¡ ÀÖ´Ù.

¶ÇÇÑ ±× ¹®Á¦¸¦ ´Ù¸¥ ¸é¿¡¼­ºÎÅÍ Á¢±ÙÇÒ ¼ö ÀÖ´Ù. ¿ì¸®°¡ ÄÄÇ»ÅÍ ÇÁ·Î±×·¥À¸·Î ÀÛ¼ºÇÒ ¼ö ÀÖÁö¸¸ ¾î¶² Æ©¸µ ±â°è·Îµµ ÇÁ·Î±×·¥ÇÒ ¼ö ¾ø´Â ¾î¶² ÇÁ·Î½ÃÀú¸¦ ãÀ¸·Á°í ½ÃµµÇÒ ¼ö ÀÖÀ» °ÍÀÌ´Ù. ¸¸¾à ÀÌ°ÍÀÌ °¡´ÉÇÏ´Ù¸é, ÀÌ °¡¼³À» ºÎÁ¤ÇÒ ¼ö ÀÖ´Â ±Ù°Å¸¦ °®°Ô µÉ °ÍÀÌ´Ù. ±×·¯³ª ÀÌÁ¦±îÁö ¾î´À ´©±¸µµ ¹Ý·Ê¸¦ ¸¸µé¾î ³¾ ¼ö°¡ ¾ø¾ú´Ù. ¸ðµç ±×·¯ÇÑ ½Ãµµ°¡ ½ÇÆÐÇÏ¿´´Ù´Â »ç½ÇÀº ±×·± ½Ãµµ°¡ ÀÌ·ç¾îÁú ¼ö ¾ø´Ù´Â Á¤È²ÀûÀÎ Áõ°Å·Î °£ÁÖµÉ ¼ö ÀÖÀ» °ÍÀÌ´Ù. ¸ðµç ¡ÈÄ´Â Æ©¸µ ±â°è°¡ ¿øÄ¢ÀûÀ¸·Î ¸ðµç ÄÄÇ»Å͸¸Å­ °­·ÂÇÏ´Ù´Â °ÍÀÌ´Ù.

ÀÌ·± ŸÀÔÀÇ ³íÀÇ´Â 1930 ³â´ë Áß¹ÝÀÇ A. M. Turing °ú ´Ù¸¥ »ç¶÷µé·Î ÇÏ¿©±Ý Æ©¸µ ¸íÁ¦ (Turing thesis) ¶ó ºÒ¸®´Â À¯¸íÇÑ ÃßÃø (conjecture) À» ¸¸µé¾î ³»°Ô ÇÏ¿´´Ù. ÀÌ °¡¼³Àº ±â°èÀûÀÎ ¹æ¹ýÀ¸·Î ¼öÇàµÉ ¼ö ÀÖ´Â ¸ðµç °è»êÀº ¾î¶² Æ©¸µ ±â°è¿¡ ÀÇÇÏ¿© ½ÇÇàµÉ ¼ö ÀÖ´Ù´Â °ÍÀ» ¸»ÇÑ´Ù.

ÀÌ´Â °³·«ÀûÀÎ Áø¼úÀÌ´Ù. µû¶ó¼­ Æ©¸µ ¸íÁ¦°¡ ¹«¾ùÀÎÁö¸¦ °è¼ÓÇؼ­ ¸¶À½¿¡ °£Á÷ÇÏ´Â °ÍÀÌ Áß¿äÇÏ´Ù. ÀÌ°ÍÀº Áõ¸íµÉ ¼ö ÀÖ´Â ¾î¶² °ÍÀº ¾Æ´Ï´Ù. ±×·¸°Ô Çϱâ À§Çؼ­´Â, ¿ì¸®´Â "±â°èÀûÀÎ ¹æ¹ý" À̶ó´Â ¸»À» Á¤È®ÇÏ°Ô Á¤ÀÇÇؾ߸¸ ÇÑ´Ù. ÀÌ´Â ¾î¶² ´Ù¸¥ Ãß»óÀûÀÎ ¸ðµ¨À» ÇÊ¿ä·Î ÇÒ °ÍÀÌ°í ¿ì¸®¿¡°Ô Àüº¸´Ù ´õ ÀÌ»óÀÇ ÁøÀüÀ» ÁÖÁö ¾Ê´Â´Ù. Æ©¸µ ¸íÁ¦´Â ¹«¾ùÀÌ ±â°èÀûÀÎ °è»êÀ» ±¸¼ºÇϴ°¡ÀÇ Á¤ÀǷμ­ ´õ ÀûÀýÇÏ°Ô º¸¿©Áø´Ù. °è»êÀÌ ¾î¶² Æ©¸µ ±â°è¿¡ ÀÇÇÏ¿© ¼öÇàµÉ ¼ö ÀÖ°í ¿ÀÁ÷ ±×·² ¶§¿¡¸¸ ±â°èÀûÀ̶ó ÇÑ´Ù.

¿ì¸®°¡ ÀÌ·± ÀÚ¼¼¸¦ ÅÃÇÏ¿© Æ©¸µ ¸íÁ¦¸¦ ´Ü¼øÈ÷ Á¤ÀÇ·Î °£ÁÖÇÑ´Ù¸é, ¿ì¸®´Â ÀÌ Á¤ÀÇ°¡ ÃæºÐÇÏ°Ô ±¤¹üÀ§ÇÑ°¡¿Í °°Àº Áú¹®À» Á¦±âÇÑ´Ù. ÀÌ°ÍÀÌ ¿ì¸®°¡ ÇöÀç ÄÄÇ»ÅÍ·Î ÇÏ°í ÀÖ´Â (±×¸®°í ¾Æ¸¶µµ ¹Ì·¡¿¡ ÇÒ ¼ö ÀÖÀ») °ÍÀ» ¸Á¶óÇÒ ¼ö ÀÖÀ» Á¤µµ·Î ÃæºÐÈ÷ ±¤¹üÀ§ÇÑ°¡? È®½ÇÇÑ "yes" ´Â °¡´ÉÇÏÁö ¾ÊÁö¸¸, ±àÁ¤ÀûÀÎ Áõ°Å´Â ¸Å¿ì °­ÇÏ´Ù. Æ©¸µ ±â°è¸¦ ±â°èÀûÀÎ °è»ê¿¡ ´ëÇÑ Á¤ÀÇ·Î ¹Þ¾ÆµéÀÌ´Â ¸î¸î ³í°ÅµéÀº ´ÙÀ½°ú °°´Ù.

ÀÌ·¯ÇÑ ³í°ÅµéÀº Á¤È²ÀûÀ̸ç, ±×¸®°í Æ©¸µ ¸íÁ¦´Â ±×·± ³í°Åµé·Î Áõ¸íµÉ ¼ö ¾ø´Ù. ±×·± ±×·²½ÎÇÔ¿¡µµ ºÒ±¸ÇÏ°í, Æ©¸µ ¸íÁ¦´Â ¿©ÀüÈ÷ °¡Á¤ÀÌ´Ù. ±×·¯³ª Æ©¸µ ¸íÁ¦¸¦ ´Ü¼øÇÏ°Ô ÀÓÀÇÀÇ Á¤ÀÇ·Î º¸´Â °ÍÀº Áß¿äÇÑ Á¡À» ÀÒ°Ô µÈ´Ù. ¾î¶² Àǹ̿¡¼­, Æ©¸µ ¸íÁ¦´Â ¹°¸®Çаú È­ÇÐÀÇ ±âº» ¿øÄ¢µéÀÌ ÇÏ´Â °Íó·³ ÄÄÇ»ÅÍ °úÇп¡¼­ °°Àº ¿ªÇÒÀ» ÇÑ´Ù. ¿¹¸¦ µé¾î, °íÀüÀûÀÎ ¹°¸®ÇÐÀº ÁÖ·Î NewtonÀÇ ¿îµ¿ ¹ýÄ¢µé¿¡ ±Ù°Å¸¦ µÎ°í ÀÖ´Ù. ¿ì¸®°¡ ºñ·Ï ±×°ÍµéÀ» ¹ýÄ¢À̶ó ºÎ¸£°í ÀÖÀ¸³ª, ±×µéÀÌ ³í¸®ÀûÀÎ ÇÊ¿¬¼ºÀ» °¡Áö°í ÀÖ´Â °ÍÀº ¾Æ´Ï´Ù. Â÷¶ó¸®, ±×µéÀº ¹°¸®ÀûÀÎ ¼¼°èÀÇ ¸¹Àº °ÍÀ» ¼³¸íÇÏ´Â ±×·²µíÇÑ ¸ðµ¨µéÀÌ´Ù. ±× ¹ýÄ¢À¸·ÎºÎÅÍ ¿ì¸®°¡ ³»¸° °á·ÐµéÀÌ ¿ì¸®ÀÇ °æÇè°ú °üÂû°ú ÀÏÄ¡Çϱ⠶§¹®¿¡ ¿ì¸®´Â ±× ¹ýÄ¢µéÀ» ÀÎÁ¤ÇÏ´Â °ÍÀÌ´Ù. ±×·¯ÇÑ ¹ýÄ¢µéÀº, ºñ·Ï ¹«¿ëÁö¹°ÀÌ µÉ ¼ö´Â ÀÖÁö¸¸, ÂüÀ̶ó°í Áõ¸íµÉ ¼ö ¾ø´Ù. ¸¸¾à ½ÇÇèÀûÀÎ °á°ú°¡ ¹ýÄ¢µé¿¡ ±Ù°ÅÇÑ °á·Ð°ú »ó¹ÝµÈ´Ù¸é, ¿ì¸®´Â ±× ¹ýÄ¢µéÀÇ Á¤´ç¼º¿¡ ´ëÇÏ¿© ÀǽÉÇϱ⠽ÃÀÛÇÒ °ÍÀÌ´Ù. ¹Ý¸é¿¡, ¾î¶² ¹ýÄ¢À» ¹«·ÂÈ­ÇÏ´Â °Í¿¡ ´ëÇÑ ¹Ýº¹µÈ ½ÇÆд ±× ¹ýÄ¢¿¡ ´ëÇÑ ¿ì¸®ÀÇ È®½ÅÀ» °­ÇÏ°Ô ÇÑ´Ù. ÀÌ°ÍÀÌ Æ©¸µ ¸íÁ¦¿¡ ´ëÇÑ ÀÔÀåÀÌ´Ù. µû¶ó¼­ ¿ì¸®°¡ ÀÌ ¸íÁ¦¸¦ ÄÄÇ»ÅÍ °úÇÐÀÇ ±âº» ¹ýÄ¢À¸·Î »ý°¢ÇÏ´Â ÀÌÀ¯°¡ µÈ´Ù. À̷κÎÅÍ ³»¸° ¿ì¸®ÀÇ °á·ÐÀº ¿ì¸®°¡ ½ÇÁ¦ÀÇ ÄÄÇ»ÅÍ¿¡ ´ëÇÏ¿© ¾Ë°í ÀÖ´Â °Í°ú ÀÏÄ¡ÇÏ°í, Áö±Ý±îÁö, ÀÌ °á·ÐÀ» ¹«¿ëÁö¹°·Î ¸¸µé·Á°í ÇÏ´Â ¸ðµç ½ÃµµµéÀÌ ½ÇÆÐÇß´Ù. ±×·¯³ª ¾î´À ´©±º°¡°¡ Æ©¸µ ±â°è¿¡ ÀÇÇÏ¿© ¸Á¶óµÇÁö ¾ÊÁö¸¸ ¿©ÀüÈ÷ ±â°èÀûÀÎ °è»êÀÇ Á÷°üÀûÀÎ °³³ä¿¡´Â Æ÷ÇԵǴ ¾î¶² Æ÷ÂøÇϱ⠾î·Á¿î »óȲÀ» ¼³¸íÇÏ´Â ¶Ç ´Ù¸¥ Á¤ÀǸ¦ Á¦¾ÈÇÒ °¡´É¼ºÀº Ç×»ó Á¸ÀçÇÑ´Ù. ±×·¯ÇÑ ÀÏÀÌ ÀϾ¸é, ±× °á°ú·Î ÀϾ´Â ¿ì¸®ÀÇ ³íÀÇ °¡¿îµ¥ ÀϺδ ½É°¢ÇÏ°Ô ¼öÁ¤µÇ¾î¾ß ÇÒ °ÍÀÌ´Ù. ±×·¯³ª ±×·¸°Ô µÉ °¡´É¼ºÀº ¸Å¿ì ÀÛ¾Æ º¸ÀδÙ.

Æ©¸µ ¸íÁ¦¸¦ ¹Þ¾ÆµéÀÓÀ¸·Î½á, ¿ì¸®´Â ¾Ë°í¸®ÁòÀÇ Á¤È®ÇÑ Á¤ÀǸ¦ Á¦½ÃÇÒ ½ÃÁ¡¿¡ ÀÖ´Ù.

¾Ë°í¸®ÁòÀ» Æ©¸µ ±â°è ÇÁ·Î±×·¥°ú µ¿ÀϽÃÇÔÀ¸·Î½á, ¿ì¸®´Â "...¾Ë°í¸®ÁòÀÌ Á¸ÀçÇÑ´Ù" ȤÀº "...¾Ë°í¸®ÁòÀÌ Á¸ÀçÇÏÁö ¾Ê´Â´Ù" ¿Í °°Àº ÁÖÀåµéÀ» ¾ö¹ÐÇÏ°Ô Áõ¸íÇÒ ¼ö ÀÖ°Ô µÈ´Ù. ±×·¯³ª, »ó´ëÀûÀ¸·Î °£´ÜÇÑ ¹®Á¦µéÀÏÁö¶óµµ ±×¿¡ ´ëÇÑ ¾Ë°í¸®ÁòÀ» ¸íÈ®ÇÏ°Ô ±¸¼ºÇÏ´Â °ÍÀº ¾ÆÁÖ ±ä ÀÛ¾÷ÀÌ´Ù. ±×·¯ÇÑ À¯ÄèÇÏÁö ¾ÊÀº ¿¹»óÀ» ÇÇÇϱâ À§ÇÏ¿©, Æ©¸µ ¸íÁ¦¿¡ È£¼ÒÇÏ¿© ¸ðµç ÄÄÇ»ÅÍ¿¡¼­ ÇÒ ¼ö ÀÖ´Â ¸ðµç ÀÏÀº ¶ÇÇÑ Æ©¸µ ±â°è¿¡¼­ ÇÒ ¼ö ÀÖ´Ù´Â °ÍÀ» ÁÖÀåÇÑ´Ù. °á·ÐÀûÀ¸·Î, Á¤ÀÇ 1 ¿¡¼­ "Æ©¸µ ±â°è" ¸¦ "Pascal ÇÁ·Î±×·¥" À¸·Î ´ëüÇÒ ¼ö ÀÖ´Ù. ÀÌ·¸°Ô ÇÏ¸é ¾Ë°í¸®ÁòÀ» Ç¥½ÃÇÏ´Â µ¥¿¡ ´ëÇÑ ºÎ´ãÀ» »ó´çÈ÷ ÁÙ¿©ÁÙ °ÍÀÌ´Ù. ½ÇÁ¦·Î, ¿ì¸®°¡ ÀÌ¹Ì ÇÏ¿´´ø °Í°ú °°ÀÌ, ¿ì¸®´Â ÇÑ ´Ü°è ´õ ³ª¾Æ°¡¼­, ¸»·Î µÈ ¼³¸í ¶Ç´Â ºí·Ï µµÇ¥µéÀ», ¸¸¾à ¿ì¸®°¡ °¨È÷ ÇÏ·Á ÇÑ´Ù¸é Æ©¸µ ±â°è ÇÁ·Î±×·¥À¸·Î ÀÛ¼ºÇÒ ¼ö ÀÖ´Ù´Â °¡Á¤ÇÏ¿¡, ¾Ë°í¸®ÁòÀ¸·Î ÀÎÁ¤ÇÒ °ÍÀÌ´Ù. ÀÌ´Â ³íÀǸ¦ ±²ÀåÈ÷ °£´ÜÇÏ°Ô Çϳª, ´ç¿¬È÷ ¿ì¸®¿¡°Ô ºñÆÇÀÇ ¿©Áö¸¦ ³²±ä´Ù. "Pascal ÇÁ·Î±×·¥" Àº È®½ÇÇÏ°Ô Á¤ÀǵǾî ÀÖÀ¸³ª, ¸íÈ®ÇÑ ¸»·ÎµÈ ¼³¸íÀº ±×·¸Áö ¾Ê´Ù. ±×¸®°í Á¸ÀçÇÏÁö ¾Ê´Â ¾Ë°í¸®ÁòÀ» Á¸ÀçÇÑ´Ù°í ÁÖÀåÇÏ´Â À§ÇèÀÌ ÀÖ´Ù. ±×·¯³ª ÀÌ·± À§ÇèÀº ¿ì¸®°¡ ³íÀǸ¦ °£´ÜÇÏ°í Á÷°üÀûÀ¸·Î ¸íÈ®ÇÏ°Ô À¯ÁöÇÒ ¼ö ÀÖ°í, ´Ù¼Ò º¹ÀâÇÑ ÀýÂ÷µé¿¡ ´ëÇؼ­ °£¸íÇÑ ¼³¸íÀ» Á¦½ÃÇÒ ¼ö ÀÖ´Ù´Â »ç½Ç·Î ±× ÀÌ»óÀ¸·Î »ó¼âµÈ´Ù. ÀÌ·¯ÇÑ ÁÖÀåµéÀÇ Á¤´ç¼º¿¡ ´ëÇÏ¿© ÀDZ¸½ÉÀ» °¡Áö´Â µ¶ÀÚµéÀº Àû´çÇÑ ÇÁ·Î±×·¥À» ¾î¶² ÇÁ·Î±×·¡¹Ö ¾ð¾î·Î ÀÛ¼ºÇÔÀ¸·Î½á ±×·± ÀDZ¸½ÉµéÀ» ÂѾƹö¸± ¼ö ÀÖÀ» °ÍÀÌ´Ù.

¿¬½À¹®Á¦

1. ¼±ÅÃÇÑ ÄÄÇ»ÅÍ¿¡ ´ëÇÑ ±â°Ô ¾ð¾î ¸í·É¾îµéÀÇ ÁýÇÕÀ» °í·ÁÇÏÀÚ. ÀÌ ÁýÇÕ¿¡ ¼ÓÇÑ ¿©·¯ ¸í·É¾îµéÀÌ ¾î¶»°Ô Æ©¸µ ±â°è¿¡ ÀÇÇÏ¿© ¼öÇàµÉ ¼ö ÀÖ´ÂÁö¸¦ °³·«ÀûÀ¸·Î ¼³¸íÇ϶ó.

2. À§ÀÇ ³íÀÇ¿¡¼­, ¿ì¸®´Â Æ©¸µ ±â°è°¡ Ǫ½Ã´Ù¿î ¿ÀÅ丶Ÿº¸´Ù °­·ÂÇÑ °Íó·³ »ý°¢µÈ´Ù°í ¸»ÇÏ¿´´Ù. Æ©¸µ ±â°ÔÀÇ Å×ÀÌÇÁ¸¦ ½ºÅÃó·³ ÀÛµ¿ÇÒ ¼ö ÀÖ°Ô ¸¸µé ¼ö Àֱ⠶§¹®¿¡, ½ÇÁ¦·Î Æ©¸µ ±â°è°¡ ´õ °­·ÂÇÏ´Ù°í ÁÖÀåÇÒ ¼ö ÀÖ´Ù°í º¸¿©Áø´Ù. ÀÌ ³íÀÇ¿¡¼­ ¾î¶² Áß¿äÇÑ ¿ä¼Ò°¡ °í·ÁµÇÁö ¾Ê¾Ò´Â°¡?

3. ³Î¸® ¾Ë·ÁÁø ¹®Çå¿¡ Æ©¸µ ±â°è¿¡ ´ëÇÑ ¿©·¯ Àç¹ÌÀÖ´Â ³í¹®µéÀÌ ÀÖ´Ù. ±× Áß ¿ì¼öÇÑ °ÍÀº Scientific American, May 1984 ¿¡ °ÔÀçµÈ, Á¦¸ñÀÌ "Turing Machines" ÀÎ, J. E. Hopcroft ÀÇ ³í¹®ÀÌ´Ù. ÀÌ ³í¹®Àº ¿ì¸®°¡ ¿©±â¼­ ¼Ò°³ÇÑ °³³äµé¿¡ ´ëÇÏ¿© À̾߱âÇÏ¿´°í ¶Ç Turing °ú ´Ù¸¥ »ç¶÷µéÀÇ ÀÛ¾÷µéÀÌ ÇàÇØÁø ¿ª»çÀûÀÎ Á¤È²À» Á¦½ÃÇÏ¿´´Ù. ÀÌ ³í¹®À» ã¾Æ Àаí, ±×¿¡ ´ëÇÑ ºñÆòÀ» ½áº¸¾Æ¶ó.