Korean Article Bank

Çѱ¹½ÅÇÐ³í¹®ÀºÇà¿¡ ´ëÇÏ¿©

2007/06/25 (08:57) from 84.173.141.157' of 84.173.141.157' Article Number : 518
Delete Modify ¹ÎÂùÈ« Access : 7225 , Lines : 115
±«µ¨, ¿¡¼Å, ¹ÙÈå
Download : Goedel.htm (26 Kbytes)



»ý¹°ÇÐ ¾øÀÌ ¸¶À½À» ¾Ë ¼ö Àִ°¡? : Douglas R. Hofstadter ÁöÀ½, ¹ÎÂùÈ«




 
 
   




±«µ¨, ¿¡¼Å, ¹ÙÈå



°úÇлç»ó8È£(1994³â-º½) : Douglas R. Hofstadter ÁöÀ½, BasicBooks, 1979, ¹ÎÂùÈ« (Çѳ²´ë ±³¼ö ¡¤ öÇÐ), ¹ü¾ç»ç ÃâÆǺÎ, Page 24~51



¥°.¡¶±«µ¨, ¿¡¼Å, ¹ÙÈå Gödel, Escher, Bach : Eternal Golden Braid¡·´Â 1979 ³â ¹Ì±¹¿¡¼­ °£ÇàµÇ¾ú°í ±× ´ÙÀ½ ÇØ¿¡ ºñ¼Ò¼³ºÎ¹®ÀÇ Ç½¸®Ã³»óÀ» ¼ö»óÇϴ ȣÇÁ½ºÅÂÅÍ (D. Hofstadter, 1945 ~) ÀÇ ¿ªÀú´Ù. ÀÌ Ã¥¿¡¼­ ÀúÀÚ°¡ ¼³¸íÇÏ°í ¼³µæÇÏ·Á ÇÏ´Â ¾ÆÀ̵ð¾î´Â ¸Å¿ì ¸¹´Ù. ¹«·Á 750 ÂÊÀ̳ª µÇ´Â ¹æ´ëÇÑ Ã¥À̳ª ¸¹Àº ¾ê±â¸¦ ´ã°í ÀÖ´Ù´Â °Ç ´ç¿¬ÇÑ ÀÏÀÌ°Ú´Ù. ±×·¯³ª ÀÌÃ¥ÀÇ ÁÖµÈ ÁٰŸ®´Â ¿ª½Ã ¼ö¸®³í¸®ÇÐÀÇ È¸±ÍÀÌ·Ð (recursion theory) ¶Ç´Â ȸ±ÍÇÔ¼ö·Ð (recursive function theory) ÀÌ´Ù. ÀÌ Ã¥¿¡¼­ ¿ì¸®´Â 'Çü½Äü°è (formal system)' ÀÇ ±âº»°³³äµé·ÎºÎÅÍ ½ÃÀÛÇؼ­ 20 ¼¼±â ¼ö¸®³í¸®ÇÐÀÇ ²ÉÀ̶ó ÇÒ '±«µ¨ Á¤¸® (Gödel Theorem)' ¿¡ À̸£±â±îÁö ȸ±ÍÀÌ·ÐÀÇ ÁٰŸ®¿¡ ´ëÇá¿© Á¤È®ÇÏ°íµµ Ä£ÀýÇÑ, °Ô´Ù°¡ Èï¹Ì¸¸Á¡ÀÇ ¾È³»ÀÚ¸¦ ¸¸³¯ ¼ö ÀÖ´Ù.

¹°·Ð Çö´ë ¼ö¸®³í¸®ÇÐÀÇ Áß¿äÇÑ ¼º°ú¸¦ ¼³¸íÇÏ°í ¼±ÀüÇÏ´Â °ÍÀÌ È£ÇÁ½ºÅÂÅÍ°¡ ÀüÇÏ·Á´Â ¸Þ½ÃÁöÀÇ ÀüºÎ´Â ¾Æ´Ï´Ù. ¿ø·¡ ÄÄÇ»ÅÍ °úÇÐÀÚÀÎ ÀúÀÚ´Â ±«µ¨ Á¤¸®¿¡ µµ´ÞÇÏ´Â Áß°£ ±æ¸ñµé¿¡¼­ ÀÇ¹Ì¿Í Çؼ®, ÄÄÇ»ÅÍÀÇ »ó-ÇÏÀ§ ¾ð¾îµé, Á¤½Å°ú »ç°í µî¿¡ ´ëÇÑ ÀÚ½ÅÀÇ °ßÇظ¦ Àý¹¦ÇÏ°Ô ³¢¿ö³Ö°í ÀÖÀ¸¸ç ¸¶Áö¸· ºÎºÐÀÇ µÎ Àå¿¡¼­´Â µ¶Àڵ鿡°Ô ÀΰøÁö´ÉÀÇ ±âº»Àû ¾ÆÀ̵ð¾î¿Í °£´ÜÇÑ ¿ª»ç, ±×¸®°í ¾ÕÀ¸·ÎÀÇ Àü¸ÁÀ» ±×·ÁÁÖ°í ÀÖ´Ù.

ÇÏÁö¸¸ ÀΰøÁö´ÉÇÐÀº Áö³­ 10 ³â°£ ¾öû³­ º¯È­¸¦ °Þ¾ú´Ù. ±×·¸´Ù¸é ÀΰøÁö´É¿¡ ´ëÇؼ­ ¸»Çϴ åÀÌ 15 ³â Àü¿¡ ¾²¿©Áø °Å¶ó¸é Ȥ½Ã ³Ê¹« ³°Àº°Ô ¾Æ´Ñ°¡? ¾Æ´Ñ°Ô ¾Æ´Ï¶ó ÀÌÃ¥¿¡¼­ '½Å°æ¸Á' ÀÌ´Ï 'º´·ÄºÐ»êó¸® (Paraller Distributed Proccessing)' ´Ï ¶Ç´Â 'ÆÛÁöÀÌ·Ð' ÀÌ´Ï ÇÏ´Â ÃÖ±Ù ÀΰøÁö´ÉÇÐÀÇ °³³äµéÀ» ã¾Æº¼ ¼ö´Â ¾ø´Ù. ÀÌÃ¥¿¡¼­ ´Ù·ç´Â °ÍÀº È£Áú·£µå (J. Haugeland) °¡ 'GOFAI (Good Old-Fashioned AI)'1)   ¶ó°í ºÒ·¶´ø ÀΰøÁö´É, Áï Á¤º¸¸¦ Á÷·Ä·Î ó¸®ÇÏ´Â µðÁöÅÐ ÄÄÇ»Å͸¦ ¸ðµ¨·Î ÇÑ ÀΰøÁö´ÉÀÌ¿ä, ÄÄÇ»Åͳª Àΰ£ÀÇ µÎ³ú³ª º»ÁúÀûÀ¸·Î ±âÈ£¸¦ Á¶ÀÛÇÏ°í ó¸® (symbol manipulation) ÇÏ´Â ±â°è¶ó´Â Á¡¿¡¼­ ÀÏÄ¡ÇÑ´Ù°í »ý°¢ÇÏ´Â °íÀüÀûÀÎ (?) °³³äÀÇ ÀΰøÁö´ÉÀÌ´Ù. ±×·¸´Ù°í Çؼ­ È£ÇÁ½ºÅÂÅÍ°¡ ¼³¸íÇÏ´Â ÀΰøÁö´ÉÀÌ ¿ª»çÀû °ü½É°Å¸®¿¡ ºÒ°úÇÑ Èê·¯°£ ¿¾ ¾ê±â¶ó°í ÇÒ ¼ö´Â ¾ø´Ù. ÀΰøÁö´ÉÇп¡ Æз¯´ÙÀÓÀ̶õ°Ô ÀÖ´Ù¸é ¾ÆÁ÷Àº GOFAI°¡ ±× ÀÚ¸®¸¦ °í¼öÇÏ°í ÀÖ´Â °ÍÀÌ´Ù.

