Zadanie tekstowe (matematyka)

Ten artykuł dotyczy algorytmicznych problemów tekstowych w matematyce i informatyce. W przypadku innych zastosowań zobacz Problem z programem Word .

W matematyce obliczeniowej problem tekstowy to problem polegający na rozstrzygnięciu , czy dwa dane wyrażenia są równoważne pod względem zbioru tożsamości przepisywania . Prototypowym przykładem jest problem tekstowy dla grup , ale jest też wiele innych przykładów. Głębokim wnioskiem teorii obliczeniowej jest to, że odpowiedź na to pytanie jest w wielu ważnych przypadkach nierozstrzygalna .

Tło i motywacja

W algebrze komputerowej często chce się zakodować wyrażenia matematyczne za pomocą drzewa wyrażeń. Ale często istnieje wiele równoważnych drzew wyrażeń. Naturalnie powstaje pytanie, czy istnieje algorytm, który, mając jako dane wejściowe dwa wyrażenia, decyduje, czy reprezentują one ten sam element. Taki algorytm nazywa się rozwiązaniem problemu tekstowego . Na przykład wyobraź sobie $,$ że są symbolami reprezentującymi liczby rzeczywiste problemu tekstowego byłoby, biorąc pod ${\ Displaystyle (x \ cdot y) / z \ mathrel {\ overset {?}} {=}} (x / z) \ cdot y} , wygeneruj wynik RÓWNY$ i podobnie wyprodukuj NIE_RÓWNOŚĆ z ${\ Displaystyle (x \ cdot y) / z \ mathrel {\ overset {?}} {=}} (x/x) \ cdot y}$ .

Najbardziej bezpośrednie rozwiązanie problemu tekstowego przybiera postać twierdzenia i algorytmu o postaci normalnej, które odwzorowują każdy element w klasie równoważności wyrażeń na pojedyncze kodowanie znane jako postać normalna - problem tekstowy jest następnie rozwiązywany przez porównanie tych form normalnych za pomocą równość syntaktyczna . $y) /z}$ przykład można zdecydować, że normalna postać $⋅ y$ , ${\ Displaystyle (x/z) \ cdot y}$ i ${\ Displaystyle (y / z) \ cdot x}$ i opracować system transformacji, aby przepisać te wyrażenia do tej postaci, udowadniając przy tym, że wszystkie równoważne wyrażenia zostaną przepisane do tej samej postaci normalnej. Ale nie wszystkie rozwiązania problemu tekstowego wykorzystują twierdzenie o postaci normalnej - istnieją właściwości algebraiczne, które pośrednio implikują istnienie algorytmu.

Podczas gdy problem tekstowy pyta, czy dwa terminy zawierające $stałe$ są , właściwe rozszerzenie problemu tekstowego, znane jako , czy dwa terminy zawierające zmienne mają przypadki , które są równe, czyli innymi słowy, czy równanie ma jakieś rozwiązania . ${\ displaystyle t_ {1} = t_ {2}}$ Typowym przykładem jest ${\ Displaystyle 2 + 3 {\ stackrel {?} {=}} 8 + (-3)}$ to zadanie tekstowe w grupie liczb całkowitych ℤ , podczas gdy $grupie$ samej ponieważ poprzednie warunki są równe w ℤ, drugi problem ma podstawienie { $\ Displaystyle \ {x \ mapsto 3 \}}$ jako rozwiązanie.

Historia

Jednym z najlepiej zbadanych przypadków problemu tekstowego jest teoria półgrup i grup . Kalendarium artykułów związanych z twierdzeniem Nowikowa-Boone'a jest następujące:

