단어 문제(수학)

계산 수학에서 단어 문제는 주어진 두 개의 표현이 일련의 정체성을 다시 쓰는 것과 동일한지 여부를 결정하는 문제다.대표적인 예가 그룹의 문제라는 단어 문제지만, 다른 사례도 많다.계산 이론의 깊은 결과는 이 질문에 대답하는 것은 많은 중요한 경우에서 이해할 수 없는 것이라는 것이다.^[1]

배경과 동기

컴퓨터 대수학에서 사람들은 종종 표현 트리를 사용하여 수학적인 표현들을 인코딩하기를 원한다.그러나 여러 개의 등가 표현 트리가 있는 경우가 많다.그 질문은 자연스럽게 두 개의 표현으로 주어진, 그것들이 같은 요소를 나타내는지를 결정하는 알고리즘이 있는지 여부에 대해 발생한다.그러한 알고리즘을 단어 문제의 해결책이라고 한다.예를 들어 $x{\displaystyle }$, ${\displaystyle y}$, ${\displaystyle z}$ ${\displaystyle$ x$,$${\displaystyle y}$$,z}$이(가) 실제 숫자를 나타내는 기호라고 상상해$$ 보십시오. 그러면 입력$({\displaystyle x}$ ${\displaystyle \cdot }$ y${\displaystyle }$)${\displaystyle }$/ z${\displaystyle \stackrel{}{}}$=${\displaystyle \stackrel{}{}}$? (${\displaystyle x}$/ ${\displaystyle z}$) ${\displaystyle \cdot }$ ${\displaystyle y}$ ${\displaystyle (x\cdot$ y$)/z\mathrel {\overset {?$$}}{=}(x/z)\cdot$ y$\},$ 출력 생성EQUAL, 그리고 유사하게 생산하다NOT_EQUAL${\displaystyle from}{\displaystyle }$( ${\displaystyle x}$ ${\displaystyle \cdot }$ y${\displaystyle }$)${\displaystyle }$/ z${\displaystyle \stackrel{}{}}$=${\displaystyle \stackrel{}{}}$? (${\displaystyle }$x${\displaystyle }$/ ${\displaystyle x}$) ${\displaystyle \cdot }$ ${\displaystyle y}$ ${\displaystyle (x\cdot$ y$)/z\mathrel {\overset {?$$}}{=}(x/x)\cdot y}$.

단어 문제에 대한 가장 직접적인 해결책은 표현의 동등성 등급의 모든 요소를 정상 형태라고 알려진 단일 인코딩에 매핑하는 정상 형태 정리 및 알고리즘의 형태를 취하는데, 이 단어 문제는 통사적 평등을 통해 이러한 정상 형태를 비교함으로써 해결된다.^[1]For example one might decide that ${\displaystyle x\cdot y\cdot z^{-1}}$ is the normal form of ${\displaystyle (x\cdot y)/z}$, ${\displaystyle (x/z)\cdot y}$, and ${\displaystyle (y/z)\cdot x}$, and devise a transformation system to rewrite those expressions모든 동등한 표현이 동일한 정상적인 형태로 다시 쓰여질 것이라는 것을 증명하는 과정에서.^[2]그러나 문제라는 단어에 대한 모든 해법이 정상적인 형태 정리를 사용하는 것은 아니다 - 알고리즘의 존재를 간접적으로 암시하는 대수학적 특성이 있다.^[1]