¥±. üÄÚ Å»ýÀÇ ¼öÇÐÀÚ¿ä, ³í¸®ÇÐÀÚ¿´´ø ±«µ¨ (K. Gödel, 1906 ~ 1978) Àº °ÅÀÇ '³í¸®ÇÐÀÇ ¾ÆÀν´Å¸ÀÎ' À̶ó°í ºÒ¸± ¸¸ÇÑ »ç¶÷ÀÌ´Ù. ±«µ¨Àº 1931 ³Í, ±×·¯´Ï±î 25 ¼¼¿¡ <¼öÇÐ ¿ø¸® (Principia mathematica) ¹× ±× ¿¬°üü°è¿¡ À־ Çü½ÄÀûÀ¸·Î °áÁ¤ºÒ°¡´ÉÇÑ ¸íÁ¦¿¡ °úÇÏ¿©> ¶ó´Â, ³»¿ëµµ ¸÷½Ã ¾î·Æ°í Á¦¸ñÁ¶Â÷ Á¢±ÙÀ» Çã¶ôÄ¡ ¾Ê´Â ³í¹®À» ¹ßÇ¥ÇÏ¿© °ÅÀÇ 100 ³â°£¿¡ °ÉÄ£ ¼öÇÐÀÚµéÀÇ ³ë·Â, Áï ¼öÇÐÀÇ Àü ¿µ¿ªÀ» Æ÷°ýÇÒ ¼ö ÀÖ´Â °ø¸®Ã¼°è¸¦ È®¸³ÇÏ·Á´Â ³ë·Â¿¡ Á¾ÁöºÎ¸¦ Âï¾ú´Ù.

¹ÙÈå´Â ´ëÀ§¹ý (counterpoint) À» ¿Ï¼ºÇÑ °íÀü½Ã´ë À½¾ÇÀÇ °ÅÀåÀÌ¸ç ¿¡¼Å´Â ±Ý¼¼±â¿¡ È°µ¿ÇÑ È­°¡´Ù. ´ëÀ§¹ýÀ̶õ µ¶¸³µÈ µÎ ¸á·Îµð°¡ ÇÔ²² ¶Ç´Â ±³Â÷ÀûÀ¸·Î ¼¯¿©¼­ ¿¬ÁֵǴ À½¾ÇÇü½ÄÀÌ´Ù. ÁÖ ¸á·Îµð¿¡ ´ëÇÑ ¹ÝÁÖ ÀÚü°¡ ¶Ç ÇϳªÀÇ ¸á·Îµð¸¦ ÀÌ·ç´Â °ÍÀÌ´Ù. 17 ¼¼±â±îÁö È­¼ºÇÐÀº ÀÚ¿¬°úÇÐÀÇ ÇÑ ºÐ¾ß·Î °£ÁֵǾúÀ» Á¤µµ·Î È­¼ºÇаú ´ëÀ§¹ý µî À½¾ÇÀÇ ÀÌ·ÐÀû ºÎºÐµéÀº ¸Å¿ì ¼öÇÐÀûÀÎ ±¸Á¶¸¦ °®°í ÀÖ´Ù. À½¹ÝÀ» ÆǸÅÇÏ´Â ¿µ¾÷»ç¿øµéÀº "ÅÂ¾Æ ¶§ºÎÅÍ ¹ÙÈåÀÇ À½¾ÇÀ» µé·ÁÁÖ¸é ¾ÆÀÌ°¡ ÀüÁ¦°¡ µÈ´Ù" ´À´Ï ÇÏ´Â º°·Î ¹Ï±âÁö ¾Ê´Â ¾ê±â¸¦ ÁÖ¿ö¼¶±â¸é¼­ õÀç ¾ÆÀ̸¦ ¹ÙÈå´Â ºÎ¸ðÀÇ È²´çÇÑ ±â´ë¸¦ ºÎÃß±â´Â°¡ Çϸé, ÇÑÆíÀ¸·Î ¼ö¸®°úÇаú À½¾ÇÀ» (¹ÙµÏÀ̳ª ü½º¿Í ÇÔ²²) ³ªÀÌ ¾î¸° õÀç°¡ µîÀåÇÒ ¼ö ÀÖ´Â ºÐ¾ß·Î ²ÅÀ¸¸é¼­ À½¾Ç°ú ¼öÇÐÀÇ °ü·ÃÀ» °Å·ÐÇÏ´Â »ç¶÷µéµµ °¡²û ÀÖ±â´Â ÇÏ´Ù. ±×·¸´Ù ÇÏ´õ¶óµµ ±«µ¨ Á¤¸®¿Í ¹ÙÈåÀÇ À½¾ÇÀÌ °øÀ¯ÇÏ´Â ³í¸®Àû ±¸Á¶¸¦ ã°Ú´Ù´Â ÀúÀÚÀÇ »ý°¢Àº ÂüÀ¸·Î ºñ¾àÀûÀÎ ¹ß»óÀ̶ó ¾Æ´ÏÇÒ ¼ö ¾ø´Ù. ³ª´Â È£ÇÁ½ºÅÂÅÍÀÇ ¹ÙÈå¿¡ ´ëÇÑ °¨ÅºÀ» °ø°¨ÇÒ ¸¸Å­ÀÇ À½¾ÇÀû ½Ä°ßµµ ¾ø´Âµ¥´Ù°¡ ¹ÙÈå À½¾Ç¿¡ ´ëÇÑ ¼³¸íÀ» ½â Àß ÀÌÇØÇÒ ¼öµµ ¾ø¾ú´Ù. °Ô´Ù°¡ ¹ÙÈåÀÇ ÀÛÇ°¿¡ ³ªÅ¸³ª´Â ȸ±Í±¸Á¶ (recursive structure) °¡ °ú¿¬ ³í¸®ÇÐÀÇ È¸±ÍÇÔ¼ö¿Í Á¤¸»·Î °°ÀºÁö¿¡ ´ëÇؼ­µµ º°·Î ±àÁ¤ÇÒ ¼ö°¡ ¾ø´Ù. ±×·¸Áö¸¸ ±×°ÍÀ¸·Î ÀÎÇØ ³í¸®ÇÐÀÇ Áß¿ä °³³ä¿¡ ´ëÇÑ ÀúÀÚÀÇ ¼³¸íÀ» µû¶ó°¡´Â µ¥ ¹æÇعÞÀ» ÀÏÀº ¾ø´Ù. ±×¸®°í Ȥ½Ã À½¾Ç°ú ¼öÇÐ ¸ðµÎ¿¡ ±íÀº °ü½ÉÀ» °¡Áø µ¶ÀÚ¶ó¸é ¹ãÀáÀ» ¼³Ä¡¸é¼­ ÀÐ°Ô µÉ·±Áöµµ ¸ð¸£°Ú´Ù.

