Recursive  Functions

 

¼öÇаú ÄÄÇ»ÅÍ°úÇп¡¼­ Àç±ÍÇÔ¼ö´Â ÀÚ¿¬¼öÀÇ ¹üÀ§¿¡¼­ Á÷°üÀûÀ¸·Î "°è»ê°¡´ÉÇÑ (computable)" ÇÔ¼öÀÇ ÀÏÁ¾ÀÌ´Ù. ½ÇÁ¦·Î °è»ê°¡´É¼º ÀÌ·Ð (Computability Theory) ¿¡¼­´Â, Àç±ÍÇÔ¼ö´Â Æ©¸µ±â°è (Turing Machine) ·Î °è»êÇÒ ¼ö ÀÖ´Â ¹Ù·Î ±× ÇÔ¼öÀÓÀ» º¸¿©ÁØ´Ù. Àç±ÍÇÔ¼ö´Â primitive recursive functions °ú °ü·ÃÀÌ ÀÖÀ¸¸ç, ±×·ÎºÎÅÍ À¯·¡ÇÑ Á¤ÀÇ´Â primitive recursive functions ÀÇ Á¤ÀÇ¿¡ µû¶ó ¸¸µç´Ù. ¸ðµç Àç±ÍÇÔ¼ö°¡ primitive recursive ÀÎ °ÍÀº ¾Æ´Ï´Ù - °¡Àå À¯¸íÇÑ ¿¹°¡ Ackermann function ÀÌ´Ù. ºñ½ÁÇÑ ÇÔ¼öÀÇ Á¾·ù·Î´Â ¥ë-recursive functions ¿Í ¸¶¸£ÄÚÇÁ ¾Ë°í¸®Áò (Markov Algorithm) À¸·Î °è»ê°¡´ÉÇÑ ÇÔ¼ö°¡ ÀÖ´Ù. ............... (Wikipedia : Recursive Function)

Æ©¸µÀº 1936 ³â On Computable Numbers, with an Application to the Entscheidungsproblem ¶ó´Â ³í¹®¿¡¼­ Æ©¸µ±â°è (Turing Machine) À» ¼Ò°³Çϸ鼭 Æ©¸µ ¸íÁ¦ (Turing Thesis) ¶ó´Â Ç¥ÇöÀ» °ø½ÄÀûÀ¸·Î »ç¿ëÇß´Ù. ±× ³í¹®¿¡¼­´Â '°áÁ¤¹®Á¦ (Entscheidungsproblem)' ´Â Ç® ¼ö ¾ø´Ù´Â °ÍÀ» º¸¿©ÁØ´Ù. À̺¸´Ù ¸î ´Þ ¾Õ¼­¼­ Church ´Â ±×ÀÇ ³í¹®  A Note on the Entscheidungsproblem À» ÅëÇؼ­ À¯»çÇÑ °á°úÀ» Áõ¸íÇߴµ¥, ±×´Â È¿À²ÀûÀÎ °è»ê°¡´É¼ºÀ» Ç¥ÇöÇϱâ À§ÇØ Àç±ÍÇÔ¼ö (Recursive Function) ¿Í ¶÷´Ù °è»ê¹ý (Lambda Calculus) ¶ó´Â Ç¥ÇöÀ» »ç¿ëÇß´Ù. Lambda calculus ´Â Church ¿Í Stephen Kleene°¡ óÀ½ »ç¿ëÇß°í Àç±ÍÇÔ¼ö´Â Kurt Gödel ¿Í Jacques Herbrand °¡ óÀ½ »ç¿ëÇÏ¿´´Ù. ÀÌ µÎ°¡Áö Ç¥ÇöÀº Church ¿Í Kleene ÀÌ »ç¿ëÇÑ functions of positive integers ÀÇ °æ¿ì¿¡¼­ ¾Ë ¼ö ÀÖµíÀÌ °°Àº Á¾·ùÀÇ ÇÔ¼ö¸¦ Ç¥ÇöÇÏ´Â °ÍÀÌ´Ù. Church ÀÇ Á¦¾ÈÀ» µé¾úÀ» ¶§ Æ©¸µÀº ½ÇÁ¦·Î ±×ÀÇ Æ©¸µ±â°è (Turing Machine) ¿Í °°Àº Á¾·ùÀÇ ÇÔ¼öµé·Î Ç¥ÇöµÈ´Ù´Â °ÍÀ» Áï½Ã ¾Ë ¼ö ÀÖ¾ú´Ù. .........

term :

Àç±Í (Recursion)   °è»êÀÌ·Ð (Theory of Computation)   °è»ê°¡´É¼º ÀÌ·Ð (Computability Theory)   Àç±ÍÇÔ¼ö (Recursive Function)