• 1910 ( 1910 ) : Axel Thue stawia ogólny problem przepisywania terminów na strukturach drzewiastych. Stwierdza: „Rozwiązanie tego problemu w najbardziej ogólnym przypadku może wiązać się z trudnościami nie do pokonania”.
• 1911 ( 1911 ) : Max Dehn stawia problem słowny dla skończenie przedstawionych grup.
• 1912 ( 1912 ) : Dehn przedstawia algorytm Dehna i udowadnia, że ​​rozwiązuje on problem tekstowy dla podstawowych grup zamkniętych orientowalnych dwuwymiarowych rozmaitości rodzaju większych lub równych 2. Kolejni autorzy znacznie rozszerzyli go na szeroki zakres teorii grup problemy decyzyjne .
• 1914 ( 1914 ) : Axel Thue stawia problem tekstowy dla skończenie przedstawionych półgrup.
• 1930 ( 1930 ) – 1938 ( 1938 ) : Pojawia się teza Churcha -Turinga , definiująca formalne pojęcia obliczalności i nierozstrzygalności.
• 1947 ( 1947 ) : Emil Post i Andrey Markov Jr. niezależnie konstruują skończenie przedstawione półgrupy z nierozwiązywalnym zadaniem tekstowym. Konstrukcja Posta jest zbudowana na maszynach Turinga, podczas gdy konstrukcja Markowa korzysta z normalnych systemów Posta.
• 1950 ( 1950 ) : Alan Turing pokazuje, że problem tekstowy dla półgrup anulowania jest nierozwiązywalny, rozwijając konstrukcję Posta. Dowód jest trudny do naśladowania, ale stanowi punkt zwrotny w problemie tekstowym dla grup.
• 1955 ( 1955 ) : Piotr Nowikow podaje pierwszy opublikowany dowód, że problem słowny dla grup jest nierozwiązywalny, wykorzystując wynik półgrupy z anulowaniem Turinga. Dowód zawiera „główny lemat” równoważny z lematem Brittona .
• 1954 ( 1954 ) - 1957 ( 1957 ) : William Boone niezależnie pokazuje, że problem tekstowy dla grup jest nierozwiązywalny, używając konstrukcji półgrupowej Posta.
• 1957 ( 1957 ) - 1958 ( 1958 ) : John Britton podaje kolejny dowód na to, że problem słowny dla grup jest nierozwiązywalny, w oparciu o wynik półgrup anulowania Turinga i niektóre wcześniejsze prace Brittona. Pojawia się wczesna wersja lematu Brittona.
• 1958 ( 1958 ) – 1959 ( 1959 ) : Boone publikuje uproszczoną wersję swojej konstrukcji.
• 1961 ( 1961 ) : Graham Higman charakteryzuje podgrupy skończenie przedstawionych grup za pomocą twierdzenia Higmana o osadzeniu , łącząc teorię rekurencji z teorią grup w nieoczekiwany sposób i dając zupełnie inny dowód nierozwiązywalności problemu słownego.
• 1961 ( 1961 ) – 1963 ( 1963 ) : Britton przedstawia znacznie uproszczoną wersję dowodu Boone'a z 1959 roku, że problemu tekstowego dla grup nie da się rozwiązać. Wykorzystuje podejście oparte na teorii grup, w szczególności Lemat Brittona . Ten dowód został wykorzystany na kursie dla absolwentów, chociaż istnieją bardziej nowoczesne i skondensowane dowody.
• 1977 ( 1977 ) : Giennadij Makanin udowadnia, że ​​​​egzystencjalna teoria równań nad wolnymi monoidami jest rozwiązywalna.

Problem tekstowy dla systemów semi-Thue

Problem dostępności dla systemów przepisywania łańcuchów (systemy semi-Thue lub półgrupy) można określić następująco: Biorąc pod uwagę system semi-Thue i dwa T ${\ Displaystyle T: = (\ Sigma, R)}$ słowa (ciągi) ${\ Displaystyle u, v \ w \ Sigma ^ {*}}$ , czy można ${\ displaystyle u$ w $}$ stosując reguły z ${\ displaystyle R}$ ? Zauważ, że przepisywanie tutaj jest jednokierunkowe. Problem tekstowy to problem dostępności dla symetrycznych relacji przepisywania, tj. systemów Thue.

Problemy z dostępnością i tekstem są nierozstrzygalne , tzn. nie ma ogólnego algorytmu rozwiązania tego problemu. Dzieje się tak nawet wtedy, gdy ograniczymy systemy do skończonych prezentacji, tj. skończonego zbioru symboli i skończonego zbioru relacji na tych symbolach. Nawet problem słowny ograniczony do terminów podstawowych nie jest rozstrzygalny dla pewnych ostatecznie przedstawionych półgrup.

Zadanie tekstowe dla grup

Główny artykuł: Problem tekstowy dla grup

$pod uwagę$ prezentację dla grupy , problem tekstowy jest algorytmicznym problemem decydowania, podając jako dane w S , reprezentują ten sam element G . Problem słowny jest jednym z trzech problemów algorytmicznych dla grup zaproponowanych przez Maxa Dehna w 1911 r. Piotr Nowikow w 1955 r . Wykazał, że istnieje skończenie przedstawiona grupa G taka, że ​​​​problem słowny dla G jest nierozstrzygalny .

Problem słowny w rachunku kombinatorycznym i rachunku lambda

Główny artykuł: Logika kombinatoryczna § Nierozstrzygalność rachunku kombinatorycznego