ÇÑÆí 20 ¼¼±â¿¡ È°¾àÇÑ, ±×·¯³ª º°·Î ³Î¸® ¾Ë·ÁÁöÁö ¾ÊÀº È­°¡ÀÎ ¿¡¼Å´Â ¿µ¿øÈ÷ ²À´ë±â¿¡ ¿Ã¶ó¼³ ¼ö ¾ø´Â °è´ÜÀ̶óµçÁö °¨»óÀÚ°¡ ±×¸²ÀÇ ÀϺΰ¡ µÇ°í ÀÖ´Â ±×¸², ¶Ç µÎ ¼ÕÀÌ ¼­·Î »ó´ë¹æÀ» ±×¸®°í ÀÖ´Â ¸ð½À µîµî ¸Å¿ì ÀÚ±âÁö½ÃÀû (self-referring) ÀÎ ±×¸²µéÀ» ±×¸®°í ÀÖ´Ù. ±×ÀÇ ±×¸² Áß¿¡´Â ¾î¶² ÇüÅ (¿¹ÄÁ´ë »õµéÀÇ ¸ð¾ç) ¸¦ ±×¸®µÇ ±× ¹è°æµµ ¶ÇÇÑ °°Àº ÇüŸ¦ ÀÌ·ç´Â ±â¹¦ÇÑ ÀÛÇ°µéµµ ¿©·µ Àִµ¥, ÀÌ·± ÀÛÇ°µéÀº 'ÇüÅ (figure) ¿Í ¹è°æ (ground)' ÀÇ ±¸º°¿¡ ´ëÇÑ µµÀüÀ̶ó ÇÒ ¸¸ÇÑ °ÍÀ¸·Î ¹è°æÀÌ µ¿½Ã¿¡ ÇüÅ°¡ µÈ´Ù´Â Á¡¿¡¼­ 'ȸ±ÍÀû' À̶ó´Â °³³äÀÇ Á¤ÀÇ¿¡ Àß µé¾î¸Â´Â´Ù. È£ÇÁ½ºÅÂÅÍ´Â ¿¡¼ÅÀÇ ÀÛÇ°µéÀ» È­º¸ (ºñ·Ï Èæ¹éÀ̱ä ÇÏÁö¸¸) ¿Í ÇÔ²² ¼³¸íÇÏ°í ÀÖ´Ù. ÀλóÆÄ ÀÌÈÄÀÇ Çö´ë ȸȭ¿¡ ´ëÇؼ­ ¿Ïº®ÇÑ ±î¸·´«ÀÎ ÇÊÀÚÁ¶Â÷µµ ¿¡¼ÅÀÇ ±×¸²µéÀ» °¨»óÇÏ´Â µ¥ ¾Æ¹«·± ¹®Á¦°¡ ¾ø¾ú´Ù.

Àرâ Àü¿¡ ²À ¾Ë·Áµå·Á¾ß ÇÒ °ÍÀº ÀÌ Ã¥ÀÇ °¢ Àå »çÀÌ¿¡ ¾Æų·¹½º¿Í °ÅºÏÀÌÀÇ ±ä ´ëÈ­°¡ ³¢¿© ÀÖ´Ù´Â Á¡ÀÌ´Ù. ¹Ù·Î ÀÌ Á¡ ¶§¹®¿¡ È£ÇÁ½ºÅÂÅÍ´Â  " ·çÀ̽º ij·²ÀÇ Á¤½Å¿¡ ÀÔ°¢Çؼ­ ¾²¿©Áø¡¦¡¦ " À̶ó´Â ±¸ÀýÀ» ºÎÁ¦¿¡ ³ÖÀº °ÍÀ̶ó°í º¸¿©Áö´Âµ¥ ÀÌ ´ëÈ­°¡ Âü Àç¹ÌÀÖ´Ù. ´Ù ¾Æ½Ã°ÚÁö¸¸ ij·² (L. Carroll) Àº 19 ¼¼±âÀÇ ³í¸®ÇÐÀÚÀε¥ ¡¶ÀÌ»óÇÑ ³ª¶óÀÇ ¾Ù¸®½º¡·ÀÇ ÀúÀÚ·Î ³Î¸® ¾Ë·ÁÁø »ç¶÷ÀÌ´Ù. ij·²Àº ¿îµ¿À» ºÎÁ¤Çß´ø °í´ë ±×¸®½ºÀÇ Ã¶ÇÐÀÚ 'Á¦³í (Zenon) ÀÇ ¿ª¼³' ÀÇ ±× ¾Æų·¹½º¿Í °ÅºÏÀ̸¦ µîÀå½ÃÄѼ­ ´ëÈ­ÁýÀ» ³Â´Ù°í Çϴµ¥, È£ÇÁ½ºÅÂÅÍ´Â ´Ù½Ã ij·²À» Èä³»³»¾î ÀÌ Ã¥¿¡¼­ ´Ù·ç°í ÀÖ´Â ¿©·¯ °¡Áö ¹®Á¬°Å¸®µé¿¡ ´ëÇÏ¿© ¾Æų·¹½º¿Í °ÅºÏÀÌ°¡ ³ª´©´Â ´ëÈ­¸¦ °¢Àå »çÀÌ¿¡ ¿«¾î ³Ö°í ÀÖ´Ù. ÀÌ ¸·°£ÀÇ ´ëÈ­µéÀº ±×³É ¾ç³äÀÌ ¾Æ´Ï´Ù. ´ëºÎºÐ ´ÙÀ½ Àå¿¡¼­ ¼³¸íÇÒ ÁÖÁ¦¸¦ ³õ°í ¹úÀÌ´Â Åä·ÐÀ¸·Î µÇ¾î ÀÖÀ¸¸ç ¶§·Î´Â ÀÌ ´ëÈ­¸¦ ÀÐÁö ¾Ê°í´Â ´ÙÀ½ ÀåÀÇ ¼³¸íÀ» µû¶ó°¡±â ¾î·Á¿î °æ¿ìµµ ÀÖ´Ù. »ç½Ç ÀÌ Ã¥ÀÌ ÀÌ·¸°Ô µÎ²¨¿öÁø °ÍÀº ´ëÈ­µé Å¿À̱ä ÇÏÁö¸¸ ÀÌ ´ëÈ­µéÀº Çϳª°°ÀÌ È£ÇÁ½ºÅÂÅÍÀÇ Àç±â¿Í ±âÁö°¡ µÎµå·¯Áö´Â Àß Â¥¿©Áø °ÍµéÀÌ´Ù (ÀÌ ´ëÈ­ Áß ¸î °³´Â ½ÇÁ¦·Î ij·²ÀÇ ÀÛÇ°À̶ó°í ±×´Â ¹àÈ÷°í ÀÖ´Ù).

