알고리즘

알고리듬

문제 또는 질문은 '정수 a는 소수인가?' 또는 '두 정수 a와 b의 최대공약수는 무엇인가?'와 같이 무한 개의 원소를 갖는 부류에 속해야 한다. 위에서 첫번째 질문은 '결정가능한' 부류에 속하며, 이처럼 연산결과가 '예' 또는 '아니오'와 같은 답을 만들어낼 경우 이 알고리듬을 결정과정이라고 한다.

2번째 질문은 '계산가능한' 부류에 속하며, 연산결과가 특정한 숫자와 같은 답을 이끌어낼 경우 이 알고리듬을 계산과정이라고 한다. 유한류의 질문에 대해서는 자명한 알고리듬이 항상 존재하며(적어도 원리에 의하면), 답의 값들을 표로 만들 수 있다.

많은 무한류의 질문에 대한 알고리듬도 존재한다. 예를 들면 BC 300년경에 편찬된 에우클레이데스(유클리드)의 〈기하학 원본 Elements〉에는 두 정수의 최대공약수를 구하는 알고리듬이 있다. 대부분 국민학생들은 "정수 a를 다른 정수 b로 나눌 때 몫과 나머지는 얼마인가?"라는 질문에 대한 알고리듬인 장제법(長除法)에 익숙해져 있다.

이러한 계산과정으로 결정가능한 문제, 즉 'a는 b로 나누어지는가?'에 대한 답을 얻을 수 있다(나머지가 0이면 답은 '예'임). 이러한 알고리듬을 반복하여 결국 결정가능한 문제인 'a는 소수인가?'에 대한 답도 얻어 낼 수 있다(a가 1 이외의 a보다 작은 다른 정수로 나누어지면 답은 '아니오'임).

그외의 알고리듬이 알려지지 않은 무한류의 질문들도 존재한다. 1637년 피에르 드 페르마가 방정식 xⁿ＋yⁿ〓zⁿ(n＞2)을 만족하는 정수 n,x,y,z가 존재하지 않음을 증명할 수 있다고 주장한 이후 수학자들은 이런 종류의 유명한 문제들에 몰두해왔다.

페르마뿐 아니라 그 이후의 어느 누구도 그 주장을 증명하지 못했으며, 그것이 틀리다는 단 한 예만으로 충분함에도 불구하고 어떤 논박도 곧 일어나지 않았다. 이러한 경우에는 그것이 아무리 방대하다 해도 결국 문제에서 유한번의 계산으로 정수들이 나오기 때문에 알고리듬을 세울 수는 있다.