두 가지 증거 모두 대각선 인수를 사용하기 때문에 셀 수없는 무한 세트의 존재와 중지 문제의 결정 불가능 사이에 모호한 연결이 있는지 궁금합니다. 모든 세트가 계산 가능한 경우 정지 문제를 결정할 수 있습니까?
답변
그것은 숨겨진 링크가 아니라 범주 이론의 언어를 사용하여 명시 적으로 만들어졌으며 질문하고 연구해야 할 매우 자연스러운 질문입니다. 주제에 대한 자료가 상당히 있습니다.
- 같은 것을 요구하는 CS 이론 질문
- 고정 소수점 정리와 캔터 정리에 대한 Andrej Bauer의 블로그 게시물 .
- 자기 참조 역설, 불완전 성 및 고정 점에 대한 보편적 접근 , Noson Yanofsky, 2003. 아래의 Lawvere 논문에 대해 부드럽게 소개합니다.
- 대각선 주장과 데카르트 종결 범주 , F. William Lawvere, 1969 년 기사를 출판하여 이러한 연결을 정확하게한다.
- 존 벨 (John Bell), 일반 환경에서의 불완전 성
- Lawvere에서 Brandenburger-Keisler까지 : 대화식 대각선 화 및 자기 참조 , Samson Abramsky 및 Jonathan Zvesper, 2010. Lawvere 논쟁을 게임 이론 불가능한 결과로 확장.