컴퓨터 사이언스에서 재귀가 가지는 특별함

앞서 재귀가 가지는 특별함에 대한 글에 대해 부연 설명할 것이 있습니다.

계산 이론에서 재귀함수는 왜 계산 가능한가 입니다.

잠깐의 웹 서핑과 자료를 뒤져봤는데... 짧은 시간에 알 수 있는게 아닌거 같습니다.

다만, 직관적으로 생각해보면

바로 귀납법과 같은 이유로 보여집니다.

재귀적으로 정의 가능하다는 것은 '나'를 반복 호출하여 정의 가능한 것이고, 이는 귀납법 또는 수열의 점화식과 같이 닫힌 계에서의 정의이기 때문에 값을 도출할 수 있다는 것이지요. (테일러 급수도 한 예가 될 수 있을거 같군요)

엄밀한 수학적 증명은 아니지만, 직관적으로 이해가 됩니다.

그러나, 재귀함수가 계산 가능하다는 것은 직관적 이해가 되지만, 계산 가능한 함수가 재귀함수인지는 직관적이지 않습니다. ^^;

그 부분은 좀 더 연구가 필요하겠군요.

혹시 정확한 정보가 있으면 알려주세요 ^^