유니코드의 음역 규칙이 튜링 완전하다는 사실이 밝혀졌다

Unicode's transliteration rules are Turing-complete

유니코드의 음역 규칙이 튜링 완전하다는 사실이 밝혀졌다

Nicolas Seriot이 유니코드의 음역(transliteration) 규칙(UTS #35)이 튜링 완전(Turing-complete)함을 증명했다. 이 규칙은 ICU 라이브러리에 포함된 로케일 데이터로, 대부분의 운영체제와 브라우저, 런타임에 탑재되어 있다. 그는 2-tag 시스템을 규칙으로 컴파일하여 Collatz 함수, Rule 110, 소수 생성 셀룰러 오토마타를 구현했다. 이는 규칙 파일이 단순한 데이터가 아닌 프로그램임을 의미하며, 외부에서 규칙을 받을 때는 코드로 간주하고 검토해야 함을 시사한다.

놀라운 점은 이 보편성(universality)이 모든 운영체제에 포함된 로케일 파일용 데이터 포맷에 존재하며, 그 사양에는 그러한 가능성이 언급조차 되어 있지 않다는 것이다.

이 날의 다른 글

2026-07-09