¥². ¾î¶µç ¾Õ¼­ ¸»ÇßµíÀÌ ÀÌ Ã¥ÀÇ ÁÖµÈ ÁÖÁ¦´Â ±«µ¨ Á¤¸®¶ó°í ÇÒ ¼ö ÀÖÀ¸¹Ç·Î ÀÌ Ã¥ÀÌ °ú¿¬ ¾î¶² Ã¥ÀÎÁö ¸Àº¸±â »ï¾Æ¼­ ³í¸®ÇÐÀÇ ¾ê±â¸¦ Çغ¸±â·Î ÇÏÀÚ. ±«µ¨ Á¤¸®¿Í ¹ÙÈåÀÇ ÀÛÇ°, ±×¸®°í ¿¡¼ÅÀÇ ±×¸²¿¡¼­ °øÅëÀûÀ¸·Î ãÀ» ¼ö ÀÖ´Â ¿ä¼Ò·Î ÀúÀÚ°¡ ²Å°í ÀÖ´Â °ÍÀº ´ëü·Î µÎ °¡Áö·Î ¸»ÇÒ ¼ö ÀÖ´Ù. ù°´Â ÀÚ±âÁö½Ã (self-reference) ¿ä, µÑ°´Â ȸ±Í (recursion) Àε¥, ¹°·Ð ÀÌ µÎ °¡Áö°¡ ¹«°üÇÑ °ÍÀÌ ¾Æ´Ï´Ù. ÀÌ Áß¿¡¼­ ÀÚ±âÁö½Ã´Â ¾Ë·ÁÁø Áö ²Ï ¿À·¡µÈ °ÍÀ̾ ±× ´ëÇ¥ÀûÀÎ ¿¹°¡ ¼º°æ¿¡µµ ±â·ÏµÇ¾î ÀÖ´Ù. ±×°ÍÀÌ ¹Ù·Î '°ÅÁþ¸»ÀïÀÌ ¿ª¼³ (liar paradox) 'À̶ó´Â °ÍÀÌ´Ù. ¿¹¸¦ µé¾î¼­ ´ÙÀ½ ¹®ÀåÀ» Çѹø »ý°¢Çغ¸ÀÚ.

(L) LÀº °ÅÁþÀÌ´Ù.

¸¸ÀÏ ÀÌ ¹®ÀåÀÌ ÂüÀ̶ó¸é ÀÌ ¹®ÀåÀº °ÅÁþÀÏ °ÍÀÌ´Ù. ¶Ç ¸¸ÀÏ ÀÌ ¹®ÀåÀÌ °ÅÁþÀ̶ó¸é ÀÌ ¹®ÀåÀº ÂüÀÌ µÈ´Ù. ±×·¯´Ï ¿ª¼³ÀÌ µÈ´Ù. µµ´ëü ÀÌ°Ô ¿Ö ¹®Á¦°¡ µÇ³ª? ¶Ç ÀÌ·± ÀÏÀÌ ¿Ö ¹ß»ýÇϴ°¡? ÀÌ°ÍÀº ±×¸® ´äÇϱ⠽¬¿î ¹®Á¦°¡ ¾Æ´Ï´Ù. ´ëÃæ ¸»ÇÑ´Ù¸é, ¸¹Àº »ç¶÷µéÀº ÀÌ·± ¿ª¼³Àº ¿ì¸®ÀÇ ¾ð¾î°¡ ³Ê¹« dzºÎÇؼ­ ¸» ÀÚü¿¡ ´ëÇؼ­ ¸»ÇÏ´Â ÀåÄ¡±îÁöµµ °¡Á³±â ¶§¹®¿¡ ¹ß»ýÇÑ´Ù°í »ý°¢ÇÑ´Ù. "¼­¿ïÀº Å« µµ½Ã´Ù" ¿¡¼­ '¼­¿ï' Àº ¼­¿ïÀ̶ó´Â µµ½Ã¸¦ °¡¸®Å²´Ù. ±×·¯³ª "¼­¿ïÀº µÎ ±ÛÀÚ´Ù" ¿¡¼­ '¼­¿ï' Àº '¼­¿ï' À̶ó´Â ¸» ÀÚü¸¦ °¡¸®Å²´Ù. ¿ì¸®´Â ÀÌ·¯ÇÑ È¥µ¿À» ÇÇÇϱâ À§Çؼ­ ¾î¶² ¸»ÀÌ ±× ¸» ÀÚü¸¦ °¡¸®Å³ ¶§ ¾ÕµÚ¿¡ ÀÛÀº µû¿ÈÇ¥¸¦ ÇÑ´Ù. ±×·¯´Ï±î Á¤È®ÇÏ°Ô ¾²¸é  " '¼­¿ï' Àº µÎ ±ÛÀÚ´Ù" ¶ó°í ÇØ¾ß ¿Ç´Ù. µµ½Ã¸¦ °¡¸®Å°´Â ¸»ÀÌ ÀÖ°í, ¶Ç ±× ¸»À» °¡¸®Å°´Â ¸»ÀÌ ÀÖÀ¸´Ï ÀÌ°ÍÀ» ºÐ¸íÈ÷ ±¸º°ÇØ¾ß ÇÑ´Ù. Ÿ¸£½ºÅ° (A. Tarski) ¶ó´Â Æú·£µåÀÇ ³í¸®ÇÐÀÚ´Â ÀüÀÚ¸¦ ´ë»ó¾ð¾î (object language), ÈÄÀÚ¸¦ ¸ÞŸ¾ð¾î (metalanguage) ¶ó°í ±¸º°ÇÏ¿© °ÅÁþ¸»ÀïÀÌ ¿ª¼³À» ÇÇÇϴ ü°èÀûÀÎ ¹æ½ÄÀ» ¼¼¿ì·Á°í Çß´Ù. ±×¸®°í ³î¶ø°Ôµµ ±«µ¨°ú ºñ½ÁÇÑ °á·Ð¿¡ µµ´ÞÇÏ°í ÀÖ´Ù.

°ÅÁþ¸»ÀïÀÌ ¿ª¼³ÀÌ ¹®Á¦°¡ µÇ´Â °ÍÀº ¿ì¸®ÀÇ À̼ºÀÌ ¸ð¼øÀ» ¿ë³³ÇÒ ¼ö ¾ø±â ¶§¹®ÀÌ´Ù. ¿ì¸® »çȸ°¡ ¸ð¼øÅõ¼ºÀ̶ó´À´Ï ¸ð¼ø±îÁöµµ Æ÷¿ëÇÒ ¼ö ÀÖ¾î¾ß ÇÏÁö ¾Ê´À³Ä´À´Ï ÇÏ´Â ¸»µéÀ» °¡²û µéÀ» ¼ö Àִµ¥, ¿ÀÇØ°¡ ÀÖÀ»±îºÁ »çÁ·À» ºÙÀÌÀÚ¸é, ¿©±â¼­ ¿ë³³ÇÒ ¼ö ¾ø´Â ¸ð¼øÀ̶õ °ÍÀº ±×·± °Ô ¾Æ´Ï´Ù. °¡Áø ÀÚµé°ú ¸ø°¡Áø Àڵ鰣ÀÇ °¥µî°ú ´ë¸³µµ ¸ð¼øÀ̶ó¸é ¸ð¼øÀÌ°í, ¶Ç ¾Æ³»·Î¼­ ±ú²ýÇÏ°í ¾Æ¸§´ä°Ô ²Ù¹Ì°í Áö³»¾ß Çϸ鼭 µ¿½Ã¿¡ ¾ö¸¶·Î¼­ Áý¾ÈÀÇ ¿Â°® Çãµå·¿ÀÏÀ» µµ¸Ã¾Æ¾ß ÇÏ´Â Áֺεµ ¸ð¼øµÈ ±â´ë¿ªÇÒÀ» ¾È°í »ì¾Æ¾ß ÇÑ´Ù°í ¸»ÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª ³í¸®Çп¡¼­ ¸»ÇÏ´Â ¸ð¼øÀ̶õ 'pÀ̸鼭 µ¿½Ã¿¡ p°¡ ¾Æ´Ï´Ù' ó·³ ¾î¶°ÇÑ °æ¿ì¿¡µµ ÂüÀÌ µÉ ¼ö ¾ø´Â ¹®ÀåÀÌ ¹üÇÏ´Â À߸øÀÌ¿ä, '°áÈ¥ÇÑ ÃÑ°¢' ó·³ ¼öÆÛ¸ÇÀ̳ª Çϳª´ÔÁ¶Â÷µµ ¸¸µé¾î³¾ ¼ö ¾ø´Â ´ë»óÀ» °¡¸®Å°´Â °³³äÀÌ ¹üÇÏ´Â À߸øÀÌ´Ù. ¸¸ÀÏ ¾î¶² »ý°¢ÀÌ ¸ð¼øÀ» ´ã°í ÀÖ´Ù¸é ±×°ÍÀº ¾î¶² ¼¼°è¿¡¼­µµ ÂüÀÏ ¼ö°¡ ¾ø´Ù. ±×·¯´Ï Áø¸®ÀÇ Ã¼°è¸¦ ¼¼¿ì·Á´Â ¸¶´ç¿¡ ¸ð¼øÀÇ ¹ß»ýÀº Å« ¹®Á¦°¡ ¾Æ´Ò ¼ö ¾ø´Ù.