Jeden z najwcześniejszych dowodów na to, że zadanie tekstowe jest nierozstrzygalne, dotyczył logiki kombinatorycznej : kiedy dwa ciągi kombinatorów są równoważne? Ponieważ kombinatory kodują wszystkie możliwe maszyny Turinga , a równoważność dwóch maszyn Turinga jest nierozstrzygalna, wynika z tego, że równoważność dwóch ciągów kombinatorów jest nierozstrzygalna. Alonzo Church zauważył to w 1936 roku.

Podobnie, jeden ma zasadniczo ten sam problem w (nieopisanym) rachunku lambda : biorąc pod uwagę dwa różne wyrażenia lambda, nie ma algorytmu, który mógłby rozróżnić, czy są one równoważne, czy nie; równoważność jest nierozstrzygalna . W przypadku kilku typowanych wariantów rachunku lambda równoważność można ustalić przez porównanie form normalnych.

Problem tekstowy dla abstrakcyjnych systemów przepisywania

Rozwiązanie problemu tekstowego: podjęcie decyzji, czy zwykle wymaga wyszukiwania heurystycznego ( ${\ stackrel {*}$ , zielony ), podczas decydowania $displaystyle x \ downarrow =y\downarrow }$ \ Displaystyle x jest proste ( szary ).

Problem tekstowy dla abstrakcyjnego systemu przepisywania (ARS) jest dość zwięzły: dane obiekty x i y czy są one równoważne pod ${\ Displaystyle {\ stackrel {*} {\ leftrightarrow}}}$ ? Problem słowny dla ARS jest ogólnie nierozstrzygalny . Istnieje jednak obliczalne rozwiązanie problemu tekstowego w konkretnym przypadku, w którym każdy obiekt redukuje się do unikalnej postaci normalnej w skończonej liczbie kroków (tj. system jest zbieżny ): dwa obiekty są równoważne pod ${\ displaystyle {\ stackrel {*} {\ leftrightarrow}}}$ wtedy i tylko wtedy, gdy redukują się do tej samej postaci normalnej. Algorytm uzupełniania Knutha-Bendixa można wykorzystać do przekształcenia zestawu równań w zbieżny system przepisywania terminów .

Problem słowny w algebrze uniwersalnej

W algebrze uniwersalnej bada się struktury algebraiczne składające się ze zbioru generującego A, zbioru operacji na A o skończonej liczbie (zwykle operacji binarnych) oraz skończonego zbioru tożsamości, które muszą spełniać te operacje. Problem słowny dla algebry polega zatem na określeniu, przy danych dwóch wyrażeniach (słowach) obejmujących generatory i operacje, czy reprezentują one ten sam element algebry modulo tożsamości. Zadania tekstowe dla grup i półgrup można sformułować jako zadania tekstowe dla algebr.

Zadanie tekstowe na swobodnych algebrach Heytinga jest trudne. Jedynymi znanymi wynikami jest to, że swobodna algebra Heytinga na jednym generatorze jest nieskończona i że istnieje swobodna kompletna algebra Heytinga na jednym generatorze (i ma o jeden element więcej niż swobodna algebra Heytinga).

Zadanie tekstowe dla swobodnych krat

Przykładowe obliczenie x ∧ z ~ x ∧ z ∧( x ∨ y )

x ∧ z ∧ ( x ∨ y ) ≤ ~ x ∧ z do 5. od x ∧ z ≤ ~ x ∧ z o 1. od x ∧ z = x ∧ z

x ∧ z ≤ ~ x ∧ z ∧ ( x ∨ y ) do 7. od x ∧ z ≤ ~ x ∧ z I x ∧ z ≤ ~ x ∨ y o 1. od x ∧ z = x ∧ z do 6. od x ∧ z ≤ ~ X do 5. od X ≤ ~ X o 1. od X = X

Zadanie tekstowe dotyczące sieci swobodnych i bardziej ogólnie sieci swobodnych ograniczonych ma rozstrzygalne rozwiązanie. Kraty ograniczone to struktury algebraiczne z dwiema operacjami binarnymi ∨ i ∧ oraz dwiema stałymi ( operacjami zerowymi ) 0 i 1. Zbiór wszystkich dobrze sformułowanych wyrażeń , które można sformułować za pomocą tych operacji na elementach z danego zbioru generatorów X będzie nazywać się W ( X ). Ten zestaw słów zawiera wiele wyrażeń, które okazują się oznaczać równe wartości w każdej sieci. Na przykład, jeśli A jest jakimś elementem X , to a ∨ 1 = 1 i a ∧ 1 = a . Zadanie tekstowe dla sieci swobodnych ograniczonych polega na określeniu, który z tych elementów W ( X ) oznacza ten sam element w sieci swobodnej ograniczonej FX , a zatem w każdej sieci ograniczonej.