단어 문제에서는 상수를 포함하는 두 개의 용어가 동일한지 여부를 묻는 반면, 통일 문제로 알려진 단어 문제의 적절한 확장(예: 방정식 해결 문제)에서는 변수를 포함하는 두 용어의 인스턴스(instance)가 동일한지 여부를 질문한다.${\displaystyle \mathrm{일반적}}$인 예로 $2{\displaystyle \mathrm{}}$+ 3${\displaystyle \stackrel{}{}}$=${\displaystyle \stackrel{}{}}$? ${\displaystyle \stackrel{}{}\mathrm{}}$+${\displaystyle }$(${\displaystyle }$- ${\displaystyle 3}$) ${\$디스플레이 $스타일 2+3{\stackrel {?$$}}{=}8+(-3)}$은 정수 그룹 ℤ의 단어 문제인$$ 반면, ${\displaystyle 2}$+ x${\displaystyle \stackrel{}{}}$=${\displaystyle \stackrel{}{}}$? ${\displaystyle \stackrel{}{}\mathrm{}}$+${\displaystyle }$(${\displaystyle }$- ${\displaystyle x}$) ${\displaystyle 2+x{\stackrel {?$$}}{=}8+(-x)}$은 같은 그룹의 통일 문제인데$$, 이전의 용어는 ℤ에서 같기 때문에 후자 문제는 해결책으로${\displaystyle }${${\displaystyle x}$ ${\displaystyle \mapsto }$ ${\displaystyle 3\}}$ ${\displaystyle \{x\mapsto$ 3$\}}}$을(를) 대체한다.대체는 부분적인 순서로 주문할 수 있으므로 통일은 격자 위에서 결합을 찾는 행위다.^{[clarification needed]}이런 의미에서 격자 위의 문제라는 단어에는 해답이 있는데, 즉 모든 등가어 집합은 자유 격자다.^{[clarification needed]}

역사

단어 문제의 가장 깊이 연구된 사례 중 하나는 세미그룹과 그룹 이론이다.노비코프-보네 정리 관련 논문 연대표는 다음과 같다.^[3][4]

• 1911년 (1911년) : 막스 딘은 정확하게 제시된 그룹에게 문제를 제기한다.^[5]
• 1912 (1912):딘은 딘의 알고리즘을 제시하며, 2보다 크거나 같은 속들의 폐쇄적 방향성 2차원 다지관의 기본 그룹에 대한 단어 문제를 해결한다는 것을 증명한다.^[6] 후속 저자들은 그것을 광범위한 그룹 이론적 의사결정 문제로 크게 확대시켰다.^[7][8][9]
• 1914 (1914):악셀 투는 정확하게 제시된 세미그룹들에게 문제를 제기한다.^[10] 더 일반적인 문제에 대한 1910년 논문에서 Thue는 "가장 일반적인 경우 이 문제의 해결책은 아마도 극복하기 어려운 어려움과 연관되어 있을 것이다"라고 말한다.^[11]
• 1930 (1930) – 1938 (1938):Church-Turing 논문이 등장하여 계산성과 불후의 공식 개념을 정의한다.^[12]
• 1947 (1947):에밀 포스트와 안드레이 마르코프 주니어는 독립적으로 해석할 수 없는 단어 문제가 있는 제시된 세미그룹을 구성한다.^[13][14] Post의 건설은 Turing 기계에 구축되어 있는 반면 Markovs는 Post의 일반 시스템을 사용한다.^[3]
• 1950 (1950):Alan Turing은 취소 세미그룹에 대한 문제가 Post의 건설을 더 진행시킴으로써 해결할 수 없다는 것을 보여준다.^[15] 그 증거는 따르기는 어렵지만, 집단에게 단어 문제의 전환점을 제공한다.^{[3]: 342}
• 1955 (1955):표트르 노비코프는 튜링의 취소 세미그룹 결과를 이용해 그룹들의 단어 문제를 해결할 수 없다는 것을 처음으로 공표한 증거를 제시한다.^{[16][3]: 354} 그 증거에는 브리튼의 보조정리기에 해당하는 "교장 보조정리"가 들어 있다.^{[3]: 355}
• 1954 (1954) – 1957 (1957):윌리엄 분(William Boone)은 독립적으로 포스트의 세미그룹 구성을 사용하여 그룹의 문제라는 단어를 해결할 수 없다는 것을 보여준다.^[17][18]
• 1957 (1957) – 1958 (1958):존 브리튼은 튜링의 취소 세미그룹 결과와 브리튼의 초기 작품 일부를 근거로 그룹들의 단어 문제가 해결 불가능하다는 또 다른 증거를 제시한다.^[19] 브리튼의 리마(Lema)^{[3]: 355} 의 초기 버전의 보조정리기가 등장한다.
• 1958 (1958) – 1959 (1959):분씨는 그의 건축물의 간략화된 버전을 출판한다.^[20][21]
• 1961 (1961):그레이엄 히그먼은 히그만의 내재적 정리로 정교하게 제시된 집단의 하위그룹을 특징짓고,^[22] 재귀이론과 그룹이론을 예기치 않은 방식으로 연결하고, 단어 문제의 불능성에 대한 아주 다른 증거를 제시한다.^[3]
• 1961 (1961) – 1963 (1963):브리튼은 분(Boone)이 1959년에 발표한 '그룹 문제'라는 단어가 해결이 불가능하다는 증거의 상당히 간결한 버전을 제시한다.^[23] 그것은 특히 브리튼의 보조정리인 집단 이데올로기적 접근법을 사용한다. 더 현대적이고 압축적인 증거가 존재하지만, 이 증거는 대학원 과정에 사용되어 왔다.^[24]

