앨런 튜링
기계가 계산할 수 없는 것도 있을까?
그때 그곳
괴델이 힐베르트의 계획을 무너뜨린 뒤에도 물음 하나가 남아 있었습니다.
어떤 수학 명제가 참인지 거짓인지를, 생각하지 않고 규칙만 따라서 판정하는 절차가 있는가. 힐베르트는 이것을 결정문제라 불렀습니다.
왜 이 질문이었나
이 물음에 답하려면 먼저 정해야 할 것이 있었습니다. 규칙만 따르는 절차란 대체 무엇인가.
튜링은 사람이 종이와 연필로 계산하는 모습을 지켜보고 그것을 극단적으로 단순하게 만들었습니다. 칸이 그어진 긴 종이테이프. 한 칸을 읽고 쓰고 좌우로 한 칸 움직이는 장치. 유한한 개수의 규칙표. 그리고 지금 어떤 상태인지를 나타내는 표시.
이것뿐입니다.
알아낸 것
이 단순한 기계가 사람이 종이와 연필로 할 수 있는 모든 계산을 할 수 있습니다.
그리고 결정적인 대목이 여기입니다. 기계의 규칙표 자체를 기호로 바꿔 테이프에 적을 수 있습니다. 그러면 테이프에 적힌 규칙표를 읽고 그 기계를 그대로 흉내 내는 기계를 만들 수 있습니다. 어떤 기계든 될 수 있는 하나의 기계. 오늘날 우리가 컴퓨터라 부르는 것의 개념입니다.
그다음 그는 이 기계로도 풀 수 없는 문제를 만들어 보였습니다. 어떤 프로그램이 언젠가 멈출지 아니면 영원히 돌지를 미리 판정하는 프로그램은 존재할 수 없다는 것입니다. 괴델과 똑같은 자기지시 논법이었습니다.
힐베르트의 물음에 대한 답은 아니오였습니다.
충분히 영리한 절차를 만들면 무엇이든 판정할 수 있다
자기 자신을 가리키게 만들어 모순을 이끌어낸 정지 문제 증명
2차대전 중 그는 블레츨리 파크에서 독일군 암호를 해독합니다. 1952년 동성애로 유죄 판결을 받아 화학적 거세를 당했고 2년 뒤 세상을 떠났습니다. 영국 정부의 공식 사과는 2009년, 왕실의 사후 사면은 2013년이었습니다