±«µ¨Àº »ê¼ö¸¦ Á¤½ÄÈ­ÇÒ ¼ö ÀÖ´Â Á¤µµ ÀÌ»óÀÇ Ç³ºÎÇÑ ¾ð¾î·Î °ÅÁþ¸»ÀïÀÌ ¿ª¼³À» ÀÏÀ¸Å² À§ÀÇ ¿¹¹®°ú °°Àº ±¸Á¶¸¦ °¡Áø ¹®ÀåÀ» ¸¸µå´Â ¹æ¹ýÀ» °í¾ÈÇس´٠(È£ÇÁ½ºÅÂÅÍÀÇ Ã¥¿¡ ÀÌ ¹æ¹ýÀÌ ÀÚ¼¼È÷ ¼³¸íµÇ¾î ÀÖ´Ù). ±«µ¨ÀÇ ¹®ÀåÀº

(G)  G´Â Áõ¸íµÉ ¼ö ¾ø´Ù.

¶ó´Â Áø¸®ÀÎ ¹®ÀåÀÌ´Ù (¸¸ÀÏ G°¡ °ÅÁþÀ̶ó¸é ¾î¶»°Ô µÉ±î? Çѹø »ý°¢ÇØ º¸ÀÚ). ÀÌ ¹®ÀåÀÌ ÂüÀ̹ǷΠ¸¸ÀÏ ¾î¶² ü°è°¡ G¸¦ Áõ¸íÇÒ ¸¸Å­ °­ÇÏ´Ù¸é, Áï G¸¦ Á¤¸®·Î °¡Áú Á¤µµ·Î °­ÇÏ´Ù¸é ±× Ã¼°è´Â ¸ð¼ø¿¡ ºüÁö°Ô µÈ´Ù. °Å²Ù·Î ¸¸ÀÏ ¾î¶² ü°è°¡ Á¤ÇÕÀûÀ̶ó¸é, Áï ¸ð¼øÀ» ÇÔÃàÇÏÁö ¾Ê´Â´Ù¸é ±× ü°è¿¡¼­ G´Â Áõ¸íµÉ ¼ö ¾ø´Ù. ±×·±µ¥ G´Â ÂüÀÎ ¹®ÀåÀ̹ǷΠ±× ü°è´Â ÂüÀÎ ¹®ÀåÀ» Áõ¸íÇÏÁö ¸øÇÏ´Â ¼ÀÀÌ´Ù. Áï ¸ð¼ø ¾ø´Â ü°è¶ó¸é ±×°ÍÀº ¿ÏÀüÇÒ ¼ö ¾ø´Ù. ÂüÀ»¼º ÀÖ°Ô Àо°¡´Â µ¶ÀÚ¶ó¸é È£ÇÁ½ºÅÂÅÍ°¡ ±«µ¨ Á¤¸®ÀÇ Àü¸ð¸¦ Ãæ½ÇÇÏ°Ô ±×¸®°í ¾Ë¾ÆµéÀ» ¼ö ÀÖ°Ô ¼³¸íÇÏ°í ÀÖÀ½À» ¹ß°ßÇÏ°Ô µÉ °ÍÀÌ´Ù. ¹°·Ð ¿©±â±îÁö µµ´ÞÇÏ·Á¸é ÀÌ Ã¥À» °ÅÀÇ ´Ù Àоî¾ß ÇÑ´Ù.

ÀÌÁ¦ ȸ±Í¶ó´Â °³³ä¿¡ ´ëÇؼ­ ¸»ÇÒ Â÷·Ê°¡ µÇ¾ú´Ù. ³í¸®Çп¡¼­ ȸ±Í¶ó´Â ¸»Àº ²Ï ³¸¼³°Ô µé¸±Áö ¸ð¸£Áö¸¸ »ç½Ç °£´ÜÇÑ È¸±ÍÇÔ¼ö´Â °íµîÇб³ ¶§  ¼öÇн𣿡 ¹è¿î °ÍÀÌ´Ù. ´ëºÎºÐÀÇ »ç¶÷µéÀº A1 = 1, An+1 = 2An + n (n ¡à 0) ¶ó´Â ½ÄÀ¸·Î ÁÖ¾îÁö´Â ¼ö¿­ÀÇ Ç¥±â¹ýÀ» º» ±â¾ïÀÌ ÀÖÀ» °ÍÀÌ´Ù. ÀÌ°Í¿¡ Á¡È­½ÄÀ̶ó´Â À̸§ÀÌ ºÙ¾î ÀÖÁö ¾Ê¾Ò´ø°¡? Á¡È­½ÄÀÌ ¹Ù·Î °£´ÜÇÑ È¸±ÍÇÔ¼öÀÌ´Ù. ´ç½Ã¿¡ ¼öÇÐ ¼±»ý´ÔµéÀÌ ÀÌ°É °¡Áö°í °ñÄ¡ ¾ÆÇ ¹®Á¦µéÀ» ³»°ï Çß´Ù. ½ÇÁ¦·Î À§ÀÇ ½Ä´ë·Î ÀÚ¿¬¼ö¸¦ ã¾Æ¼­ Â÷·Ê·Î ½á³ª°¡´Â °Ç ¹«ÁöÇÏ°Ô ½±´Ù. 1, 3, 8, 19, 42, 89, ¡¦¡¦ ¹¹ ÀÌ·¸°Ô ³ª°¡´Â ¼ö¿­ ¾Æ´Ñ°¡? ÀÌ ¼ö¿­ÀÇ Ç×ÀÌ µÇ´Â ÀÚ¿¬¼öµéÀÇ °è¿­À» S¶ó°í ÇÏÀÚ. ±×·¯¸é S´Â ȸ±ÍÀûÀ¸·Î °è»ê°¡´ÉÇÑ ÁýÇÕ (recursively enumerable set) ÀÌ µÈ´Ù (¿©±â¿¡ ´ëÇؼ­µµ Á¦´ë·Î µÈ ¼³¸íÀ» º¸·Á¸é Ã¥À» Á÷Á¢ ÀÐÀ¸½Ã¶ó). ÀÓÀÇÀÇ ÀÚ¿¬¼ö°¡ ÁÖ¾îÁ³À» ¶§ ±× ¼ö°¡ S¿¡ ¼ÓÇÏ´ÂÁö ¾È ¼ÓÇÏ´ÂÁö ¾Ë ¼ö°¡ ÀÖÀ»±î? ¹°·Ð ¾Ë ¼ö ÀÖ´Ù. À§ÀÇ ¼ö¿­Àº ÀÛÀº ¼öºÎÅÍ ½ÃÀÛÇؼ­ Â÷·Ê·Î Ä¿Áø´Ù. ±×·¯´Ï±î À§ÀÇ ¼ö¿­À» °è¼Ó À̾¼­ ¹®Á¦ÀÇ ¼ö°¡ ¾ò¾îÁö´ÂÁö ¾Æ´Ï¸é ±×³É ³Ñ¾î°¡´ÂÁö ¾Ë¾Æº¼ ¼ö ÀÖ´Ù. ¹®Á¦ÀÇ ¼ö°¡ ¸Å¿ì Å« ¼ö¶ó¸é ÀÌ°Ç ¸Å¿ì Áö°Ü¿î ÀÏÀÌ°Ú´Ù. ±×·¯³ª ¾î¶µç ¾î¶² ¼ö°¡ S¿¡ ¼ÓÇÏ´ÂÁö ¾Æ´ÑÁö´Â ºÐ¸íÇÏ°Ô °áÁ¤µÈ´Ù. ÀÌ·¯ÇÑ ¹®Á¦°¡ ¹Ù·Î °áÁ¤°úÁ¤ (decision procedure) À» °®´Â ¹®Á¦´Ù.

