기록노트

4-1. 앨런 튜링과 에니그마 더 알아가기 앨런 튜링 1분만에 흝어보기 영국의 수학자, 논리학자. 계산기가 어디까지 논리적으로 작동할 수 있는가에 대하여 처음으로 지적인 실험을 시도한 학자로 유명하며, 제2차 세계대전에서 독일 나치의 암호체계, 에니그마를 풀어내 연합군을 승리에 큰 공헌을 이바지한 사람이다. 컴퓨터공학 및 정보공학의 이론적 토대를 마련해, 오늘 날에는 컴퓨터 공학의 아버지라고 불리는 천재 수학자이기도 하다. 튜링 기계라는 개념을 도입하고 알고리즘의 개념을 공식화하여 컴퓨터공학의 이론적 토대를 마련하였고, 튜링 봄베를 개발하여 훗날의 콜로서스라는 프로그래밍이 가능한 전자 컴퓨터의 기술적 토대를 만들었다. 튜링 테스트라고 불리는 ..

4. 앨런 튜링과 튜링 기계 2.1 기계적 계산의 정의: 튜링기계[ 책 p.31~34 ] 제2차 세계대전에서 독일 나치의 암호체계, 에니그마를 풀어내 연합군을 승리에 큰 공헌을 이바지한 사람이자, 컴퓨터 공학의 아버지라고 불리는 천재 수학자, 앨런 튜링은 괴델의 증명을 단도직입적으로 다시 증명했다. 그는 "기계적인 방식"이 뭔지를 정의내렸고, 그 방식만으로는 모든 사실을 만들 수 없음을 증명했다. 튜링은 다섯 종류의 단순한 기계 부품들을 정의하고 그 부품들로 만든 기계로 돌릴 수 있는 것만을 "기계적인 방식"이라고 정의했다. 그리고 이 방식으로는 절대 돌릴 수 없는 계산 문제를 하나 보여 기계적인 방식으로는 모든 참인 명제를 만들어낼 수 없다는 결론을 이끌어 냈다. 그는 우선 자신이 정의한 "기계적인 방..

3. 괴델의 불완전성 정리 1.5 괴델의 불완전성 정리와 튜링의 증명[ 책 p.27~31 ] 하지만 20세기 수학자들의 원대한 꿈은 1931년, 3년만에 쿠르트 괴델이라는 젊은 수학자에 좌절된다. 그는 다음과 같이 말했다. 진리임에도 증명될 수 없는 수학적 명제가 존재한다. 그는 기계적인 방식만으로는 참인지 거짓인지 판결할 수 없는 명제가 항상 존재한다고 말했다. 즉, 힐베르트가 주장한 "기계적인 방식으로 모든 명제를 만들어내는 것"은 불가능하다는 것이었다. 조금 수학적으로 들어간다면 다비트 힐베르트는 집합론의 공리를 제안했지만, 버트런드 러셀이 러셀의 역리를 발표하며 흔들리게 되고, 쿠르트 괴델에 의해 완전히 좌절되고 만다. 이는 수학들에게 수학기초론의 근본적인 인식에 동의하게 되는 계기를 마련해주어 ..