μ-재귀 함수
자연수에서 자연수로의 계산 가능한 부분 함수 / From Wikipedia, the free encyclopedia
수리논리학 및 컴퓨터 과학에서 μ-재귀 함수(영어: μ-recursive function) 또는 간단히 재귀 함수란, 자연수에서 자연수로의 '계산가능한' 부분 함수이다. 재귀 이론에서는, μ-재귀 함수와 튜링 기계로 계산가능한 함수가 일치하는 것임이 알려져 있다. 유명한 예로 피보나치 수 등이 있다.
μ-재귀 함수는 원시 재귀 함수와 밀접한 관련이 있으며, 그 재귀적(귀납적) 정의가 원시 재귀 함수에 기초하고 있다. 다만, μ재귀함수가 모두 원시 재귀 함수인 것은 아닌데, 그러한 예로 아커만 함수 등이 있다.
또 재귀함수와 일치하는 개념으로는, 람다 계산에서 쓰이는 재귀함수나 마르코프 알고리즘(Markov algorithms)으로 계산가능한 함수 등이 있다.