계산 가능 함수

계산 가능한 함수(computable function)는 그 함수의 결과값을 특정한 계산 방식을 따라 유한 시간 안에 얻어낼 수 있는 함수를 의미한다. 계산 가능한 함수는 알고리즘의 개념을 함수로 표현한 것으로 볼 수 있는데, 이때 함수는 특정한 알고리즘으로 정의되고, 해당 알고리즘을 계산하는 것으로 함수의 값을 얻는다.

계산 가능한 함수의 구체적인 정의는 계산 모델에 따라 결정되는데, 다음의 계산 모델은 모두 동일한 계산 가능성을 가지며, 따라서 이를 기반으로 정의하는 계산 가능한 함수 역시 동일한 의미를 가진다.

• 튜링 기계
• μ-재귀 함수
• 람다 대수

계산 가능한 집합

 이 부분의 본문은 재귀 집합입니다.

계산 가능한 집합(computable set)은 임의의 값이 그 집합에 속하는지를 계산할 수 있는 집합을 의미한다.

집합 $A$에 대하여, 계산 가능한 함수 $f$가 존재하여, 어떤 값 $n$이 $A$에 속한다면 $f(n)=1$, 속하지 않는다면 $f(n)=0$일 경우, 이 집합은 계산 가능하다고 정의한다.

한편, 어떤 집합에 대하여, 부분적으로 계산 가능한 함수가 존재하여, 임의의 값에 대하여 그 값이 집합에 속하는 것과 그 값에 대한 함수값이 존재하는 것이 동치일 경우, 그 집합은 귀납적으로 셀 수 있는 집합(recursively enumerable set)이라고 정의한다.