Entscheidungsproblem

 

¸¸ÀÏ ¿ì¸®¿¡°Ô ¾î¶² ³í¸®±â°è°¡ À־ ±× ¾È¿¡ ÀÌ·± Á¾·ùÀÇ Áø¼úµéÀ» Áý¾î ³Ö°í ¼ÕÀâÀ̸¦ µ¹·Á¼­, ±× ³íº¯ÀÌ ³í¸®ÀûÀ¸·Î Ÿ´çÇÑÁö ¿©ºÎ¸¦ ±× ±â°è°¡ È®Á¤ÀûÀ¸·Î ¿ì¸®¿¡°Ô ¸»ÇØÁشٸé ÀÌ ¾ó¸¶³ª ¸ÚÁø ÀÏÀ̰ڴ°¡. ÀÌ·¯ÇÑ ±â°è¸¦ ³í¸®ÇÐÀÚµéÀº °áÁ¤ÀýÂ÷ (decision procedure) ¶ó°í ÇÑ´Ù. ¹Ù·Î ÀÌ·¯ÇÑ ÀýÂ÷¿¡ ´ëÇÑ ¿¬±¸°¡ 1930 ³â´ë¿¡ ¿µ±¹ÀÇ ¼öÇÐÀÚ Alan Turing À¸·Î ÇÏ¿©±Ý °è»ê (Computation) ÀÇ ±âÃʸ¦ Ž±¸Çϵµ·Ï Ã˹߽ÃŲ °è±â°¡ µÇ¾ú´Ù........ Æ©¸µÀ¸·Î ÇÏ¿©±Ý Áö±ÝÀº Æ©¸µ±â°è (Turing Machine) ¶ó°í À̸§ºÙÀÎ ÀÌ·ÐÀûÀÎ ±â°èÀåÄ¡¸¦ °í¾ÈÇϵµ·Ï ÇÑ °ÍÀÌ ¹Ù·Î °áÁ¤¹®Á¦ (¿µ¾î·Î´Â decision problem, µ¶¾î·Î´Â Entscheidungsproblem) ÀÌ´Ù ......... (Rudy Rucker 1988)

Entscheidungsproblem ´Â ÁÖ¾îÁø ÀÏÂ÷³í¸® (first order) ¹®ÀåÀÌ À¯È¿ÇÑÁö (universally valid) ¾Æ´ÑÁö¸¦ °áÁ¤ÇÏ´Â (decide) ¹ü¿ë ¾Ë°í¸®ÁòÀ» ¹ß°ßÇÏ·Á°í ÇÏ´Â, ±âÈ£³í¸®ÇÐ (Symbolic Logic) ºÐ¾ßÀÇ °úÁ¦ÀÌ´Ù. 1936 ³â¿¡ Alonzo Church ¿Í Alan Turing Àº °¢°¢ÀÇ ¿¬±¸¿¡¼­ ÀÌ°ÍÀÌ ºÒ°¡´ÉÇÏ´Ù´Â °ÍÀ» º¸¿©Áá´Ù. ¸¶Âù°¡Áö·Î, ƯÈ÷ »ê¼ú¿¡¼­ÀÇ ¹®ÀåÀÌ ÂüÀÎÁö °ÅÁþÀÎÁö ¿©ºÎ¸¦ ¾Ë°í¸®ÁòÀûÀ¸·Î °áÁ¤ÇÏ´Â °ÍÀº ºÒ°¡´ÉÇÏ´Ù.

±×·¯ÇÑ Àǹ®Àº 17 ¼¼±âÀÇ Gottfried Leibnitz ºÎÅÍ ½ÃÀ۵Ǿú´Âµ¥, ±×°ÍÀº ¼öÇй®ÀåÀÇ Áø¸®°ªÀ» °áÁ¤Çϱâ À§ÇØ ±âÈ£¸¦ Á¶ÀÛÇÒ ¼ö ÀÖ´Â ±â°è¸¦ ²Þ²Ù¸é¼­, ±â°èÀû °è»ê±â¸¦ ¸¸µå´Âµ¥ ¼º°øÇÑ Á÷ÈÄÀÌ´Ù. ±×´Â ±× ù´Ü°è°¡ ¸íÈ®ÇÑ Çü½Ä¾ð¾î (Formal Language) À̾î¾ß¸¸ ÇÑ´Ù´Â °ÍÀÌ°í ±×ÀÇ °è¼Ó ÁøÇàµÈ ´ëºÎºÐÀÇ ÀÛ¾÷ÀÌ ±× ¸ñÇ¥¸¦ ÇâÇÑ °ÍÀÌ´Ù. 1928 ³â¿¡ David Hilbert ¿Í Ackermann Àº À§¿¡¼­ ¾ð±ÞÇÑ Çü½ÄÀ¸·Î ¹®Á¦¸¦ Á¦±âÇß´Ù.

