결정문제'결정 문제'란 모든 수학적 명제에 대해 참인지 거짓인지를 유한 시간내에 판별할 수 있는 일반적인 절차, 즉 알고리즘이 존재하는지를 묻는 것이었습니다. 이 문제를 처음 제기한 힐베르트는 이러한 알고리즘이 존재할 것이라 기대했습니다. 1920년대에는 수학적 엄밀성에 대한 열정이 고조되어 있었고, 수학적 진리를 탐구하는 강력한 체계들이 속속 등장하고 있었기 때문입니다. 힐베르트는 수학이 충분히 강력하다면, 모든 문제에 대해 확실한 답을 구할 수 있을 것이라 보았던 것입니다.하지만 10년이 채 지나지 않은 1936년, 영국의 젊은 수학자 앨런 튜링은 '계산 가능한 수와 결정 문제에 관한 적용에 관하여'라는 논문을 통해 모든 수학적 명제를 증명하거나 반증할 수 있는 하나의 보편적인 절차, 즉 알고리즘이 ..

How the Slowest Computer Programs Illuminate Math’s Fundamental Limits | Quanta Magazine How the Slowest Computer Programs Illuminate Math’s Fundamental LimitsThe goal of the “busy beaver” game is to find the longest-running computer program. Its pursuit has surprising connections to some of the most profound questions and concepts in mathematics.www.quantamagazine.org "바쁜 비버" 게임의 목표는 가장 오래 실행되는..

최근 수십년간 컴퓨터에 의한 수학 이론의 발견과 증명에 학자들 뿐만 아니라 일반인까지도 많은 관심을 가졌다. 컴퓨터가 증명한 수학문제들을 먼저 알아보고 이러한 컴퓨터의 발전이 현대 수학에 미치는 영향에 대해 생각해보자 . 컴퓨터에 의한 증명 컴퓨터에 의한 증명 중 제일 유명한 것은 4색문제일 것 같다. 1852년 영국의 수학자 프랜시스 구트리에는 영국 지도를 색칠하다 한 가지 물음을 갖게 된다. 임의의 구획으로 나뉜 지도를 색칠할 때 인접한 구획을 같은 색으로 칠하지 않으려면 최소한 몇 가지의 색이 필요할까? 실제로 색을 칠해보니 영국의 지도는 네 가지 색이면 충분하게 색칠 되었다. 그런데 그는 왜 그렇게 되는지 알 수는 없었다. 이 문제는 '4색 문제'라고 불리며 수수께끼로 남았고 100년이 넘는 시간..