Halting  problem

 

À¯ÇÑÇÑ ¼öÀÇ ´Ü°è ÈÄ¿¡ ƯÁ¤ÇÑ ÇÁ·Î±×·¥ÀÌ ¸ØÃâ °ÍÀ̶ó°í (¹®Á¦°¡ Ç®¸±°ÍÀ̶ó°í) ¿ì¸®¿¡°Ô ¹Ì¸® ¸»ÇØÁÙ ¼ö ÀÖ´Â ¾î¶² ÀϹÝÀûÀÎ ÀýÂ÷ (¾Ë°í¸®µë) °¡ Àִ°¡? ´Þ¸® ¸»Çϸé, ¾î¶² ÁÖ¾îÁø Æ©¸µ±â°è (Turing Machine) ÇÁ·Î±×·¥ P ¿Í ÀÔ·Â ÀÚ·áµéÀÇ ÁýÇÕ I ¿¡ ´ëÇؼ­, P ¿Í I ¸¦ ¹Þ¾ÆµéÀÎ ´ÙÀ½¿¡ ÀÚ·á I ¸¦ ó¸®ÇÒ ¶§ P °¡ À¯ÇÑÇÑ ¼öÀÇ ´Ü°è ÈÄ¿¡ ¸ØÃâ °ÍÀÎÁöÀÇ ¿©ºÎ¸¦ ¿ì¸®¿¡°Ô ¸»ÇØÁÙ ¼ö ÀÖ´Â ¾î¶² ´ÜÀÏÇÑ ÇÁ·Î±×·¥ÀÌ Àִ°¡? À̶§ ¿ì¸®°¡ ¹®Á¦»ï´Â °ÍÀÌ ¸ðµç °æ¿ì¿¡ ÀÛµ¿ÇÒ ¾î¶² ´ÜÀÏÇÑ ÇÁ·Î±×·¥À̶ó´Â °ÍÀ» ÁÖ¸ñÇ϶ó. ¹Ù·Î ÀÌ°ÍÀÌ ±× À¯¸íÇÑ ¸ØÃã¹®Á¦ (Halting Problem) ´Ù.

...... ½ÇÁ¦ ÇÁ·Î±×·¥¿¡ ´ëÇÑ ¸ØÃã ±ÔÄ¢Àº ´ë°³ "¸¸ÀÏ ÀÌ·±Àú°Ç Á¶°ÇÀ» ¸¸Á·ÇÏ´Â ±×·¯±×·¯ÇÑ °ªÀÌ ³ª¿À¸é ¸ØÃç¶ó. ±×·¸Áö ¾ÊÀ¸¸é °è¼ÓÇؼ­ °è»êÇ϶ó" ¿Í °°ÀÌ ¸»ÇÏ´Â, ¾Õ¿¡¼­ Á¦½ÃµÈ °Í°ú Á¾·ù°¡ °°Àº ¾Ï¹¬ÀûÀÎ ±ÔÄ¢ÀÌ´Ù. ¸ØÃã¹®Á¦¿¡¼­ ÇÙ½ÉÀûÀÎ °ÍÀº ÇÁ·Î±×·¥ÀÇ ¸ØÃã Á¶°ÇÀÌ ¸¸Á·µÉ °ÍÀ̳ÄÀÇ ¿©ºÎ¸¦ ¹Ì¸® ¸»ÇØÁÖ±â À§ÇØ ±× ÇÁ·Î±×·¥°ú ÀÔ·ÂÀÚ·áµé¿¡ Àû¿ëµÉ ¼ö ÀÖ´Â ¾î¶² È¿°úÀûÀÎ ÀýÂ÷°¡ Á¸ÀçÇÏ´À³Ä ÇÏ´Â ¹°À½ÀÌ´Ù. 1936 ³â¿¡ Alan Turing Àº ÀÌ ¹®Á¦¸¦ ÀÏ°Å¿¡ ºÎÁ¤ÀûÀ¸·Î ÇØ°áÇß´Ù. Áï ÁÖ¾îÁø ÇÁ·Î±×·¥ P ¿Í ÀÔ·ÂÀÚ·á ÁýÇÕ I ¿¡ ´ëÇؼ­, P °¡ ÀÔ·Â I ¸¦ ó¸®ÇÏ´Â °ÍÀ» ³¡³¾ÁöÀÇ ¿©ºÎ¸¦ ¸»ÇØÁÖ´Â ¾î¶² ÀϹÝÀûÀÎ ¹æ¹ýµµ ¾ø´Ù´Â °ÍÀÌ´Ù.

