결정론적 모델이란?
예측한 그대로 동작하는 알고리즘이다. 어떤 특정한 입력이 들어오면 언제나 똑같은 과정을 거쳐서 언제나 똑같은 결과를 내놓는다. ... 결정론적 알고리즘을 가장 단순한 형태로 생각하면 수학 함수라고 볼 수 있다. 함수에 특정한 입력이 들어오면 언제나 동일한 결과를 거쳐서 동일한 결과값이 나오는데, 결정론적 알고리즘도 마찬가지이다. -Wikipedia-
되짚어가며 거슬러 올라가다보면 앨런튜링, 르네데카르트까지 가기때문에... 간략하게만 정의한다면, YES/NO로 답할 수 있는 문제를 '결정문제'(Decision Problem)라고 하며 이런 문제에 대해서
주어진 입력값에 대해서 내부 출력의 각 신호의 관계를 수학모델로 옮기고, 이 모델을 수학적으로 고찰, 결론을 유도하는 것을 의미한다(Wikipedia 참고). 따라서 동일한 입력값이 주어진다면 동일한 결과값을 내뱉는 수학함수로 보면 간단하다.
Deterministic vs. Non-Deterministic vs. Probabilistic Algorithm
튜링기계에서의 예를 살펴보면, 상태(state)가 결정/비결정론 알고리즘과 직접적으로 연관이 있음을 알 수 있다. stateless라는 것은 현재 상태에서 다음상태로 이동할 때 선택가능한 답안이 일정한 것들로 제한되어 유일한 계산경로를 따르는 반면, 비결정론적인 알고리즘의 경우 계산경로가 병렬 가지치기를 통해 다양하게 나타날 수 있다.
가장 직관적이고 간단한 결정론적 모델이지만, 항상 결정론적 알고리즘을 찾을 수 있는 것은 아니기에 이런 경우 확률적 알고리즘을 대안으로 사용할 수 있다. 확률적 알고리즘은 이 다음상태가 확률적으로 결정된다. 아주 작은 확률로 틀릴 수 있지만 근사해를 구하는 효율적인 방법이다.
사실 이것이 파다보면 굉장히 흥미로운 분야라 인공생명, 인공지능의 시초, 오토마타 이론까지 보게 되지만 식견이 짧아 이것과 관련해서는 따로 시간을 내서 공부해봐야 할 것 같다.
