앨런 튜링 논문 탐방 - 튜링 이전의 배경

1646년 독일에서 태어남
이 당시엔 유클리드 기하학조차 고급 주제였고 대학에서나 가르쳤다
- 유클리드 기하학이란? 좌표를 사용하는 해석기하학과 달리 오로지 공리로 이루어진 기하학
- 다섯 개의 axiom에서 시작해 모든 theorem을 만든다
1673년에 곱셉/나눗셈까지 가능한 사칙연산 기계식 계산기 발명
- 계산을 기계가 대신 하는 것의 중요성 인지
- 논리적 추론을 일종의 계산으로 대체하고 그런 계산을 수행하는 기계를 만드는 게 최종 목표
이 시기에 있었던 중요한 수학적 발견 두 가지
1. 대수학을 표현하고 풀어내는 방법 (지금 고등학교 수준의 대수학)이 체계화됨
2. 데카르트와 페르마가 공간상의 점을 숫자의 쌍으로 표현하면서 기하학을 대수학으로 환원
이 두 가지를 사용해서 풀어나간 문제 중에 하나가 극한
- π / 4 = 1 + 1/3 + 1/5 + 1/7 + ⋯
- 극한에서 미적분학이 탄생. $∫$, $dx$ 이런 류의 기호를 활용하여 수학을 언어처럼 풀어나가는 발상이 이때쯤 생겨난 것

1848년에 태어남
$∀$, $∃$ 기호를 처음으로 만듦
X이면 Y이다 → X ⊇ Y 로 표현하기
불의 논리 체계가 기존의 논리적 추론을 사용해 논리 체계를 만든다는 뭔가 순환적 모순의 여지가 있었다면 프레게는 논리를 개발하는 과정에서 기존의 논리를 사용하지 않고 정확한 문법을 갖춘 인공적인 언어를 만들어냄. 논리적 추론이 기호의 나열이 되었다
최초의 정규화된 가상 언어

칸토어의 연속체 가설

러셀의 역설

1862년에 태어남
1900년 8월에 열렸던 세계 수학자 대회 → 다음 세기의 수학에는 어떤 문제들이 있을 것인가를 논의 → 힐베르트가 23개의 문제를 제시 → 그 중 중요한 것이 2번 문제: 산술의 일관성
산술의 일관성 문제란?
- 힐베르트의 결정 문제로도 불림
- 원래 의도 : 유클리드 기하학의 일관성을 증명해 보자
- 그런데 힐베르트 자신이 기하학 공리들의 일관성 증명을 다른 산술 공리들의 일관성으로 축소하는 증명은 완성했음
- 따라서 산술 체계의 일관성만 증명되면 유클리드 기하학의 일관성도 증명된다
산술의 일관성 문제가 왜 중요한가?
- 자연수 체계에 모순이 없음을 증명하기 위해 자연수 체계를 끌고 오면 안 됨 (1+1=2 라는 걸 증명하기 위해 1+2=3 을 가져오면 아무 의미가 없음)
- 결국 이 문제는 체계 바깥에서 체계를 검증할 수 있는가로 이어진다
- 체계의 일관성이 증명된다면 → 체계 내의 모든 수식은 참 또는 거짓 둘 중 하나임을 확신할 수 있다 → 그럼 모든 수식에 대해 참 거짓을 판별할 수 있는 기계도 만들어 볼 수 있지 않을까? → 라이프니츠의 목표에 도달할 수 있다는 희망

체계 바깥에서 체계를 검증할 수 있는가 → 괴델이 불가능하다고 증명해 줬음
그렇다면 ‘모든 수식에 대해 참 거짓을 판별할 수 있는 기계’도 불가능하다고 증명할 수 있지 않을까?
튜링 기계의 핵심은 우리가 계산이라고 부르는 과정을 분석한 결과 모든 계산이 가능한 것들은 튜링 기계에서 동작하는 알고리즘으로 표현할 수 있다는 사실
그래서 어떤 특정한 문제를 튜링 기계에서 수행할 수 없다고 증명한다면 그러한 문제를 해결하는 알고리즘은 존재하지 않는다고 결론 내릴 수 있음
1936년 발표한 논문 “계산 가능한 수에 대하여, 그리고 결정문제에의 응용” 을 통해 그런 기계는 만들 수 없다고 증명 완료