¾î¶² first-order ¹®ÀåÀÌ ÀÏÂ÷ ¼ú¾î°è»ê (First order predicate calculus) ÀÇ °ø¸® (Axiom) ¸¦ µû¸¥´Ù¸é À¯È¿ÇÏ´Ù (universally valid or logically valid) ¶ó°í ÇÒ ¼ö ÀÖ´Ù. Kurt Gödel ÀÇ ¿ÏÀü¼ºÁ¤¸® (Completeness Theorem) ¿¡¼­´Â ÇϳªÀÇ ¹®ÀåÀÌ ¾î¶² ¸ðµ¨¿¡¼­ ±× °ø½Ä (formula)¸¦ ¸ðµÎ Çؼ®ÇÏ¿´À» ¶§ ÂüÀ̶ó¸é, ±×·¯ÇÑ °æ¿ì¿¡¸¸ À¯È¿ÇÏ´Ù (universally valid) ¶ó°í ÇÏ¿´´Ù.

±× Áú¹®¿¡ ´äÇϱâ Àü¿¡, "¾Ë°í¸®Áò (Algorithm)" À̶ó´Â °ÍÀÌ Çü½ÄÀûÀ¸·Î Á¤ÀǵǾî¾ß ÇÑ´Ù. ÀÌ°ÍÀº 1936 ³â¿¡ Alonzo Church °¡ ¶÷´Ù °è»ê¹ý (Lambda Calculus) ¿¡ ±âÃÊÇؼ­ È¿°úÀûÀÎ °è»ê°¡´É¼º (effective calculability) ¶ó´Â °³³äÀ¸·Î Á¤ÀÇÇÏ¿´°í, Alan Turing Àº °°Àº ÇØ¿¡ Æ©¸µ±â°è (Turing Machine) ÀÇ °³³äÀ¸·Î Á¤ÀÇÇÏ¿´´Ù. µÎ Á¢±Ù¹æ¹ýÀº óġ-Æ©¸µ ¸íÁ¦ (Church-Turing Thesis) ÀÇ ¿¹·Î¼­, °°Àº °ÍÀÌ´Ù.

Entscheidungsproblem ¿¡ ´ëÇÑ ºÎÁ¤ÀûÀÎ ´äº¯ÀÌ 1936 ³â¿¡ Alonzo Church ¿¡ ÀÇÇØ, ±× Á÷ÈÄ¿¡ Alan Turing ¿¡ ÀÇÇØ ÇàÇØÁ³´Ù. Church ´Â µÎ °³ÀÇ ÁÖ¾îÁø lambda calculus expressions ÀÌ °°ÀºÁö ´Ù¸¥Áö¸¦ °áÁ¤ÇØÁÖ´Â ¾Ë°í¸®ÁòÀº Á¸ÀçÇÏÁö ¾Ê´Â´Ù°í Áõ¸íÇß´Ù. ±×´Â ÁÖ·Î Kleene ÀÇ Ãʱâ ÀúÀÛ¿¡ ÀÇÁ¸Çß´Ù. Turing Àº ±× ¹®Á¦¸¦ Turing machine ¿¡¼­ÀÇ Á¤Áö¹®Á¦ (Halting Problem) À¸·Î Ãà¼Ò½ÃÄ×À¸¸ç ±×ÀÇ ³í¹®Àº Church ÀÇ ³í¹®º¸´Ù ÈξÀ ´õ Å« ¿µÇâÀ» ¹ÌÄ£ °ÍÀ¸·Î »ý°¢µÈ´Ù. µÎ»ç¶÷ÀÇ ÀÛ¾÷Àº Kurt Gödel ÀÇ ºÒ¿ÏÀü¼º Á¤¸® (Incompleteness Theorem) ¿¡ ´ëÇÑ Ãʱâ ÀúÀÛ¿¡ Å©°Ô ¿µÇâÀ» ¹ÞÀº °ÍÀ̸ç, ƯÈ÷ ³í¸®¸¦ »ê¼ú·Î Ãà¼Ò½ÃÅ°±â À§ÇØ ¼ýÀÚµéÀ» ³í¸®Àû °ø½Ä¿¡ ÇÒ´çÇÏ´Â ¹æ¹ý¿¡ ¿µÇâÀ» ¹Þ¾Ò´Ù.

Turing ÀÇ ÁÖÀåÀ» µû¶ó°¡º¸ÀÚ. first order logic À» À§ÇÑ ÀϹÝÀûÀÎ °áÁ¤ ¾Ë°í¸®ÁòÀ» °¡Á³´Ù°í Çغ¸ÀÚ. ÁÖ¾îÁø Turing machine ÀÌ Á¤ÁöÇÏ´ÂÁö ¾Ê´ÂÁö¿¡ ´ëÇÑ Àǹ®Àº °áÁ¤ ¾Ë°í¸®Áò¿¡ ¹Î°¨ÇÑÁö ¾Æ´ÑÁö ÇÏ´Â first-order ¹®Àå¿¡ ´Þ·È´Ù°í ÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª Turing Àº ÁÖ¾îÁø Turing machine ÀÌ Á¤ÁöÇÏ´ÂÁö ¿©ºÎ¸¦ °áÁ¤ÇÒ ¼ö ÀÖ´Â ¾î¶² ¾Ë°í¸®Áòµµ Á¸ÀçÇÏÁö ¾Ê´Â´Ù´Â °ÍÀ» Áõ¸íÇß´Ù.

