컴퓨터과학이 여는 세계_2.1 기계적 계산의 정의: 튜링기계_이광근

강좌 동영상

 귀델은 기계적인 방식으로 모든 참인 명제를 만들어 낼 수 없음을 풀리지 않는 문제를 풀기 위해 기계를 계속 확장하여도 풀어낼 수 없는 문제가 계속 나온다는 것을 증명하였다.

 튜링은 이 증명을 듣고 자신만의 방법으로 튜링기계를 만들어 증명하고자 했다.

(튜링기계에 대한 설명은 이쪽으로)

 이 기계를 만들고 이것으로 계산하는 것만 기계적인 방법이라고 정의를 내렸다. 그 후 이 기계가 충분히 기계적임을 대표한다는 것을 보이기 위해 여러 방법으로 설득을 한 뒤에 이 기계로도 풀리지 않는 문제가 있음을 밝혔다.

 이 기계가 확장되고 확장되어 Universal Machine인 오늘날의 컴퓨터가 되었다.