기타 썸네일형 리스트형 튜링의 불완전성 정리 증명 ※ 혼자 공부한 내용을 정리한 글입니다. 엄밀한 내용이 궁금하다면 참고 문헌을 읽어 보길 권합니다. 1. 불완전성 정리란? 힐베르트는 수학 체계가 완전하다고 믿었다. 즉 모든 참인 증명은 수학 체계의 공리에서 유도될 수 있으며 따라서 공리에서부터 출발하여 모든 참인 증명을 기계적으로 만들 수 있다고 여겼다. 하지만 괴델이 자연수의 체계에 대해 자연수 체계 속에서 증명될 수 없지만 체계 외부에서 보면 참인 명제가 존재한다는 것을 증명했으며, 이를 불완전성 정리라고 한다. 간략한 증명 방법은 다음과 같다. G = G는 증명불가능하다. 이러한 명제 G가 존재한다고 가정하자. 명제 G는 거짓일 수 없으므로 참이지만 증명불가능한 명제가 되며, 곧 공리계의 불완전성을 의미한다. 위 명제는 명제 속에서 자기 자신을 .. 더보기 제 4회 천하제일 코딩대회 본선 후기 몇 시간 전(2020년 12월 22일 7시) 제 4회 천하제일 코딩대회가 끝났습니다. 2학년 선배 두 분과 팀을 이뤄 참여했고, 11문제 중 5문제를 풀고 전체 4위로 동상을 받았습니다. 원래 오프라인에서 진행되는 대회이지만 코로나19 상황이 악화되어 온라인으로 진행되었습니다. 팀원과는 디스코드로 소통했고, 부정행위 방지를 위해서인지 대회가 끝날 때까지 계속 캠을 켜고 화면도 공유해야 했습니다. 오프라인 행사를 기대했던 저는 아쉬움이 남았지만, 현재 상황에서 취할 수 있는 최선의 방법이었다고 생각합니다. 시작이 10분 연기되었던 점만 빼면 대회는 전반적으로 원활하게 진행되었습니다. 처음에 디스코드 방으로 들어가니 딜레이가 너무 심하고, 마이크도 잘 되지 않는 것 같아 당황했습니다. 다행히 시간이 지나자 .. 더보기 이전 1 다음
