Rewriting Systems on Arbitrary Monoids

당신은 하나의 것을 다른 것으로 바꾸는 규칙들을 가진 퍼즐을 풀고 있다고 상상해 보세요. 컴퓨터 과학과 수학의 세계에서, 이는 보통 문자열(사전 속의 단어들 같은 것)을 사용하여 수행됩니다. 만약 당신에게 "cat"이라는 단어가 있고 "cat"이 "dog"이 된다는 규칙이 있다면, 당신은 그것들을 바꿀 수 있습니다. 이것이 전통적인 방식인 **문자열 재작성(String Rewriting)**입니다.

하지만 이 논문의 저자인 에두아르도 마갈랴에스(Eduardo Magalhães)는 단순하지만 심오한 질문을 던집니다: 우리가 단순히 단어들만 가지고 놀고 있는 게 아니라면 어떨까? 만약 우리가 숫자, 도형, 혹은 단어처럼 전혀 보이지 않는 추상적인 아이디어들을 가지고 놀고 있다면 어떨까요?

다음은 일상적인 비유를 사용한 이 논문의 주요 아이디어 정리입니다:

1. 문제점: "단어"에 대해 너무 까다로움

전통적으로 재작성 시스템은 **자유 모노이드(Free Monoids)**에서만 작동합니다. 자유 모노이드를 하나의 거대한 빈 창고라고 생각해보세요. 당신은 오직 상자(문자)들을 일렬로 쌓을 수만 있습니다. 당신은 오직 그것들을 서로 붙임으로써 결합할 수 있습니다.

• 문제점: 논문은 이것이 너무 제한적이라고 주장합니다. 이는 마치 벽이 없는 창고 안에서만 가구를 재배치할 수 있다고 말하는 것과 같습니다. 현실 세계(그리고 논리학)에서 우리는 종종 고유한 내부 규칙을 가진 구조들을 다룹니다 (예를 들어, 12 + 1 = 1이 되는 시계, 또는 "앨리스 + 밥"이 그냥 "그룹"이 되는 친구 모임 같은 것들).
• 논리의 간극: 저자는 "자유로운 창고가 된다는 것"이 논리학의 언어로 볼 때 매우 구체적이고 정의하기 어려운 규칙이라는 점을 지적합니다. 만약 당신이 이러한 시스템을 표준적인 논리 도구로 연구하고 싶다면, 시스템 내부에서 "자유롭다"는 것을 쉽게 정의할 수 없기 때문에 난관에 부딪히게 됩니다.

2. 해결책: 모노이드 재작성 시스템 (MRS)

저자는 **모노이드 재작성 시스템(Monoidal Rewriting Systems, MRS)**을 도입합니다.

• 비유: 단순히 선 위에 문자를 배열하는 대신, 당신에게 도구 상자(모노이드)가 있다고 상상해 보세요. 이 도구 상자에는 도구들을 결합하는 특정한 방법(곱셈)이 있습니다.
  • 문자열 시스템에서는 "A"와 "B"를 붙여서 "AB"로 만들 수만 있습니다.
  • MRS에서는 당신의 도구 상자에 있는 규칙을 따른다면, 도구 상자 안의 어떤 두 항목도 결합할 수 있습니다. 아마도 당신의 도구 상자는 더하는 숫자의 집합일 수도 있고, 겹쳐지는 도형의 집합일 수도 있습니다.
• 변화: 논문은 이렇게 말합니다. "모든 것이 단어인 척하는 것을 그만둡시다. 규칙이 그 구조 자체를 직접 다루도록 합시다." 이는 시스템을 더 유연하게 만들고, 그 구조를 설명하는 내부적인 성격을 갖게 합니다.

3. "완벽한" 상태: 노이테리언(Noetherian)과 컨플루언트(Confluent)

어떤 재작성 게임에서든, 당신은 두 가지를 원합니다:

1. 노이테리언 (종결성, Noetherian/Termination): 게임은 결국 끝나야 합니다. 무한히 루프를 돌며 계속해서 무언가를 바꿀 수는 없습니다. (예: "A"를 "B"로 바꾸고, 다시 "B"를 "A"로 바꾸는 규칙이 영원히 반복되어서는 안 됩니다).
2. 컨플루언트 (일관성, Confluent/Consistency): 어떤 순서로 규칙을 적용하더라도, 결국 동일한 최종 결과에 도달해야 합니다. (예: 방이 어질러져 있을 때, 양말을 먼저 치우든 책을 먼저 치우든 상관없이 방이 똑같이 깨끗해져야 합니다).

