계산 가능 함수
From Wikipedia, the free encyclopedia
계산 가능한 함수(computable function)는 그 함수의 결과값을 특정한 계산 방식을 따라 유한 시간 안에 얻어낼 수 있는 함수를 의미한다. 계산 가능한 함수는 알고리즘의 개념을 함수로 표현한 것으로 볼 수 있는데, 이때 함수는 특정한 알고리즘으로 정의되고, 해당 알고리즘을 계산하는 것으로 함수의 값을 얻는다.
계산 가능한 함수의 구체적인 정의는 계산 모델에 따라 결정되는데, 다음의 계산 모델은 모두 동일한 계산 가능성을 가지며, 따라서 이를 기반으로 정의하는 계산 가능한 함수 역시 동일한 의미를 가진다.