Zadanie tekstowe można rozwiązać w następujący sposób. Relacja ≤ _~ na W ( X ) może być zdefiniowana indukcyjnie przez ustawienie w ≤ _~ v wtedy i tylko wtedy, gdy spełniony jest jeden z poniższych warunków:

1.   w = v (można to ograniczyć do przypadku, gdy w i v są elementami X ),
2.   w = 0,
3.   v = 1,
4.   w = w ₁ ∨ w ₂ i oba w ₁ ≤ _~ v i w ₂ ≤ _~ v trzymać,
5.   w = w ₁ ∧ w ₂ i albo w ₁ ≤ _~ v albo w ₂ ≤ _~ v zachodzi,
6.   v = v ₁ ∨ v ₂ i albo w ≤ _~ v ₁ albo w ≤ _~ v ₂ zachodzi,
7.   v = v ₁ ∧ v ₂ i zarówno w ≤ _~ v _1, jak i w ≤ _~ v ₂ utrzymują się.

To definiuje preorder ≤ _~ na W ( X ), więc relacja równoważności może być zdefiniowana przez w ~ v , gdy w ≤ _~ v i v ≤ _~ w . Można więc pokazać, że częściowo uporządkowana przestrzeń ilorazowa W ( X )/~ jest swobodną siatką ograniczoną FX . Klasy równoważności W ( X _ )/~ to zbiory wszystkich słów w i v z w ≤ _~ v i v ≤ _~ w . Dwa dobrze sformułowane słowa v i w w W ( X ) oznaczają tę samą wartość w każdej ograniczonej sieci wtedy i tylko wtedy, gdy w ≤ _~ v i v ≤ _~ w ; te ostatnie warunki można skutecznie rozstrzygnąć za pomocą powyższej definicji indukcyjnej. Tabela pokazuje przykładowe obliczenia pokazujące, że słowa x ∧ z i x ∧ z ∧( x ∨ y ) oznaczają tę samą wartość w każdej ograniczonej sieci. Przypadek krat, które nie są ograniczone, traktuje się podobnie, pomijając reguły 2 i 3 w powyższej konstrukcji ≤ _~ .

Przykład: System przepisywania terminów w celu rozstrzygnięcia problemu tekstowego w grupie wolnej

Bläsius i Bürckert demonstrują algorytm Knutha – Bendixa na zestawie aksjomatów dla grup. Algorytm daje konfluentny i noetherowski system przepisywania terminów , który przekształca każdy termin w unikalną postać normalną . Reguły przepisywania są numerowane jako nieciągłe, ponieważ niektóre z nich stały się zbędne i zostały usunięte podczas działania algorytmu. Równość dwóch terminów wynika z aksjomatów wtedy i tylko wtedy, gdy oba terminy są przekształcone w dosłownie ten sam termin w postaci normalnej. Na przykład warunki

${\ 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}{\rightsquigarrow} } 1 ^ {-1}{\stackrel {R8}{\rightsquigarrow }}1}$ , i

${\ 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}{\ rightsquigarrow }}b\cdot (b^{-1}\cdot 1){\stackrel {R11}{\rightsquigarrow }}b\cdot b^{-1}{\stackrel {R13}{\rightsquigarrow }}1}$

mają tę samą postać normalną, tj. ${\ displaystyle 1}$ ; dlatego oba terminy są równe w każdej grupie. $}$ termin $⋅ za ) {\ Displaystyle$ \ ma za ${\ Displaystyle a \ cdot b}$ i $a}$ odpowiednio. Ponieważ formy normalne są dosłownie różne, pierwotne terminy nie mogą być równe w każdej grupie. W rzeczywistości są one zwykle różne w grupach nieabelowych .

Aksjomaty grupowe używane w uzupełnianiu Knutha – Bendixa

A1	${\ Displaystyle 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)}$

System przepisywania terminów uzyskany z ukończenia przez Knutha – Bendixa

R1	${\ Displaystyle 1 \ cdot x}$	${\ Displaystyle \ rightsquigarrow x}$
R2	${\ Displaystyle x ^ {- 1} \ cdot x}$	${\ Displaystyle \ rightsquigarrow 1}$
R3	${\ Displaystyle (x \ cdot y) \ cdot z}$	${\ Displaystyle \ rightsquigarrow 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 \ rightsquigarrow y ^ {- 1} \ cdot x ^ {- 1}}$

Zobacz też

• Problem z konkubinatem
• Problem izomorfizmu grup