Æ©¸µ ±â°è¶ó´Â °³³äÀº °á±¹ °è»êÀ̶ó´Â »ý°¢À» °ß°íÇÑ ¼öÇÐÀû Åä´ë À§¿¡ ¿Ã·Á³õ¾ÒÀ¸¸ç, ¿ì¸®·Î ÇÏ¿©±Ý È¿°úÀû (effective) ÀýÂ÷¶ó´Â ¸ðÈ£ÇÏ°í Á÷°üÀûÀÎ »ý°¢¿¡¼­ ¾Ë°í¸®µëÀ̶ó´Â Á¤È®ÇÏ°í ¼öÇÐÀûÀ¸·Î Àß Á¤ÀÇµÈ °³³äÀ¸·Î ³ª¾Æ°¡°Ô Çß´Ù ..... (John Casti 2000)

Á¤Áö¹®Á¦´Â ºñ°ø½ÄÀûÀ¸·Î ´ÙÀ½°ú °°ÀÌ ¹¦»çÇÒ ¼ö ÀÖ´Â ÆÇÁ¤¹®Á¦ (Entscheidungsproblem) ÀÌ´Ù.

Alan Turing Àº 1936 ³â¿¡ ¸ðµç °¡´ÉÇÑ ÀԷ¿¡ ´ëÇØ Á¤Áö¹®Á¦¸¦ ÇØ°áÇÒ ¼ö ÀÖ´Â ÀϹÝÀûÀÎ ¹æ¹ýÀ̳ª ¾Ë°í¸®ÁòÀº ¾ø´Ù´Â °ÍÀ» Áõ¸íÇß´Ù. Á¤Áö¹®Á¦°¡ Áß¿äÇÑ ÀÌÀ¯´Â ±×°ÍÀÌ °áÁ¤ºÒ°¡´É¼º (undecidable)À» Áõ¸íÇÏ´Â ÃÖÃÊÀÇ ¹®Á¦¿´´Ù´Â »ç½ÇÀÌ´Ù. °è¼ÓÇؼ­ ¸¹Àº ´Ù¸¥ ¹®Á¦µéÀÌ ´Ù·ç¾îÁ³À¸¸ç, °áÁ¤ºÒ°¡´É¼ºÀÎ ¹®Á¦¸¦ Áõ¸íÇÏ´Â ÀüÇüÀûÀÎ ¹æ¹ýÀº ±×°ÍÀ» Á¤Áö¹®Á¦·Î Ãà¼Ò½ÃÅ°´Â °ÍÀÌ´Ù.

Á¤Áö¹®Á¦ÀÇ °áÁ¤ºÒ°¡´É¼º¿¡ ´ëÇÑ °á°ú´Â ÆÇÁ¤¹®Á¦ (Entscheidungsproblem) °¡ ÇØ°áµÉ ¼ö ¾øÀ¸¸ç, ƯÈ÷ ÀÚ¿¬¼ö¿¡ ´ëÇÑ ¾î¶² ¹®ÀåÀÌ ÂüÀÎÁö °ÅÁþÀÎÁö¸¦ °áÁ¤ÇÏ´Â ÀϹÝÀûÀÎ ¾Ë°í¸®ÁòÀº ÀÖÀ» ¼ö ¾ø´Ù´Â °ÍÀÌ´Ù. ±× ÀÌÀ¯´Â ¾î¶² ¾Ë°í¸®ÁòÀÌ ¾î¶² ÀÔ·ÂÀÌ ÁÖ¾îÁ³À» ¶§ ¸ØÃâ °ÍÀ̶ó°í Áø¼úÇÏ´Â ¸íÁ¦´Â ¼ö¿¡ °üÇÑ ¹®ÀåÀ¸·Î ÀÚµ¿ÀûÀ¸·Î ´Ù½Ã °ø½ÄÈ­ÇÒ ¼ö ÀÖ´Ù´Â °Í ¶§¹®ÀÌ´Ù. Áï ¾Ë°í¸®Áò¿¡ °üÇÑ ¿ø·¡ÀÇ ¹®ÀåÀÌ ÂüÀÎÁö °ÅÁþÀÎÁö °áÁ¤ÇÒ ¼ö ÀÖ´Â ¾Ë°í¸®ÁòÀº ¾ø±â ¶§¹®¿¡, ¼ö¿¡ °üÇÑ µ¿µîÇÑ ¹®ÀåÀÌ ÂüÀÎÁö °ÅÁþÀÎÁö °áÁ¤ÇÒ ¼ö ÀÖ´Â ¾Ë°í¸®ÁòÀº ¾ø´Ù´Â °ÍÀÌ´Ù.