±×·¯¸é ¼Ò¼ö (prime number : 1 °ú ÀÚ±âÀڽŠÀÌ¿ÜÀÇ ¾à¼ö¸¦ °®Áö ¾Ê´Â ¼ö) ÀÇ °è¿­Àº ¾î¶³±î? ÁÖ¾îÁø ¼ö°¡ ¼Ò¼öÀΰ¡ ¾Æ´Ñ°¡ ÇÏ´Â ¹®Á¦´Â °áÁ¤°úÁ¤À» °®´Â´Ù. ±× ¼ö¸¦ 2 ·Î ³ª´©¾îº¸°í, 3 À¸·Î ³ª´©¾îº¸°í, 4 ·Î, ¡¦¡¦ ÀÌ·¸°Ô ±× ¼ö¿¡ À̸£±â±îÁö Â÷·Ê·Î Çغ¸¸é µÉ Å×´Ï±î ¸»ÀÌ´Ù. ±×·±µ¥ ¸ðµç ¼Ò¼ö¸¦ ºü¶ß¸®Áö ¾Ê°í ã¾Æ³»´Â Á¡È­½Ä (ȸ±ÍÇÔ¼ö) À» ãÀ» ¼ö ÀÖÀ»±î? ÀÌ°Ç Á» ¸¸¸¸Ä¡ ¾ÊÀ» °Í °°´Ù. ±×¸®°í ÀÌ°ÍÀÌ ¸¶·Î È£ÇÁ½ºÅÂÅÍ°¡ ¾ê±ê°Å¸®·Î »ïÀº ¹®Á¦°¡. ÀÌ ¹®Á¦¿¡ ´ëÇÑ ´äÀÌ ±Ã±ÝÇÏ´Ù¸é ÀÌ Ã¥ÀÇ 3 Àå±îÁö¸¸ ÀÐÀ¸¸é µÈ´Ù.

½ÇÁ¦·Î ³í¸®Çаú ¼öÇп¡¼­ ȸ±ÍÁýÇÕÀÇ °³³äÀº ³í¸®ÀûÀÎ Ã߸® ¶Ç´Â ¼öÇÐÀûÀÎ ¿¬»êµéÀ» ÄÄÇ»ÅÍÈ­ÇÏ´Â µ¥ °áÁ¤ÀûÀ¸·Î Áß¿äÇÑ ¿ªÇÒÀ» ÇÑ´Ù. ¿¹¸¦µé¾î ³»°¡ º°´Þ¸® ÇÒ ÀÏÀÌ ¾ø¾î¼­ ½É½ÉÇ®ÀÌ·Î Á¾ÀÌ¿¡ a, b, c ¶ó´Â ¼¼ ±ÛÀڷθ¸ ÀÌ·ç¾îÁø ³ª¿­À» Çϳª °ñ¶ó¼­

abccac

¶ó°í ¾²°í¼­ Á¦ÀÏ ¿ÞÂÊ¿¡ a°¡ ÀÖ´Â °ÍÀ» º¸°í ÀÌ ³ª¿­ÀÇ ¿À¸¥Æí ³¡¿¡ bab¶ó´Â ³ª¿­À» µ¡ºÙÀÌ°í ¿ÞÆí¿¡¼­ ¼¼ ±ÛÀÚ¸¦ Áö¿ü´Ù°í ÇÏÀÚ. ±×·¡¼­ ³ª´Â

cacbab

¶ó´Â ³ª¿­À» ¾ò´Â´Ù. ÀÌ ³ª¿­Àº b·Î ½ÃÀÛÇÏ´Â °ÍÀ» º¸°í ÀÌ ¶§¿¡´Â ¿À¸¥Æí¿¡ cab¸¦ ºÙÀÌ°í ¿ÞÆí¿¡ ¼¼ ±ÛÀÚ¸¦ Áö¿ö¼­

babcab

¶ó´Â ³ª¿­À» ¾ò´Â´Ù. ÀÌÁ¦ ÀÌ ³ª¿­Àº b·Î ½ÃÀÛÇÏ´Â °ÍÀ» º¸°í ÀÌ ¶§¿¡´Â ¿À¸¥Æí¿¡ abba¸¦ ´õÇÏ°í ¿ÞÆí¿¡ ¼¼ ±ÛÀÚ¸¦ Áö¿ö¼­

cababba

¸¦ ¾ò´Â´Ù. ¾ò¾îÁø ³ª¿­ÀÌ a·Î ½ÃÀÛÇÒ ¶§¿¡´Â ¾ðÁ¦³ª ¿ÞÆíÀÇ ¼¼ ±ÛÀÚ¸¦ Áö¿ì¸é¼­ ¿À¸¥Æí ³¡¿¡ bab¸¦ ºÙÀÌ°í, b·Î ½ÃÀÛÇÒ ¶§¿¡´Â ¾ðÁ¦³ª ¿ÞÆíÀÇ ¼¼ ±ÛÀÚ¸¦ Áö¿ì¸é¼­ ¿À¸¥Æí ³¡¿¡ abba¸¦ ºÙÀÌ°í, c·Î ½ÃÀÛÇÒ ¶§¿¡´Â ¾ðÁ¦³ª ¿ÞÆí¿¡ ¼¼ ±ÛÀÚ¸¦ Áö¿ì¸é¼­ cab¸¦ ºÙÀÌ°í, ÀÌ·¸°Ô ÀÌ ÀÏÀ» °è¼ÓÇÑ´Ù¸é ³ª´Â ´ÙÀ½°ú °°Àº ³ª¿­µéÀ» Â÷·Ê·Î ¾ò°Ô µÉ °ÍÀÌ´Ù.

    abbacab

      acabbab

        bbabbab

          bbababba

            babbaabba

                ¤ý

                  ¤ý

                    ¤ý

