튜링불완전 편집하기
최신판 | 당신의 편집 | ||
2번째 줄: | 2번째 줄: | ||
==역사와 배경== | ==역사와 배경== | ||
− | |||
− | |||
*수학이 직관과 상식을 벗어나 형식화, 추상화되면서, 체계의 근거로 사용되는 공준의 집합체가 내적으로 모순되지 않고, 따라서 "공준에서 서로 모순되는 정리가 추론되는 경우는 없는가"라는 무모순성의 문제가 제기되었는데 형식적인 수학에서는 '진리'와 '증명가능성'의 개념이 구별되어 쓰인다. 즉, 한 공리 체계에서 연역적으로 어떤 정리를 도출할 수 있으면 그 정리는 증명가능한 것인데, 그 체계 내에서 거짓임을 증명할 수 없는 어떤 진술이 항상 참임을 증명할 수 있다는 보장은 하지 않는다. | *수학이 직관과 상식을 벗어나 형식화, 추상화되면서, 체계의 근거로 사용되는 공준의 집합체가 내적으로 모순되지 않고, 따라서 "공준에서 서로 모순되는 정리가 추론되는 경우는 없는가"라는 무모순성의 문제가 제기되었는데 형식적인 수학에서는 '진리'와 '증명가능성'의 개념이 구별되어 쓰인다. 즉, 한 공리 체계에서 연역적으로 어떤 정리를 도출할 수 있으면 그 정리는 증명가능한 것인데, 그 체계 내에서 거짓임을 증명할 수 없는 어떤 진술이 항상 참임을 증명할 수 있다는 보장은 하지 않는다. | ||
− | |||
*1931년, [[괴델]]은 20대의 나이에 학계를 깜짝 놀라게 한 세기적 결과인 불완전성 정리를 발표,‘진리임에도 증명될 수 없는 수학적 [[명제]]가 존재한다’는 것이다.그의 정리는 제일, 제이 불완전성 정리들로 나눠진다. 제일 [[불완전성 정리]]는 대략적으로 서술하면, 수학에서는 증명도 부정도 되지 않는 명제가 반드시 존재한다는 것이다.그는 [[칸토어]]의 연속체의 가설이 수학에서 ‘부정되지 않는 명제’임을 증명하는데 성공한다. 그 후 1960년대에 와 비로소 코헨(Paul J. Cohen)이란 젊은 수학자에 의해 연속체 가설이 ‘증명도 되지 않는 명제’임이 밝혀짐으로 연속체 가설 문제의 종지부가 찍힌다.제이 불완전성 정리는 더욱 놀랍다. 수학을 전개하는 근본 공리를 선정해 그 체계가 정말 모순이 없다면, 그 모순이 없다는 사실 자체는 (그 체계의 논리전개로는) 증명을 할 수 없다는 것이다. 괴델의 정리는 힐베르트나 그 이전 수학자들이, ‘우리가 알고자 하는 수학적 문제들은 결국 진리이거나 거짓으로 판명 또는 증명될 것이라’는 당연하다고 여겼던 믿음이 옳지 않다는 것이다. 이는 인간 인식을 형식화 또는 기계화하는 것에 근본적인 한계가 있음을 매우 분명하게 보여준 하나의 세기적 사건이었다.제일, 제이 정리를 한마디로 요약하면, ‘진리이나 증명되지 않는 수학적 명제가 존재한다’이다. 제이 정리의 경우, 방금 살핀 것과 같이, ‘수학에 모순이 없다’는 명제 자체는[[진리]]여야 함에도, 증명될 수 없다는 것이다. 제일 정리의 경우도, 수학에서 증명도 반증도 되지 않는 명제는, 플라톤적 관점에서 그 자신 또는 자신의 부정명제 둘 중 하나는 참일 수밖에 없으나, 어느 것도 증명되지 않는다.괴델은 참인 수학적 명제들의 범위가, 인간이 궁극적으로 증명의 방법을 통해 참으로 확인해 인식할 수 있는 명제들의 범위를 넘어선 것을 보인 것이다. 이를 위해 우선 `인간이 참으로 인식 또는 증명할 수 있는 명제'들의 범위를 규정하기 위해 `계산 가능하다'는 개념을 최초로 제안하게 된다.후에 [[앨런 튜링]]과 후대 학자들에 의해 정의가 확장 보강되고, 튜링은 그렇다면 기계적 [[프로그램]]으로 `계산 가능하다는 개념'을 실행하는 장치를 만들 수 있지 않을까 생각했고, 실제 컴퓨터를 설계하기에 이른 것이다. <ref>〈[https://terms.naver.com/entry.nhn?docId=3570783&cid=58944&categoryId=58970 괴델의 불완전성 정리]〉, 《네이버 지식백과》</ref> | *1931년, [[괴델]]은 20대의 나이에 학계를 깜짝 놀라게 한 세기적 결과인 불완전성 정리를 발표,‘진리임에도 증명될 수 없는 수학적 [[명제]]가 존재한다’는 것이다.그의 정리는 제일, 제이 불완전성 정리들로 나눠진다. 제일 [[불완전성 정리]]는 대략적으로 서술하면, 수학에서는 증명도 부정도 되지 않는 명제가 반드시 존재한다는 것이다.그는 [[칸토어]]의 연속체의 가설이 수학에서 ‘부정되지 않는 명제’임을 증명하는데 성공한다. 그 후 1960년대에 와 비로소 코헨(Paul J. Cohen)이란 젊은 수학자에 의해 연속체 가설이 ‘증명도 되지 않는 명제’임이 밝혀짐으로 연속체 가설 문제의 종지부가 찍힌다.제이 불완전성 정리는 더욱 놀랍다. 수학을 전개하는 근본 공리를 선정해 그 체계가 정말 모순이 없다면, 그 모순이 없다는 사실 자체는 (그 체계의 논리전개로는) 증명을 할 수 없다는 것이다. 괴델의 정리는 힐베르트나 그 이전 수학자들이, ‘우리가 알고자 하는 수학적 문제들은 결국 진리이거나 거짓으로 판명 또는 증명될 것이라’는 당연하다고 여겼던 믿음이 옳지 않다는 것이다. 이는 인간 인식을 형식화 또는 기계화하는 것에 근본적인 한계가 있음을 매우 분명하게 보여준 하나의 세기적 사건이었다.제일, 제이 정리를 한마디로 요약하면, ‘진리이나 증명되지 않는 수학적 명제가 존재한다’이다. 제이 정리의 경우, 방금 살핀 것과 같이, ‘수학에 모순이 없다’는 명제 자체는[[진리]]여야 함에도, 증명될 수 없다는 것이다. 제일 정리의 경우도, 수학에서 증명도 반증도 되지 않는 명제는, 플라톤적 관점에서 그 자신 또는 자신의 부정명제 둘 중 하나는 참일 수밖에 없으나, 어느 것도 증명되지 않는다.괴델은 참인 수학적 명제들의 범위가, 인간이 궁극적으로 증명의 방법을 통해 참으로 확인해 인식할 수 있는 명제들의 범위를 넘어선 것을 보인 것이다. 이를 위해 우선 `인간이 참으로 인식 또는 증명할 수 있는 명제'들의 범위를 규정하기 위해 `계산 가능하다'는 개념을 최초로 제안하게 된다.후에 [[앨런 튜링]]과 후대 학자들에 의해 정의가 확장 보강되고, 튜링은 그렇다면 기계적 [[프로그램]]으로 `계산 가능하다는 개념'을 실행하는 장치를 만들 수 있지 않을까 생각했고, 실제 컴퓨터를 설계하기에 이른 것이다. <ref>〈[https://terms.naver.com/entry.nhn?docId=3570783&cid=58944&categoryId=58970 괴델의 불완전성 정리]〉, 《네이버 지식백과》</ref> | ||