±×·¯³ª Á¤Áö¹®Á¦ÀÇ °áÁ¤ºÒ°¡´É¼º¿¡ °üÇÑ ¾ÆÁÖ ³î¶ó¿î ¶Ç´Ù¸¥ °á°ú´Â, ¾Ë°í¸®ÁòÀ¸·Î Á¤ÀǵǴ ÇÔ¼ö¿¡ ´ëÇÑ ¾î¶² Áß¿äÇÑ (non-trivial) ¹®ÀåÀÇ Áø¸®¿©ºÎ´Â °áÁ¤µÉ ¼ö ¾ø´Ù´Â Rice's theorem ÀÌ´Ù. ¿¹¸¦µé¸é, "ÀÌ ¾Ë°í¸®ÁòÀº 0 ÀÌ ÀÔ·ÂµÇ¸é ¸ØÃâ °ÍÀÌ´Ù" ¶ó´Â °áÁ¤¹®Á¦´Â ÀÌ¹Ì °áÁ¤ºÒ°¡´ÉÇÏ´Ù. ÀÌ Á¤¸®´Â ¾Ë°í¸®Áò ±× ÀÚü°¡ ¾Æ´Ï¶ó ¾Ë°í¸®Áò¿¡ ÀÇÇØ Á¤ÀÇµÈ ÇÔ¼ö¸¦ °¡Áö°í ÀÖ´Ù´Â °ÍÀ» ÁÖ¸ñÇ϶ó. ¿¹¸¦µé¸é ¾î¶² ¾Ë°í¸®ÁòÀÌ 100 step À̳»¿¡ ¸ØÃâ °ÍÀÎÁö¸¦ °áÁ¤ÇÏ´Â °ÍÀº °¡´ÉÇÏÁö¸¸, ±×·¯³ª ÀÌ°ÍÀº ¾Ë°í¸®Áò¿¡ ÀÇÇØ Á¤ÀÇµÈ ÇÔ¼ö¿¡ ´ëÇÑ ¹®ÀåÀÌ ¾Æ´Ï´Ù. ......

Gregory Chaitin ´Â Á¤Áö¹®Á¦¿¡ ÀÇÁ¸ÇÏÁö ¾Ê´Â algorithmic information theory ¿¡ °üÇÑ °áÁ¤ºÒ°¡´É ¹®Á¦¸¦ Á¦½ÃÇß´Ù. ±×´Â ÀÓÀÇ·Î ¸¸µé¾îÁø ÇÁ·Î±×·¥ÀÌ Á¤ÁöÇÒ È®·üÀ» Ç¥ÇöÇÏ´Â halting probability ÀÇ Èï¹Ì·Î¿î Á¤ÀǸ¦ Á¦½ÃÇß´Ù.