³»°¡ óÀ½¿¡ ¾´ ³ª¿­ºÎÅÍ °è¼ÓÇÏ¿© ¾ò¾îÁø ³ª¿­µéÀÇ ÁýÇÕÀº ¾Õ¼­ ¸»ÇÑ È¸±ÍÀûÀ¸·Î °è»ê°¡´ÉÇÑ ÁýÇÕÀ» ÀÌ·é´Ù. ±×·±µ¥ ÀÌ·¸°Ô ´ÙÀ½ ³ª¿­À» ¾ò´Â ÀÏÀ» °è¼ÓÇÑ´Ù¸é ¾î¶»°Ô µÉ±î? (1) »õ·Î ¾ò´Â ³ª¿­ÀÌ ÀÌÀü¿¡ ¾òÀº ³ª¿­°ú ¶È°°¾ÆÁ®¼­ ¼øȯÇÏ´Â ³ª¿­ÀÇ °í¸®¿Í ¸¸³ª°Å³ª, ¶Ç´Â (2) °á±¹¿¡´Â ³ª¿­ÀÌ Á¡Á¡ ª¾ÆÁ®¼­ ¾ø¾îÁö°Å³ª, ¶Ç´Â (3) ¹«ÇÑÁ¤ »õ·Î¿î ³ª¿­µéÀ» ¾òÀ¸¸é¼­ °è¼ÓµÇ°Å³ª, ÀÌ ¼Â ÁßÀÇ ÇÑ °¡Áö °æ¿ì¿¡ ¼ÓÇÏ°Ô µÉ °ÍÀÌ´Ù.

ÀÌ °ÔÀÓ(?)Àº Æ÷½ºÆ® (E. Post) ÀÇ 'µ¡ºÙÀ̱â ü°è (Tag system)'2)   ¶ó°í ¾Ë·ÁÁø °ÍÀε¥ ÀÌ ¿¹¸¸ °®°íµµ ¿ì¸®´Â '±â°èÀû °úÁ¤' ¿¡ ´ëÇؼ­ Áß¿äÇÑ °³³äµéÀ» ´Ù ¾ò¾î³¾ ¼ö ÀÖ´Ù. À¯ÇÑ °³ÀÇ ±âÈ£µéÀÇ ÁýÇÕ { a1 ¡¦¡¦ am} (¿ì¸®ÀÇ ¿¹¿¡¼­´Â { a, b, c}) ; À¯ÇÑ °³ÀÇ ¼ø¼­½ÖÀÇ ÁýÇÕ { (a1, A1) , ¡¦¡¦ (am, Am) } (¿ì¸®ÀÇ ¿¹¿¡¼­´Â { (a, bab), (b, abba), (c, cab)}) ; ÇϳªÀÇ Á¤¼ö n (¿ì¸®ÀÇ ¿¹¿¡¼­´Â n = 3) ; ±×¸®°í óÀ½¿¡ ÁÖ¾îÁö´Â ÇϳªÀÇ ³ª¿­ A0 (¿ì¸®ÀÇ ¿¹¿¡¼­´Â abccac) °¡ ÁÖ¾îÁö¸é ÇϳªÀÇ µ¡ºÙÀ̱â ü°è°¡ °áÁ¤µÈ´Ù. ÀÌ Ã¼°è¿¡¼­ ³ª¿­À» ¾ò¾î³»´Â ±ÔÄ¢Àº ´ÙÀ½°ú °°ÀÌ ÁÖ¾îÁø´Ù.



    (±ÔÄ¢0) A0 ¸¦ ÁýÇÕ W ·Î ÀâÀ¸¶ó. (±ÔÄ¢1) ·Î °¡¶ó.

    (±ÔÄ¢1) W ¸¦ '¸ñ·Ï' ¿¡ ÀúÀåÇ϶ó. ÀÌÁ¦ W ÀÇ Á¦ÀÏ ¿ÞÆí ±âÈ£°¡ a1À̸é W ÀÇ ¿À¸¥Æí ³¡¿¡ A1 À» µ¡ºÙÀ̸鼭 ¿ÞÆíÀÇ ¼¼ ±âÈ£¸¦ Áö¿ì¶ó. ÀÌ·¸°Ô Çؼ­ ¾ò¾îÁø °á°ú¸¦ W ·Î »ïÀ¸¶ó.

    (±ÔÄ¢2) ¸¸ÀÏ W °¡ °øÁýÇÕÀ̸é, Áï ¸ðµç °ÍÀÌ ´Ù Áö¿öÁö¸é, (±ÔÄ¢3) À¸·Î °¡¶ó. ±×·¸Áö ¾ÊÀ¸¸é W °¡ '¸ñ·Ï' ÀÇ ¾î¶² Ç×°ú °°ÀºÁö °Ë»çÇ϶ó. ¸¸ÀÏ °°Àº Ç×ÀÌ ¹ß°ßµÇ¸é (±ÔÄ¢3) À¸·Î °¡¶ó. °°Àº Ç×ÀÌ ¹ß°ßµÇÁö ¾ÊÀ¸¸é (±ÔÄ¢1) ·Î °¡¶ó.

    (±ÔÄ¢3) ¸ØÃ߶ó.



(±ÔÄ¢3) ÀÌ Àû¿ëµÇ¸é ±× ü°è´Â ¸ØÃß°Ô µÈ´Ù. ¿¹¸¦ µé¾î¼­ {a, b, c}, {(a, bab), (b, abba), (c, ca)}, n = 3, A0 = cabcba ·Î ÁÖ¾îÁö´Â ü°è´Â °°Àº ³ª¿­À» ¾ò¾î¼­ ¸ØÃß°Ô µÈ´Ù. ¶Ç {a, b, c}, {(a, cac), (b. bab), (c, ca)} n = 3, A0 = cabcba ·Î ÁÖ¾îÁö´Â ü°è´Â ¸ðµç ±âÈ£°¡ Áö¿öÁ®¼­ ¸ØÃß°Ô µÈ´Ù. ÀÌ°Ç ±æÁö ¾ÊÀ¸´Ï±î ¾à 5 ºÐÀÌ¸é °¢ÀÚ È®ÀÎÇغ¼ ¼ö ÀÖ´Ù.

