Computation

History

‘계산’에 대한 형식적 정의가 만들어지기 전에 논리학 및 수학에서 쓰이던 표현은 ‘효과적 방법’, ‘효과적 절차effective procedure’ 등이었다. 당시에 “컴퓨터”는 계산을 하는 직업을 가진 사람을 뜻했고, 효과적 절차란 ‘직관적으로 생각하기에 기계적인 계산 절차’에 따라 팬과 종이를 써서 수행하는 계산 행위를 말했다.

1920년대 이후 계산이 무엇인지를 명확히 정의하기 위한 여러 시도가 있었고 그 결과 여러 형식적 정의가 만들어졌는데, “튜링 기계 또는 그와 동등한 기계에 의해 수행될 수 있으면 계산이다”라는 정의가 가장 널리 알려져 있다.

앨런 튜링의 튜링 기계와 동등한 기계(또는 계산 체계)에서는 알론조 처치의 람다식도 포함된다. 알론조 처치는 “효과적 계산가능성effective computability”라는 표현을 썼고, 그의 제자인 앨런 튜링은 “계산computation”이라는 표현을 썼다.

In a recent paper Alonzo Church has introduced an idea of “effective calculability”, which is equivalent to my “computability”, but is very differently defined … The proof of equivalence between “computability” and “effective calculability” is outlined in an appendix to the present paper¹

Footnotes

1. On computable numbers, with an application to the entscheidungsproblem ↩