Æ©¸µÀÇ Á¤¸®°¡ ¾Ë°í¸®ÁòÀÌ ¸ØÃß´Â Áö¸¦ °áÁ¤ÇÒ ÀϹÝÀûÀÎ ¹æ¹ýÀ̳ª ¾Ë°í¸®ÁòÀÌ ÀÖÀ» ¼ö ¾ø´Ù´Â °ÍÀ» º¸¿©ÁÖ´Â ¹Ý¸é¿¡, °³º° ÇÁ·Î±×·¥ÀÇ °æ¿ì¿¡´Â °ø°Ý¿¡ ¸Å¿ì ¹Î°¨ÇÒ ¼ö ÀÖ´Ù (individual instances of that problem may very well be susceptible to attack). Ưº°ÇÑ ¾Ë°í¸®ÁòÀÌ ÁÖ¾îÁ³À» ¶§, ¾î¶² ÀÔ·ÂÀÏ °æ¿ì¿¡ ±×°ÍÀÌ ¸ØÃç¾ßÇÏ´Â Áö¸¦ º¸ÀÏ ¼ö ÀÖ´Ù. ±×·¯³ª »ç½Ç ÄÄÇ»ÅÍ°úÇÐÀÚ´Â ÇϳªÀÇ correctness proof ÀÇ ºÎºÐÀ¸·Î¼­¸¸ ±×°ÍÀ» ¼öÇàÇÑ´Ù. ±×·¯³ª ¸ðµç ±×·± Áõ¸íÀº, "¾Ë°í¸®ÁòÀÌ ¸ØÃß´Â Áö¸¦ °áÁ¤ÇÏ´Â mechanical, general way °¡ ¾ø´Ù" ´Â »õ·Î¿î Ãß·ÐÀ» ¿ä±¸ÇÑ´Ù.

¶Ç´Ù¸¥ °æ°í°¡ ÀÖ´Ù. Á¤Áö¹®Á¦ÀÇ °áÁ¤ºÒ°¡´É¼ºÀº ¾Ë°í¸®ÁòÀÌ ¾Æ¸¶µµ ¹«ÇÑÀÇ ÀúÀåÀåÄ¡¸¦ °¡Áø´Ù°í °¡Á¤ÇÑ´Ù´Â »ç½ÇÀÌ´Ù. ¾î´À ÇѼø°£¿¡´Â À¯ÇÑÇÑ °ÍµéÀ» ÀúÀåÇÒ ¼ö ÀÖÁö¸¸, ±×°ÍÀº Ç×»ó ´õ ¸¹Àº °ÍÀ» ÀúÀåÇÏ°í °áÄÚ ¸Þ¸ð¸®¸¦ ÃÊ°úÇÏÁö ¾Ê´Â´Ù. ¸¸ÀÏ ±â°èÀÇ ¸Þ¸ð¸®¿Í ¿ÜºÎ ÀúÀåÀåÄ¡°¡ À¯ÇÑÇÏ´Ù¸é, ±×°ÍÀº ½ÇÁ¦·Î Á¸ÀçÇÏ´Â ÄÄÇ»ÅÍ¿¡ ´ëÇÑ °ÍÀÌ°í, µû¶ó¼­ ±â°è»ó¿¡¼­ ÀÛµ¿ÇÏ´Â ÇÁ·Î±×·¥¿¡ ´ëÇÑ Á¤Áö¹®Á¦´Â ÀÏ¹Ý ¾Ë°í¸®ÁòÀ¸·Î ÇØ°áµÉ ¼ö ÀÖ´Ù (ºñ·Ï ±ØÈ÷ ºñÈ¿À²ÀûÀÎ °ÍÀÌÁö¸¸). .............. (Wikipedia : Halting problem)

term :

¸ØÃã¹®Á¦ (Halting Problem)   Æ©¸µ±â°è (Turing Machine)   Æ©¸µ Å×½ºÆ® (Turing Test)   Æ©¸µ ¸íÁ¦ (Turing Thesis)   °è»ê°¡´É¼º ÀÌ·Ð (Computability Theory)   °è»ê (Computation)   °è»êº¹ÀâµµÀÌ·Ð (Computational Complexity Theory)   ÆÇÁ¤¹®Á¦ (Entscheidungsproblem)   ¾Ë°í¸®Áò (Algorithm)

paper :

¸ØÃã¹®Á¦ (halting problem) : John Casti. Werner De Pauli

video :

ÄÄÇ»ÅÍ°úÇÐÀÌ ¿©´Â ¼¼°è - ¸ØÃã¹®Á¦¸¦ Ǫ´Â Æ©¸µ±â°è´Â ¾ø´Ù : SNU : À̱¤±Ù : 2016/03/07 ... µ¿¿µ»ó 82°³

Proof That Computers Can't Do Everything (The Halting Problem) : 2013/09/27

 

Turing & The Halting Problem - Computerphile : 2014/08/21