ÇϳªÀÇ µ¡ºÙÀ̱â ü°è°¡ ÁÖ¾îÁö¸é ¾î¸¥ÀÌµç ¾ÆÀÌµç ±â°èµç ±× ü°è°¡ ¸ØÃß´ÂÁö ¾Æ´ÑÁö¸¦ ¾Ë¾Æº¸·Á°í ¸î ½Ã°£ÀÌ°í ¸î ÁÖ°£ÀÌ°í µ¡ºÙÀ̱⠰ÔÀÓÀ» ÇÒ ¼ö°¡ ÀÖ´Ù. ±×·¯¹Ç·Î µ¡ºÙÀ̱â ü°è´Â ±â°èÀûÀ¸·Î °è»êµÉ ¼ö Àִ ü°è´Ù. ±ÔÄ¢ÀÇ Àû¿ë¿¡ À־ ¾Ö¸ÅÇÑ ±¸¼®µµ ¾ø°í ¾î¶² âÁ¶ÀûÀÎ Á÷°üÀÌ °³ÀÔÇÒ ¿©Áöµµ ¾ø´Â °ÍÀÌ´Ù. ÀÌ°ÍÀÌ ¹Ù·Î '±â°èÀû °úÁ¤' ÀÇ ÇÙ½ÉÀÌ µÈ´Ù. 'È¿À²Àû °úÁ¤ (effective procedure)' À̶ó°í ºÒ¸®±âµµ ÇÏ´Â ±â°èÀû °úÁ¤Àº À¯ÇÑ °³ÀÇ ±âÈ£µéÀ» Àаí, ¾²°í, ÀúÀåÇÏ°í, Áö¿ì°í, µÎ ±âÈ£°¡ ¼­·Î °°ÀºÁö °Ë»çÇÏ´Â Àϸ¸À¸·Î ¼öÇàµÉ ¼ö ÀÖ´Â °úÁ¤ÀÌ´Ù (±â°èÀû °è»ê°úÁ¤ÀÌ °ú¿¬ ¹«¾ùÀÎÁö Á¤È®ÇÏ°Ô Á¤½ÄÈ­Çϱâ´Â ¾î·Æ´Ù. ÀÌ¿¡ ´ëÇؼ­´Â ¿©·¯ ³í¸®ÇÐÀÚ ³ª¸§´ë·Î ±ÔÁ¤Áö¾ú´Âµ¥ À̵éÀÇ ±ÔÁ¤ÀÌ ½ÇÁ¦·Î µ¿µîÇÏ´Ù´Â °ÍÀÌ ¹àÇôÁ® ÀÖ´Ù. »ç¶÷µéÀº ÀÌ Á¡À» µé¾î¼­ '±â°èÀû °úÁ¤' À» Á¤È®ÇÑ Á¤ÀÇ ¾øÀ̵µ ¹Þ¾ÆµéÀÏ ¸¸ÇÑ °³³äÀ̶ó°í ¿©±ä´Ù). ±×·±µ¥ ÁÖ¾îÁø µ¡ºÙÀ̱â ü°è°¡ ¸ØÃߴ°¡ ¾Æ´Ñ°¡¸¦ °áÁ¤ÇØÁÖ´Â °áÁ¤°úÁ¤Àº ÀÖÀ»±î? ÄÄÇ»ÅÍ¿¡°Ô ¾î¶² µ¡ºÙÀ̱â ü°è¸¦ ÁÖ°í¼­ ±×°ÍÀÌ ¸ØÃß´ÂÁö ¾Ë¾Æº¸µµ·Ï Çغ¸ÀÚ (»ç¶÷ÇÑÅ× ½ÃÅ°¸é ´©°¡ ÀÌ Áö·çÇÑ ÀÏÀ» ÇÏ·Á°í Çϰڴ°¡?). ¸¸ÀÏ ÀÌ Ã¼°è°¡ ¸ØÃá´Ù¸é ÄÄÇ»ÅÍ´Â ¸ØÃá´Ù°í ¾Ë¾Æ³¾ °ÍÀÌ´Ù. ±×·¯³ª ÀÌ Ã¼°è°¡ ¸ØÃßÁö ¾Ê´Â´Ù¸é ¾î¶²°¡? ÄÄÇ»ÅÍ´Â °è¼ÓÇؼ­ (°íÀ峯 ¶§±îÁö) ´ÙÀ½ ³ª¿­À» ¾ò¾î°¥ °ÍÀÌ´Ù. ÀÌ °æ¿ì¿¡ ¿ì¸®´Â ÀÌ Ã¼°è°¡ Á¶±Ý ´õ ÀÖ´Ù°¡ ¸ØÃâÁö °è¼Ó Çسª°¥Áö ¾Ë ¼ö°¡ ¾ø´Ù. ±×·¯¹Ç·Î '¾î¶² µ¡ºÙÀ̱â ü°è°¡ ¸ØÃߴ°¡' ÇÏ´Â ¹®Á¦´Â È¿À²ÀûÀÎ °áÁ¤°úÁ¤À» °®Áö ¾Ê´Â´Ù. Æ÷½ºÆ®°¡ Á¦½ÃÇÑ µ¡ºÙÀ̱â ü°è¿¡ ÀÌ·± °ÍÀÌ ÀÖ´Ù :

{ 0, 1 }, { (0, 00 ), (1, 1101 ) }, n = 3, A0 = 100100100100100100100.

ÀÌ Ã¼°è°¡ ¸ØÃâ±î ¾Æ´Ï¸é ¹«ÇÑÈ÷ °è¼ÓµÉ±î? ±Ã±ÝÇÏ´õ¶óµµ Çغ¸·Á°í ÇÏÁö ¸¶½Ã±æ ¡¦¡¦. ÀÌ Ã¼°è¿¡ ´ëÇÑ Á¶»ç°¡ »ç¶÷µéÀº ¹°·ÐÀÌ°í ÄÄÇ»ÅͱîÁö µ¿¿øµÇ¾î¼­ ÀÌ·ç¾îÁ³Áö¸¸ ¾ÆÁ÷µµ ÀÌ°ÍÀÌ ¸ØÃß´ÂÁö ¹«ÇÑÁ¤ °è¼ÓµÇ´ÂÁö ¾Ë·ÁÁöÁö ¾Ê°í ÀÖ´Ù [¼ö¹é ³â°£ ¾È Ç®¸®´ø Æ丣¸¶ÀÇ ¸¶Áö¸· Á¤¸® (Fermat's Last Theorem) µµ Áõ¸íÀÌ µÇ¾î¼­ ¼öÇÐÀÚµéÀÌ Áö±Ý °ËÁõÁßÀ̶ó´Âµ¥ ÀÌ°Ç ¿Ö ¾ÈÇ®¸±±î?].

ÀÌ¿Í ºñ½ÁÇÑ Çü½Äü°èµé·Î È£ÇÁ½ºÅÂÅÍ´Â MIU-ü°è, pq-ü°è, TNT-ü°è µîÀ» ¼Ò°³ÇÏ¿© ´Ù·ç°í Àִµ¥, À̸¦ ÅëÇÏ¿© Çü½Äü°è, ³ª¿­, Á¤¸®, °ø¸®, Ã߸®±ÔÄ¢, °áÁ¤°úÁ¤ µî ¼ö¸®³í¸®¿Í ȸ±ÍÀÌ·ÐÀÇ ±âº» °³³äµéÀ» ¾Ë±â ½±°Ô ¼³¸íÇÏ°í ÀÖÀ» »Ó ¾Æ´Ï¶ó °¡´ÉÇÒ ¶§¸¶´Ù ¹ÙÈåÀÇ À½¾Ç, ¿¡¼ÅÀÇ ¹Ì¼ú ÀÛÇ°µé¿¡¼­ ÀÌ·¯ÇÑ °³³äµé¿¡ ´ëÀÀÇÏ´Â ¿ä¼Ò¸¦ ²ôÁý¾î³½´Ù. ¾î¶² ºÎºÐÀº ºñÀ¯¿¡ ºÒ°úÇÑ °Í °°±âµµ ÇÏ°í ¾î¶² ºÎºÐÀº ¸Å¿ì Á¤È®ÇÑ °Í °°±âµµ Çѵ¥ À½¾Çµµ ¹Ì¼úµµ, °Ô´Ù°¡ ³í¸®Çеµ Àß ¸ð¸£´Â ÇÊÀÚ¿¡°Ô´Â ÀÌ Á¡ÀÌ ¸Å¿ì ¾î·Æ°í ºÒºÐ¸íÇÏ´Ù. ÀÌ Á¡ ¿©·¯ºÐ²²¼­ ÀÐÀ¸¸é¼­ ÆÇ´ÜÇØÁÖ½Ã±æ ¹Ù¶õ´Ù.

                     ÁÖ  

1) Haugeland, J., Artificial Intelligence : The Very Idea (Cambridge, MA : The MIT Press / A Bradford Book, 1985).

2) Post, E., "Formal reductions of the general combinatorial decision problems," (1943) in Davis, M., The Undecidable (New York :     Raven Press, 1965).



http://209.85.135.104/search?q=cache:h2jKVF2WEWEJ:www.aistudy.com/paper/culture/GEB_min.htm+%EC%9E%90%EA%B8%B0%EC%A7%80%EC%8B%9C+%EC%97%AD%EC%84%A4&hl=ko&ct=clnk&cd=5&gl=de



Backward Forward Post Reply List