결정문제'결정 문제'란 모든 수학적 명제에 대해 참인지 거짓인지를 유한 시간내에 판별할 수 있는 일반적인 절차, 즉 알고리즘이 존재하는지를 묻는 것이었습니다. 이 문제를 처음 제기한 힐베르트는 이러한 알고리즘이 존재할 것이라 기대했습니다. 1920년대에는 수학적 엄밀성에 대한 열정이 고조되어 있었고, 수학적 진리를 탐구하는 강력한 체계들이 속속 등장하고 있었기 때문입니다. 힐베르트는 수학이 충분히 강력하다면, 모든 문제에 대해 확실한 답을 구할 수 있을 것이라 보았던 것입니다.하지만 10년이 채 지나지 않은 1936년, 영국의 젊은 수학자 앨런 튜링은 '계산 가능한 수와 결정 문제에 관한 적용에 관하여'라는 논문을 통해 모든 수학적 명제를 증명하거나 반증할 수 있는 하나의 보편적인 절차, 즉 알고리즘이 ..
On Non-Computable Functions 이 논문에서 제시하는 계산 불가능한 함수의 구성은 유한하고 비어 있지 않은 음이 아닌 정수 집합에는 가장 큰 원소가 존재한다는 원칙에 기초하고 있다. 또한 이 원칙은 현재 기준으로 매우 명확하게 정의된 집합에 대해서만 사용된다. 계산 가능한 함수의 나열을 사용하지 않으므로, 이 구성에서 대각선화 방법(diagonal process)을 사용하지 않는다. 따라서 모든 수학 분야에서 자명하게 여겨지는 원칙이 비구성적 존재를 도출해낸다는 사실이 흥미롭다. I. 서론이 논문의 목적은 몇 가지 매우 간단한 계산 불가능한 함수의 예를 제시하는 것이다. 이러한 예들은 단순함을 넘어서 중요한 점을 조명해준다. 함수
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 "바쁜 비버" 게임의 목표는 가장 오래 실행되는..
Amateur Mathematicians Find Fifth ‘Busy Beaver’ Turing Machine | Quanta Magazine Amateur Mathematicians Find Fifth ‘Busy Beaver’ Turing Machine | Quanta MagazineAfter decades of uncertainty, a motley team of programmers has proved precisely how complicated simple computer programs can get.www.quantamagazine.org단순한 프로그램이 얼마나 복잡해질 수 있는지, 이제 연구자들이 그 비밀에 다가섰습니다. 약 40년 전, 독일 서부 도시 도르트문트에 수많은 컴퓨터 과학자들..