What is computation
우리는 컴퓨터computer에게 계산computation을 시키기 위해 프로그램을 작성한다. 그렇다면 컴퓨터가 수행하는 이 계산의 개념이 무엇일까? 들어가기에 앞서 위키피디아에서 계산의 정의를 긁어와봅시다. (위키피디아의 정의를 분석한 것이기 때문에 틀릴 수도 있습니다. 감안해주세요)
computaiton def
any type of calculation that follows a well-defined model.이제 위의 정의를 이루는 두 가지 개념을 고려해보자.
1. calculation
2. well-defined model한국어로는 calculation 또한 계산으로 번역되는데, 이렇게 보면 순환정의 같기도 하다(계산을 정의하기 위해, 다시 계산의 정의를 들고 오는). 하지만, 영어에서는 computaiton과 calculation이 서로 다른 단어 이고, 위의 정의에서는 computation을 정의하기 위해 calculation의 개념이 사용 되었으므로, calculation이 좀 더 세부적인 개념이라고 볼 수 있을 듯 하다.
이제 calculation의 위키 상의 정의를 다시 따와보자.
calculation def
transforms one or more inputs into one or more outputs대충 구조가 보인다.
- inputs
- outputs
- input에서 output으로 변환하는 transfomration
이렇게 세 부분으로 나눠서 이해할 수 있을 것 같다. input / output / transformation 이 세 가지 요소가 잘 정의될 경우, 우리는 calculation을 수행할 수 있다. 확실히 좀 더 concrete하게 정의 됨을 알 수 있다.
이제 다시 computation의 정의로 돌아가보자. 위의 정의에서 1.에 해당하는 calculation이 잘 정의 되었으니, 두 번째 개념인 follows a well-defined model을 살펴보자.
well-definedness def
어떤 정의가 단 하나의 의미를 가지며, 모호하지(여러 해석이 가능한) 않음. 특정 개념이나 표기가 잘 정의 되었다는 것은 통사적인 표현이 정확한 의미론적 대상을 가리키는 것을 뜻한다. 1:1 대응 된다고 이해해보자.
따라서, 위의 computation의 정의를 풀어 설명하면 아래와 같이 이해할 수 있을 것이다.
computation(분석된 버전) def
1. input / transformation / output 의 구조를
2. well-defined(고정된 의미) 된 모델로 설명하여
3. input을 transform하여 output을 생성해 내는 action물론 여기서 이 transformating 행위의 주체는 사람일수도, 사람이 만든 컴퓨터일 수도 있다. 하지만 계산 수행의 주체보다 더욱 중요한 것은, 이러한 행위 자체를 computation으로 정의 했고, computation을 well-defined model로 의미론적으로 고정함으로써, 수행주체가 인간이 됐든 컴퓨터가 됐든 외계인이 됐든 수학적으로 같은 의미를 지닌 결과들을 '현실적으로' 얻어낼 수 있다는 것이다.
다만, 여기까지는 상당히 러프한 정의이고, 이 시점에서 우리는 명령어라든지, 명령어들의 순차성이라든지에 대해 아무것도 이야기 하지 않았다. 다시 말하자면, 여기까지 우리는 기계적인 계산mechanical computation에 대한 논의는 하지 않았다. 기계적 계산을 포함한 계산 일반에 대한 정의를 한 것이다.
이제 위에서 정의한 일반적인 계산 위에서, 기계적인 계산 mechanical Computation을 정의해보자. 우리가 일반적으로 생각하고 있는 프로그래밍의 순차적인 명령어들의 집합, 이 개념은 알고리즘을 통해 구체화 될 수 있다. 그리고, 이런 알고리즘들이 성립하는 well-defined된 구조가 우리가 수학적으로 관심을 가지고 있는 기계적인 계산의 모델Computation Model이 된다.
이제 알고리즘의 정의를 살펴보자. 다시 위키에서 정의를 긁어왔다.
algorithm def
1. a process or set of well-defined rules
2. *to be followed in calculations* or other problem-solving operations알고리즘 정의의 1.의 a process or set of rules of well-defined rules는 calculation의 transformation의 구체적인 형식을 정의하고 있고, 2.는 위의 computation 정의에서의 calculation을 명시하고 있다.
결국, 알고리즘은 computation에서 러프하게 정의 되어 있는 calculation의 기계적이고 구체적인 수행 방법에 대한 내용인 것이고, turing machine이라든지, lamda calculus라든지 우리가 알고 있는 계산 모델들은 이런 맥락 위에서 존재한다고 볼 수 있다.
