계산 가능한 차원의 "나열 가능한"구조가 있습니까? $\omega$?
말하는 그 (셀 수, 계산 가능한 언어) 구조$\mathfrak{A}$이 계산 가능한 차원을$\omega$ 계산 가능한 복사본이 무한히 많다면 $\mathfrak{A}$계산 가능한 동형까지. 이러한 구조의 가장 간단한 예는 아마도 선형 순서 일 것입니다.$\mathfrak{O}=(\omega;<)$.
지금 $\mathfrak{O}$-그리고 내가 아는 모든 "자연적인"구조는 일종의 "생산성"조건을 만족합니다. 여기서 계산 가능한 복사본의 계산 가능한 시퀀스가 주어지면 계산 가능한 새로운 복사본을 계산 가능하게 생성 할 수 있습니다. 순서. 반면에 계산 가능한 차원을 가진 인공 구조가 더 많이 있습니다.$\omega$무한한 계산 가능한 사본이 전혀 존재하지 않으므로 생산성이 저하됩니다. (자세한 내용은 여기 를 참조 하십시오 .)
세 번째 극단적 인 행동이 발생할 수 있는지에 관심이 있습니다. 구조가$\mathfrak{A}$이다 listable 의 계산 가능한 사본의 일부 계산 가능한 순서가 IFF에$\mathfrak{A}$ 모든 계산 가능한 사본 $\mathfrak{A}$그 사본 중 하나에 대해 계산 가능하게 동형입니다. 등재 가능성은 이전 단락에서 언급 한 두 가지 행동 모두와 분명히 모순됩니다.
계산 가능한 차원이있는 나열 가능한 구조가 있습니까? $\omega$?
답변
예. Hirschfeldt와 Khoussainov 는 그러한 구조를 만들었습니다. 섹션 3의 시작 부분, 1208 페이지를 참조하십시오. 실제로 이들 목록은 주입 적입니다 (동등한 클래스 모듈로 계산 가능한 동형). 흥미롭게도 그들은 "효과적으로 무한 계산 가능한 차원"이라고 부르지 만 생산적인 구조에 대한 아이디어도 고려합니다. 1200 페이지를 참조하십시오.