튜링은 수학적 문제를 풀 수있는 기계를 고안해 내고
이를 '계산가능한 수에 대해서, 수리명제 자동생성 문제에 응용하면서' 라는 논문에서 발표한다.
그래, 바로 '컴퓨터'이다. ( 난 폰으로 보는데? 할 수도 있지만 스맛폰도 엄밀히 따지면 컴퓨터다)
그는 컴퓨터의 원시적 형태인 '튜링머신'을 제시한다.
튜링머신을 구성하는 아이디어 역시 괴델의 증명에서 따왔다.
괴델은 '괴델수'라는 개념을 도입해서 모든 명제를 숫자로 환원시켰다.
가령 1+1=2 는 45234235, 이런식으로 말이다.
컴퓨터는 모든 문제를 0과1로 수식화시켜 계산한다.
이 아이디어 역시 괴델의 아이디어에서 따온것이다.
어찌됐든 튜링은 논문에서 이 기계를 사용하여
컴퓨터가 '무한한 시간이 걸리는 문제'를 어떻게 다룰 지를 연구하였고,
꽤나 김빠지는 대답을 도출한다.
'컴퓨터는 어떤 수학적문제를 푸는데 무한한 시간이 걸리는지 아닌지 일반적으로 파악 조차 할 수 없다!'
더 쉽게 요약하자면
'컴퓨터가 어떤 수학적 문제를 풀 수있는지 없는지 조차 일반적으로 알아낼 수 없다'
이다.
여기서 '일반적'이라는 표현에 주목해야한다.
하나의 프로그램으로 '모든 문제'를 해결하는 상황을 상정한것이다.
개개의 경우에는 풀 수 있는지 없는지 알아낼 수 있다.
가령 위에서 말한 '연속체 가설'의 경우 우리는 풀 수 없음을 증명했다.
튜링이 말하는 computer는 사실 계산하는 인간이었다는 말이있지
일반적이다라는 말의 해석에서 오해를 불러올수있어서 덧붙이면ㅡa라는 문제를 풀수있는 프로그램A가있고 b라는 문제를 풀수있는 프로그램 B가 있으면 두 프로그램을 합친 C를 만들수있음 ㅡC는 a와b 모두 풀수있음ㅡ따라서 모든 문제에대해 개개의 문제를 풀수있는 프로그램이 각각 존재한다면 그 프로그램을 모두 모아 하나의 프로그램 H로 만들수있는데
그런 H가 존재할수 없다는뜻은 곧 문제를 풀수없는 문제가 적어도 하나 존재한다ㅡ괴델의 불완전성정리ㅡ증명불가능한 명제가 적어도 하나 존재한다와 같은거임
조금 다른 문제지만 관련은 많겠지... 결정문제의 본질은 모종의 진술을 입력으로 받았을때 0 or 1을 출력으로 뱉어내는 함수가 항상 존재하는가? 하는 건데
튜링이 이게 불가능한 걸 증명할때 쓴 방법이 기계에 기계의 결정가능성을 결정하도록 하였을때 모순이 나온다는 식이었고 이건 괴델의 불완전성 증명이랑 판박이임
더 충격적인거 볼려면 처치ㅡ튜링 명제 검색해보셈ㅡ모든 기계적 절차는 튜링머신에 포함된다는 강한 주장인데ㅡ이게 인간이 만들어낼수있는 기계를 넘어서 인간 그자체(인간의 뇌)나 우주 까지 확장하면 좀 무서워짐 ㅡ물론 증명이나 반증은 안됨