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)