"어떤 문제를 알고리즘으로 해결할 수 있는가?” 는 20세기 초반 계산 이론이라는 수학의 영역이었습니다.
이러한 계산 가능성을 탐구하기 위해 알랜 튜링은 튜링 머신이라는 가상의 알고리즘 기계를 고안했습니다.
튜링 머신을 통해 튜링은 알고리즘에 의해 풀리지 않는 문제가 존재함을 증명했습니다.
튜링이 증명했던 알고리즘에 의해 풀리지 않는 문제는 바로 정지 문제였습니다.
즉, 튜링 머신이 계산 알고리즘과 데이터를 입력 받아서 계산 후 멈추면 문제를 알고리즘으로 해결한 것이고, 멈추지 못 하면 해결하지 못 한 것입니다.
정지 여부를 통해 해결 여부를 판가름 한다는 것입니다.
튜링의 증명은 아래와 같습니다.
def halt(ftn) :
# ftn 함수가 계산 후 멈추면 True, 아니면 False를 반환
return True or False
def foo(ftn) :
if halt(ftn) == True :
while True:
print ‘hello’
# 재귀로 foo 함수를 호출하면, 모순이 발생합니다. foo 가 멈추면 halt(foo)가 참이고, foo는 결국 무한 루프를 돕니다. 따라서, 위의 halt 함수는 존재할 수 없습니다.
foo(foo)
물론 튜링은 위와 같은 pseudo 코드 대신 튜링머신으로 증명했는데 방법은 위의 pseudo 코드와 비슷합니다.
즉, 위의 foo 함수와 같은 튜링머신을 만들어서 재귀적으로 호출해서 halt 함수와 같은 튜링머신이 존재할 수 없음을 증명한 것이죠.
비슷한 시기에 알론소 처치도 재귀함수와 람다 계산법을 통해 이 정지 문제를 증명했습니다. (아쉽게도 처치의 자세한 증명은 아직 공부가 안되었습니다…)
튜링과 처치는 재귀를 통해서 정지 문제를 증명했다는 공통점이 있습니다.
재귀가 어떤 의미를 가지는지 아직 잘 모르겠지만, 전산학에 있어서 재귀는 시발점 역할이 되어 왔고, 재귀함수는 전산학에서 ‘계산 가능한 함수’의 일종으로 분류됩니다.
재귀를 상징하는 Ouroboros라는 전설의 동물
다음 글이 재귀가 가지는 의미에 대해 살짝 소개를 하고 있습니다.
해커 문화의 뿌리를 찾아서 Part 6: ‘괴델, 에셔, 바흐’ 그리고 해커리즘의 쇠락
코딩할 때도 그렇고, 이런 저런 글을 읽어봐도 “재귀”란 참 기묘합니다.
이를테면…
이 명제는 거짓이다라는 명제.
