스탠퍼드대의 Moses Charikar, 코넬대의 Jon Kleinberg, 스탠퍼드대의 Chirag Pabbaraju는 Gold의 언어 식별 모형에서, 문자열마다 끝에 붙는 색 하나만으로도 무엇이 필요한지 살폈다. 대상은 가산한 후보 언어 목록에서 고른 비밀 언어의 열거이며, 학습자는 열거가 진행되는 동안 언어를 추측해 결국 모두 맞혀야 한다. 이 연구는 모든 언어가 무한한 가산 집합에 대해, 문자열당 하나의 말단 비트면 식별이 가능하다고 보였다.
핵심 결과는 두 갈래다. 첫째, 언어 집합 전체, 곧 모든 무한 부분집합에 대해 적용되는 말단 2색 배정이 존재하며, 그 같은 배정으로 임의의 가산 부분계가 식별된다. 둘째, 이런 전역 말단 색칠은 유한한 색 수로는 Borel map으로 정의될 수 없다는 하한이 뒤따른다. 상반되는 점은 기존 trace coloring이 말단 색으로 바꾸면 Borel이지만, 색 수는 무한히 필요하다는 대목이다.
상한 구성은 collection-dependent 2색과 collection-independent 2색으로 나뉜다. 전자는 가산 언어 모음마다 별도로 정해지며 Proposition 4.1에서 보인다. 후자는 모든 무한 부분집합을 포괄하는 Theorem 5로 제시되며, 초한 재귀와 almost-disjoint families를 쓴다. 본문은 이 구성에서 각 언어를 색칠하는 규칙이 집합론적 비구성성을 피하기 어렵다고 설명한다.
하한 쪽에서는 Galvin-Prikry 정리를 사용한다. Borel map으로 주어진 유한 팔레트의 전역 말단 색칠은 finite-prefix coloring으로 정규화될 수 있고, 이로부터 식별 불가능한 가산 부분계가 구성된다고 보인다. Theorem 9는 모든 무한 부분집합의 집합에 대해, 유한 팔레트를 쓰는 어떤 Borel 색칠도 가산 부분계 전체를 식별하게 만들지 못함을 밝힌다. 반면 Theorem 10은 무한 팔레트를 쓰는 Borel 전역 색칠이 가능함을 보인다.
| 분류 | 색 수 | 정의 성격 | 근거 |
|---|---|---|---|
| Collection-dependent | 2 colors | Proposition 4.1 | countable language collection, every |Li| = ∞ |
| Collection-independent | 2 colors | Theorem 5 | all infinite subsets of the universe |
| Constructive (Borel) | infinite color set | Theorem 10 | terminal colorings of [Σ∗]ω via Borel map J : C → ZN |
| Constructive (Borel) | finite palette 불가 | Theorem 9 | no collection-independent finite Borel coloring |
자료: STORIUM 정리
원문 표 1은 결과를 네 칸으로 요약한다. collection-dependent와 collection-independent를 가로축으로, constructive(Borel)과 non-Borel을 세로축으로 두었을 때, collection-dependent constructive는 2색, collection-independent constructive는 infinite color set, collection-independent non-Borel은 2색, collection-independent constructive와 non-Borel의 대비는 Theorem 5와 Theorem 9로 뒷받침된다. 이 논문은 색의 위치, 색 수, 정의의 명시성 사이에 정확한 tradeoff가 있음을 보인다.
저작권자 © STORIUM 무단전재 및 재배포 금지
