서수형 기반의 로직 시스템

Systems of Logic Based on Ordinals

서수수를 기초로 한 논리학 체계는 수학자 앨런 튜링의 박사학위 논문이었다.[1][2]

튜링의 논문은 새로운 형태의 형식논리에 관한 것도 아니고, 상대적 진실성에 근거하여 진리 상태 간에 비교가 이루어질 수 있는 서수나 상대적 번호 부여에서 파생된 이른바 '순위 논리' 시스템에도 관심이 없었다.대신 튜링은 칸토르의 인피나이트 방법을 이용해 고델리아 불완전성 상태를 해결할 가능성을 조사했다.따라서 이 조건은 명시될 수 있다. 즉, 공리의 집합이 유한한 모든 시스템에서, 배타적 또는 조건은 표현력 및 입증력에 적용된다. 즉, 사람은 힘을 가질 수 있고 증거도 없고 힘도 없으나 둘 다 가질 수 없다.

이 논문은 괴델의 정리 이후 형식적인 수학 체계를 탐구한 것이다.괴델은 산수를 나타낼 만큼 강력한 형식 시스템 S가 있다는 것을 보여주었는데, 사실이지만 시스템은 증명할 수 없는 정리 G가 있다.G는 증명 대신에 시스템에 추가 공리로 추가될 수 있다.그러나 이것은 그 자체로 증명할 수 없는 참 정리 G' 등을 가진 새로운 시스템 S'를 만들 것이다.튜링의 논문은 단순히 이 과정을 반복해서 반복하면서, 원론적인 이론에 추가할 무한대의 새로운 공리들을 만들어 내고, 심지어 한 걸음 더 나아가서 트랜스피나이트 재귀들을 사용하여 "무한을 지나쳐" 가는 새로운 이론들n G, 각각의 서수 n에 하나씩을 산출하게 되면 어떤 일이 일어나는지 살펴본다.

이 논문은 알론조 교회 휘하의 프린스턴에서 완성되었으며 서수 논리 개념을 도입한 수학의 고전 작품이었다.[3]

마틴 데이비스는 튜링의 컴퓨팅 오라클 사용이 논문의 주요 초점은 아니지만, 다항 시간 계층 구조와 같은 이론 컴퓨터 과학에 큰 영향을 미친다는 것이 입증되었다고 말한다.[4]

참조

  1. ^ Turing, Alan (1938). Systems of Logic Based on Ordinals (PhD thesis). Princeton University. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. ProQuest 301792588.
  2. ^ Turing, A. M. (1939). "Systems of Logic Based on Ordinals". Proceedings of the London Mathematical Society: 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3.
  3. ^ 솔로몬 페퍼먼, 롤프 헤르켄 1995 ISBN 3-211-82637-8페이지 111페이지의 "유니버설 튜링 머신: 반세기 조사"에서 O(z)의 땅의 튜링
  4. ^ 세티모 터미 2006 ISBN 88-470-0320-2페이지 63-66[1]에 의해 편집된 상상력과 엄격함에 있어서 마틴 데이비스 "컴퓨팅 능력, 계산 및 현실 세계"

외부 링크


Stub icon

이 수학적 논리 관련 논문은 단조롭다.위키피디아를 확장하여 도울 수 있다.

Stub icon

수학적인 출판물에 관한 이 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.