시스템이 이 두 가지를 모두 갖추면, 당신은 어떤 지저씨러진 입력값으로부터 고유한 "정규형(Normal Form)"(그 대상의 가장 깨끗하고 단순한 버전)으로 환원할 수 있습니다.

4. 거대한 연결고리: "번역가" (Biadjunction)

이 논문은 두 세계 사이에 다리를 놓습니다:

• 세계 A: 지저분하고 규칙이 많은 재작성 시스템(MRS)의 세계.
• 세계 B: 깨끗하고 단순한 모노이드(최종 구조)의 세계.

저자는 양방향으로 작동하는 번역가(수학적 도구인 biadjunction)를 만듭니다:

• 규칙에서 구조로: 만약 당신이 규칙들을 가지고 있다면, 번역가는 그 안에 숨겨진 "깨끗한" 구조(기약 원소들의 모노이드)를 찾아냅니다.
• 구조에서 규칙으로: 만약 당신이 깨끗한 구조(예를 들어 숫자 5)를 가지고 있다면, 번역가는 그것을 생성하는 "표준적인" 규칙 세트를 구축할 수 있습니다.

메타포: 조각상(모노이드)을 상상해 보세요.

• 조각상을 설명하는 한 가지 방법은 "이것은 찰흙으로 만들어졌다"라고 말하는 것입니다. (구조).
• 또 다른 방법은 다음과 같은 지침 목록을 주는 것입니다: "덩어리를 가져와서, 평평하게 펴고, 원형으로 자르고, 가장자리를 매끄럽게 다듬는다." (재작성 시스템).
• 논문은 이 두 가지 묘사가 완벽하게 연결되어 있음을 증명합니다. 당신은 지침으로부터 조각상을 만들 수 있고, 조각상으로부터 다시 최선의 지침 세트로 돌아갈 수 있으며, 이 과정에서 어떤 정보도 잃지 않습니다.

5. "티에체(Tietze)" 변환: 마법 지팡이

마지막으로, 이 논문은 까다로운 질문에 답합니다: "만약 동일한 조각상을 만드는 두 개의 서로 다른 규칙 세트가 있다면, 그것들은 서로 어떻게 연관되어 있을까?"

과거의 문자열 재작성 세계에는 한 규칙 세트를 다른 규칙 세트로 바꿀 수 있는 **티에체 변환(Tietze Transformations)**이라는 유명한 움직임들이 있었습니다. 저자는 이 더 넓은 세계를 위해 **일반화된 기초 티에체 변환(Generalized Elementary Tietze Transformations, GETTs)**을 발명했습니다.

• 비유: 케이크를 만드는 두 가지 서로 다른 레시피가 있다고 상상해 보세요.
  • 레시피 A는 "밀가루, 설탕, 달걀을 섞는다"라고 합니다.
  • 레씨피 B는 "마른 재료를 섞은 다음, 젖은 재료를 섞고, 굽는다"라고 합니다.
  • 단계는 달라 보이지만, 둘 다 똑같은 케이크를 만듭니다.
• 결과: 논문은 동일한 케이크를 만드는 어떠한 유효한 레시피(Noetherian Confluent MRS)라도, 이 "GETT 움직임"들의 연속을 통해 다른 유효한 레시피로 변형될 수 있음을 증명합니다.
  • 움직임 1: 이미 참인 규칙을 추가함 (중복적인 규칙).
  • 움직임 2: 다른 규칙들에 의해 이미 설명되는 규칙을 제거함.
  • 움직임 3: 한 단계를 설명하는 데 도움이 되는 새로운 재료(기호)를 도입함.
  • 움직임 4: 특정 부분에 집중하여 전체 시스템을 단순화하는 복잡한 움직임.

요약

이 논문은 "재작성"(규칙에 따라 무언가를 바꾸는 것)의 개념을 "단어"라는 제약으로부터 해방시킵니다. 이는 다음을 보여줍니다:

1. 당신은 단지 문자열뿐만 아니라 어떠한 수학적 구조에서도 이를 수행할 수 있습니다.
2. 규칙과 결과 사이에는 완벽한 논리적 다리가 존재합니다.
3. 동일한 결과를 만들어내는 어떤 두 규칙 세트라도, 특정한 보편적 움직임을 사용하여 서로 변형될 수 있습니다.

이는 마치 집을 설명할 때 벽돌(문자열)을 나열하는 방법도 있지만, 건축 설계도(모노이드)로도 설명할 수 있다는 것을 깨닫는 것과 같습니다. 그리고 모든 설계도는 그것을 짓기 위한 고유하고 완벽한 지침을 가지고 있으며, 모든 지침은 고유한 설계도로 이어진다는 것을 수학적으로 증명할 수 있다는 것과 같습니다.