News·19시간 전
거의-계산 가능한 모델: 모든 재귀적 열거 가능 1차 이론에 대한 구성
LessWrong 에 게재된 게시물에서, 모든 일관된 재귀적 열거 가능 1차 이론이 '거의-계산 가능한' 모델을 가짐을 보입니다. 이 모델은 프로그램이 이전 출력을 번복할 수 있지만, 각 유한 부분 집합에 대해 최종적으로 수렴하도록 허용합니다. 집합론의 공리(예: 공집합 공리)를 예시로 들어 구성 방법을 설명합니다.
모든 일관된 재귀적 열거 가능 1차 이론은 '거의-계산 가능한' 모델을 가지며, 이 게시물은 그 프로그래밍 방법을 보여줍니다.
골자
- 정의 — 거의-계산 가능한 모델은 프로그램이 출력을 번복할 수 있지만, 각 유한 단계에서 결국 수렴하는 모델입니다.
- 결과 — 모든 일관된 재귀적 열거 가능 1차 이론은 이러한 모델을 가집니다.
- 구성 — 집합론의 공리(예: 공집합 공리)를 사용하여 구체적인 구성 방법을 설명합니다.
배경·맥락
- 실용적인 1차 이론 대부분은 계산 가능한 모델이 없지만, 이 정의를 완화하면 모든 재귀적 열거 가능 이론이 모델을 가집니다.
- 언어 — 집합론 언어는 등호 없이 이진 술어 E 만 사용하며, 모델은 자연수의 부분 집합 위에 정의됩니다.
자금 용처·향후
- 일반화 — 이 접근법은 등호가 있는 임의의 재귀적 열거 가능 1차 이론으로 확장 가능합니다.
- 의의 — 계산 가능성 이론과 모형 이론의 교차점에서 흥미로운 결과입니다.
편집자 한 줄
LessWrong 의 기술적 게시물로, 수리논리학에 관심 있는 독자에게 적합합니다.
- #computability
- #first-order-logic
- #model-theory
- #set-theory
LessWrong