¸¸ÀÏ ¿ì¸® ½º½º·Î specified object constants, function constants, predicate constants, subject axioms À» °¡Áø Ưº°ÇÑ first-order À̷п¡ ±¹ÇÑÇÑ´Ù¸é, ±× À̷п¡¼­ÀÇ ¹®ÀåÀÇ Âü °ÅÁþÀº »ê¼úÀûÀ¸·Î ¸Å¿ì Àß °áÁ¤µÉ ¼ö ÀÖÀ» °ÍÀ̶ó´Â °ÍÀÌ Áß¿äÇÏ´Ù. ÀÌ°ÍÀÇ ¿¹°¡ Presburger arithmetic ¿¡ ÁÖ¾îÁø´Ù.

±×·¯³ª Peano's axioms ¿¡ Ç¥ÇöµÈ natural numbers ÀÇ ÀϹÝÀûÀÎ first-order ÀÌ·ÐÀº ±×·± ¾Ë°í¸®ÁòÀ¸·Î´Â °áÁ¤µÉ ¼ö ¾ø´Ù. ÀÌ°ÍÀº À§¿¡¼­ ¾ð±ÞÇÑ Turing ÀÇ ÁÖÀåÀ¸·ÎºÎÅÍ ³ª¿Â´Ù. .............. (Wikipedia : Entscheidungsproblem)

´ÙÀ½ Ç¥¿¡¼­´Â °è»ê°¡´É¼º ÀÌ·Ð (Computability Theory) (û»ö) °ú °è»êº¹ÀâµµÀÌ·Ð (Computational Complexity Theory) (³ì»ö) ¿¡¼­ °í·ÁµÇ´Â ¹®Á¦µé (¶Ç´Â ¾ð¾î, ¹®¹ýµé) À» ºÐ·ùÇÏ´Â ÀϺθ¦ º¸¿©ÁØ´Ù. ¸¸ÀÏ ¹®Á¦ X °¡ Y ÀÇ ÁøºÎºÐÁýÇÕ À̶ó¸é X ´Â Y ÀÇ ¾Æ·¡¿¡ À§Ä¡ÇÏ°í °ËÀº»ö ¼±À¸·Î ¿¬°áµÈ´Ù. ¸¸ÀÏ X °¡ ºÎºÐÁýÇÕÀÌÁö¸¸ °°Àº ÁýÇÕ (equal sets) ÀÎÁöµµ ¸ð¸¦ ¶§´Â Á¡¼±À¸·Î ¿¬°áµÈ´Ù.  

 

Decision Problem

 

 

 

SolidLine.png

 

SolidLine.png

 

 

Type 0 (Recursively enumerable)

 

Undecidable

SolidLine.png

 

 

 

 

 

Decidable

 

 

 

 

 

SolidLine.png

 

 

 

 

 

EXPSPACE

 

 

 

 

 

DottedLine.png

 

 

 

 

 

EXPTIME

 

 

 

 

 

DottedLine.png

 

 

 

 

 

PSPACE

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

DottedLine.png

Type 1 (Context-sensitive)

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

PSPACE-Complete

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

 

SolidLine.png

SolidLine.png

Co-NP

DottedLine.png

 

NP

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

DottedLine.png

SolidLine.png

SolidLine.png

DottedLine.png

BPP

 

BQP

 

NP-complete

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

 

SolidLine.png

SolidLine.png

P

SolidLine.png

SolidLine.png

DottedLine.png

 

DottedLine.png

SolidLine.png

NC

 

P-Complete

SolidLine.png

SolidLine.png

 

 

 

 

 

Type 2 (Context-free)

 

 

 

 

 

SolidLine.png

 

 

 

 

 

Type 3 (Regular)

 

 

 

 

 

 

term :

Æ©¸µ±â°è (Turing Machine)   Æ©¸µ Å×½ºÆ® (Turing Test)   Æ©¸µ ¸íÁ¦ (Turing Thesis)   °è»ê°¡´É¼º ÀÌ·Ð (Computability Theory)   °è»ê (Computation)   °è»êº¹ÀâµµÀÌ·Ð (Computational Complexity Theory)

paper :

ÇØ°áÀÌ ºÒ°¡´ÉÇÑ ¹®Á¦µé : Rudy Rucker

¾Ë°í¸®Áò°ú Æ©¸µ ±â°è : Roger Penrose