논리와 증명의 강

기원전 300년–1637년

problem reformulation

허용 도구의 문법이 방정식의 차수로 번역되다

라이덴에서 인쇄된 《La Géométrie》는 선분 관계를 대수식으로, 곡선을 방정식으로 다루는 방법을 밀어 올렸다. 작도 가능성을 수와 다항식의 성질로 번역할 길이 열린 것이다. 데카르트가 1837년 Wantzel의 정리를 미리 증명한 것은 아니지만, 기하의 “안 된다”를 대수의 차수와 연산으로 판정할 수 있게 한 중요한 어깨였다.

1854년–1928년

publication network

논리를 계산하는 대수에서 모든 문장을 판정하는 꿈으로

《이론 논리의 기초》는 어떤 논리식이 항상 참인지를 유한한 연산으로 판정할 일반 절차가 있는지 물었다. 이 *Entscheidungsproblem*은 ‘기계적 방법’이 무엇인지 아직 정확히 정의되기 전에 제시된 야심찬 질문이었다. 괴팅겐 핀은 힐베르트 학파의 강의·연구 맥락이며, 책의 정확한 집필실이나 출판 도시를 뜻하지 않는다.

1928년–1931년

institutional problem network

완전성을 요구한 프로그램이 체계 내부의 한계를 만나다

괴델은 자연수 산술을 표현할 만큼 강하고 효과적으로 공리화된 체계에는, 일정한 무모순성 가정 아래 체계 안에서 결정하지 못하는 문장이 생긴다는 것을 보였다. 또 그런 체계는 일반적으로 자신의 무모순성을 자신의 방법만으로 증명할 수 없다. 이것은 ‘모든 수학이 틀렸다’는 말도, 아직 정의되지 않은 모든 기계의 능력을 판정한 말도 아니다.

1936년

independent comparison

서로 다른 계산 모형이 같은 경계에 닿다

처치의 람다 계산과 같은 시기, 튜링은 사람이 규칙에 따라 기호를 조작하는 과정을 추상 기계로 표현했다. 두 서로 다른 모형이 같은 계산 가능 함수에 이른 사실이 ‘효과적 절차’의 수학을 굳혔다.

1936년–1970년

theorem extension

기계의 정지 문제에서 정수 방정식의 판정 불가능성으로

마티야세비치는 피보나치 수의 지수적 성장을 디오판토스 방정식으로 표현해 줄리아 로빈슨의 남은 가설을 해결했다. 데이비스·퍼트넘·로빈슨의 선행과 합쳐, 임의의 정수계수 다항식에 정수해가 있는지 항상 판정하는 알고리즘은 존재하지 않는다는 힐베르트 열 번째 문제의 부정 해답이 완성됐다. 개별 방정식을 풀 수 없다는 뜻은 아니다.