Semi-Thue 시스템의 단어 문제

The accessibility problem for string rewriting systems (semi-Thue systems) can be stated as follows: Given a semi-Thue system ${\displaystyle T:=(\Sigma ,R)}$ and two words (strings) ${\displaystyle u,v\in \Sigma ^{*}}$, can ${\displaystyle u}$ be transformed into ${\displaystyle v}$ by app$R{\displaystyle }$ ${\displaystyle R}$의 거짓말 규칙$?$ 여기서 다시 쓰는 방법은 단방향이라는 점에 유의하십시오.단어 문제는 대칭적 재작성 관계에 대한 접근성 문제다.Thue 시스템.^[25]

접근성과 단어 문제는 불분명하다. 즉, 이 문제를 해결하기 위한 일반적인 알고리즘이 없다.^[26]이것은 심지어 우리가 시스템이 유한한 표시, 즉 기호의 유한한 집합과 그 기호들의 유한한 관계를 갖도록 제한하는 경우에도 유지된다.^[25]

그룹에 대한 단어 문제

그룹 G에 대한$$ 프레젠테이션 $⟨{\displaystyle }$ ${\displaystyle S}$ ${\displaystyle \mid }$ ${\displaystyle R\mathcal{}}$ ${\displaystyle ⟩}$ ${\displaystyle \langle S\mid {\mathcal{R}\angle }$이(가) 주어졌을 때, 단어 문제는 G의 동일한 요소를 나타내는지 여부를 S에 입력 두 단어로 주어지는 알고리즘 문제다.문제라는 단어는 1911년 막스 딘이 제안한 그룹에 대한 세 가지 알고리즘 문제 중 하나이다.1955년 표트르 노비코프(Pyotr Novikov)에 의해 G에 대한 문제라는 단어가 불분명할 정도로 미세하게 제시된 그룹 G가 존재한다는 것이 증명되었다.^[27]

결합 미적분학의 단어 문제

이해할 수 없는 단어 문제의 가장 간단한 예는 결합 논리학에서 발생한다: 두 줄의 결합자는 언제 등가?결합기는 가능한 튜링 기계를 모두 인코딩하고, 두 튜링 기계의 등가성은 불문율이기 때문에, 두 문자열의 결합기 균등성은 불문율인 것으로 뒤따른다.^[28]

마찬가지로 (유형화되지 않은) 람다 미적분학에서도 본질적으로 같은 문제를 가지고 있다: 두 개의 뚜렷한 람다 식을 주어, 등가 여부를 판별할 수 있는 알고리즘이 없다; 등가성은 불분명하다.람다 미적분학의 몇 가지 유형 변형의 경우 등가성은 정상 형태 비교에 의해 결정된다.

추상 재작성 시스템의 단어 문제

추상적 재작성 시스템(ARS)의 문제라는 단어는 매우 간결하다: 주어진 x와 y 물체는$£{\$에 해당된다$.$^[29]ARS의 문제라는 단어는 일반적으로 이해할 수 없다.단, 모든 물체가 한정된 수의 스텝(즉, 시스템이 수렴되는)에서 고유한 정상 형태로 감소하는 특정 사례에 단어 문제에 대한 계산 가능한 해결책이 있다. 두 물체는 동일한 정상 형태로 감소하는 경우에만$$ ${\displaystyle \stackrel{}{}}$ ${\$에 따라 동등하다..^[30] Knuth-Bendix 완료 알고리즘은 일련의 방정식을 융합 용어 재쓰기 시스템으로 변환하는 데 사용할 수 있다.

유니버설 대수학의 단어 문제

유니버설 대수학에서는 생성 집합 A, 유한 아리티의 연산 집합(일반적으로 이항 연산) 및 이러한 연산이 충족해야 하는 유한한 ID 집합으로 구성된 대수 구조를 연구한다.대수학의 문제라는 단어는 생성자와 연산을 포함하는 두 개의 표현식(단어)을 주어 그것들이 대수학의 동일 요소를 나타내는지를 결정하는 것이다.그룹과 세미그룹의 문제라는 단어는 알헤브라의 문제라는 단어로 표현될 수 있다.^[1]

지상의 문제라는 단어는 해독할 수 없다.^{[31][clarification needed]}

자유 헤잉 알헤브라스라는 단어는 어렵다.^[32]유일한 알려진 결과는 한 발전기의 자유 헤이팅 대수학은 무한하며, 한 발전기의 자유 완전 헤팅 대수학이 존재한다는 것이다(자유 헤이팅 대수학보다 한 가지 더 많은 원소를 가지고 있다).

프리 래티스의 단어 문제

x∧z ~ x∧z∧(x∨y)의 계산 예제

x∧z∧(x∨y) ≤~ zz 5시까지 그 이후 zz ≤~ zz 1로 그 이후 zz = zz

zz ≤~ x∧z∧(x∨y) 7시까지 그 이후 zz ≤~ zz 그리고 zz ≤~ yy 1로 그 이후 zz = zz 6시까지 그 이후 zz ≤~ x 5시까지 그 이후 x ≤~ x 1로 그 이후 x = x

무료 선반에 대한 문제라는 단어는 몇 가지 흥미로운 측면이 있다.경계 격자의 경우, 즉 두 개의 이항 연산 ∨과 ∧과 두 개의 상수(nullary operations) 0과 1을 갖는 대수적 구조의 경우를 고려한다.주어진 생성기 X의 요소 집합에서 이러한 연산을 사용하여 공식화할 수 있는 모든 잘 형성된 식 집합을 W(X)라고 한다.이 단어 집합은 모든 격자에서 동일한 값을 나타내는 많은 표현들을 포함하고 있다.예를 들어, a가 X의 일부 요소인 경우, 1 1 = 1 및 1 1 =a.자유 경계 격자 문제라는 단어는 이러한 W(X) 요소들 중 어느 요소가 자유 경계 격자 FX에서 같은 요소를 나타내는지를 결정하는 문제로서, 따라서 모든 경계 격자에서는 같은 요소를 나타낸다.

단어 문제는 다음과 같이 해결될 수 있다.W(X)에 대한 관계 ≤_~는 다음 중 하나에 해당하는 경우에만 w ≤_~ v를 설정하여 귀납적으로 정의할 수 있다.

1. w = v(w와 v가 X의 요소인 경우로 제한될 수 있음)
2. w = 0,
3. v = 1,
4. w = w₁ ∨ w₂ 및 w₁ ≤_~ v 및 w₂ ≤_~ v hold,
5. w = w₁ ∧ w₂ 및 w₁ ≤_~ v 또는 w₂ ≤_~ v hold,
6. v = v₁ ∨ v₂ 및 w ≤_~ v₁ 또는 w ≤_~ v hold₂,
7. v = v₁ ∧ v₂ 및 w ≤_~ v₂ 홀드₁ 둘 _~다.

이것은 W(X)에 사전 주문 ≤_~을 정의하기 때문에 w ≤_~ v와 v ≤_~ w일 때 w ~ v로 동등성 관계를 정의할 수 있다.그러면 부분적으로 순서가 정해진 지수 공간 W(X)/~가 자유 경계 격자 FX임을 알 수 있다.^[33][34]W(X)/~의 등가 등급은 w와 v를 w와 _~v와 _~w와 합한 모든 단어의 집합이다.W(X)에서 잘 형성된 두 단어는 w _~w v와 v ≤_~ w의 경우에만 모든 경계 격자에서 동일한 값을 나타낸다. 후자의 조건은 위의 귀납적 정의를 사용하여 효과적으로 결정할 수 있다.표는 x∧z와 x∧z∧(x∨y)이라는 단어가 모든 경계 격자에서 동일한 값을 나타내는 계산 예제를 보여준다.상기의 구성에서 규정 2.와 3.을 생략하고, 경계가 없는 격자의 경우를 유사하게 취급한다.

예: 자유 그룹에서 단어 문제를 결정하는 용어 재작성 시스템

블래시우스와 브뤼케르트는 그룹을 위해 설정된 공리에 대해 크누스-벤딕스 알고리즘을 시연한다^[35].이 알고리즘은 모든 용어를 독특한 정상적인 형태로 변형시키는 결합적이고 노메테리아적인 용어 재작성 시스템을 산출한다.^[36]일부 규칙이 중복되어 알고리즘 실행 중에 삭제되었기 때문에 재작성 규칙은 논란의 여지가 없는 번호로 지정된다.두 용어의 동일성은 두 용어가 문자 그대로 동일한 정규 형식 용어로 변환되는 경우에만 공리에서 나타난다.예를 들어, 용어

${\displaystyle ((a^{-1}\cdot a)\cdot (b\cdot b^{-1}))^{-1}{\stackrel {R2}{\rightsquigarrow }}(1\cdot (b\cdot b^{-1}))^{-1}{\stackrel {R13}{\rightsquigarrow }}(1\cdot$$1)^{-1}{\stackrel {R1}{{\wrightsquigarrow }{1$}{{1$}{\stackrel {R8}{\wrightsquigarrow$ $\},$ $그리고$

${\displaystyle b\cdot ((a\cdot b)^{-1}\cdot a){\stackrel {R17}{\rightsquigarrow }}b\cdot ((b^{-1}\cdot a^{-1})\cdot a){\stackrel {R3}{\rightsquigarrow }}b\cdot (b^{-1}\cdot (a^{-1}\cdot a)){\\stackrel {R2}{\wrighquigarrow }{{-1}\cdot 1){\stackrel {R11}{\wrightsquigarrow }{{1}{\stackrel {R13}{\wrightsquigarrow }}{1}{1}$

동일한 정규 $형식$인 viz$.$ 1 {\$displaystyle$ 1}을(를$)$ 공유하므로 두 용어는 모든 그룹에서 동일하다$.$${\displaystyle 또}$ 다른 예로, $1{\displaystyle \mathrm{}}$ ${\displaystyle \cdot }$ (${\displaystyle }$${\displaystyle \cdot }$ ${\displaystyle b}$) ${\displaystyle 1\cdot (a\$$cdot b$$)}$과 $b{\displaystyle }$($1$은 ${\displaystyle \mathrm{각각}}$ ${\displaystyle \cdot }$ b ${\displaystyle a\cdot b}$과 ${\displaystyle b}$ ${\displaystyle \{}$ ${\displaysty b\cdot a}$의 정상적인 형태를 가지고$$ 있다$.$정상적인 형태는 말 그대로 다르기 때문에 원래의 용어는 모든 그룹에서 동등할 수 없다.사실, 그들은 보통 비아벨라 그룹에서는 다르다.

Knuth-Bendix 완료에 사용되는 그룹 공리

A1	$1\cdot x}$	${\displaystyle =x}$
A2	${\displaystyle x^{-1}\cdot x}$	${\displaystyle =1}$
A3	${\displaystyle(x\cdot y)\cdot z}$	${\displaystyle =x\cdot(y\cdot z)}$

Knuth-Bendix 완료에서 얻은 용어 재작성 시스템

R1	$1\cdot x}$	$\displaystyle \rightsquigarrow x}$
R2	${\displaystyle x^{-1}\cdot x}$	$\displaystyle \rightsquigarrow 1}$
R3	${\displaystyle(x\cdot y)\cdot z}$	$\displaystyle \putquigarrow x\cdot(y\cdot z)}$
R4	${\displaystyle x^{-1}\cdot(x\cdot y)}$	$\displaystyle \rightsquigarrow y}$
R8	${\displaystyle 1^{-1}$	$\displaystyle \rightsquigarrow 1}$
R11	${\displaystyle x\cdot 1}$	$\displaystyle \rightsquigarrow x}$
R12	${\displaystyle (x^{-1})^{-1}$	$\displaystyle \rightsquigarrow x}$
R13	${\displaystyle x\cdot x^{-1}$	$\displaystyle \rightsquigarrow 1}$
R14	${\displaystyle x\cdot(x^{-1}\cdot y)}$	$\displaystyle \rightsquigarrow y}$
R17	${\displaystyle (x\cdot y)^{-1}$	${\displaystyle \quigarrow y^{-1}\cdot x^{-1}$

참고 항목

• 문나무
• 결합 문제
• 집단 이형성 문제

참조