Problema da palavra

Na matemática e na ciência da computação, um problema de palavra para um conjunto de S em relação às codificações finitas de seus elementos é o problema algorítmico de decidir se duas representações podem ser usadas para representar o mesmo elemento do conjunto. O problema é geralmente encontrado em álgebra abstrata, onde dada uma representação de uma estrutura algébrica por geradores e relatores, o problema é determinar se duas expressões representam o mesmo elemento; um exemplo seria o problema de palavras para grupos. Informalmente dizendo, o problema de palavras em álgebra é: dado um conjunto de identidades E com duas expressões x e y, será possível transformar x em y utilizando as identidades em E usando as regras de reescrita em ambas as direções ? Embora responder a essa pergunta possa não parecer difícil, o resultado notável (e profundo) que aparece, em vários casos importantes é que o problema é indecidível. Muitos dos problemas indecidíveis na matemática, senão todos podem ser propostos como problemas de palavra; veja a lista de problemas indecidíveis para mais exemplos.

Contexto e motivação

Na matemática acontecem vários casos que alguém deseja utilizar uma quantidade finita de informação para descrever um elemento de um conjunto (geralmente infinito). Esse problema é bem aparente em matemática computacional. Modelos tradicionais de computação (tal como a máquina de Turing) possuem a capacidade de armazenamento ilimitada, então a principio é possível realizar computações com elementos de conjuntos infinitos. Por outro lado, uma vez que o espaço de armazenamento utilizado a qualquer momento é finito, precisamos de cada elemento possuindo uma representação finita.

Por varias razões, nem sempre é possível ou desejável utilizar um sistema de codificação singular, isto é, um em que cada elemento tem uma codificação única. Quando utilizando um sistema de codificação sem singularidade, a questão naturalmente surge se há um algoritmo em que, dado como entrada para duas codificações, define se elas representam o mesmo elemento. Tal algoritmo é chamado de uma solução para o problema da palavra do problema de codificação.

O problema da palavra em cálculo combinatório

O exemplo mais simples de um problema indecidível ocorre em lógica combinatória: Quando duas strings* de combinadores são equivalentes? Pois os combinadores codificam todas as possíveis máquinas de Turing, e a equivalência de duas máquinas de Turing é indecidível, segue portanto que a equivalência de duas strings de combinadores é indecidível.

Da mesma forma, um tem, essencialmente, o mesmo problema no cálculo de lambda: dadas duas expressões lambda distintas, não há nenhum algoritmo que possa discernir se eles são equivalentes ou não; equivalência é indecidível.

Problema da palavra em álgebra universal

Em álgebra, geralmente estuda-se álgebras infinitas que são geradas (sob as operações finitarias da álgebra) por vários elementos finitos. Nesse caso, os elementos da álgebra têm um sistema natural codificações finitas como expressões em termos de geradores e operações. O problema da palavra aqui é determinar, dados esses dois termos, se eles representam ou não o mesmo elemento da álgebra. Grosseiramente falando, o problema da palavra na álgebra é: dado um conjunto de identidades E (em teoria equacional), e dois termos s e t, é possível transformar s em t utilizando as identidades em E como regras de reescrita em ambas as direções? 1 Uma extensão própria do problema da palavra é conhecida como problema da unificação (também conhecido por problema da resolução de equações). Enquanto que o problema da palavra questiona se dois termos são iguais, o outro questiona se os termos possuem instâncias que são iguais. Como um exemplo comum, "$2+3{\stackrel {?}{=}}8+(-3)$" é um problema de palavra na integral do grupo ℤ, enquanto que "$2+x{\stackrel {?}{=}}8+(-x)$" é um problema de unificação no mesmo grupo; uma vez que o termo anterior ocorre de ser igual em ℤ, o termo seguinte possui a substituição $\{x\mapsto 3\}$ como solução.

As substituições podem ser ordenadas em ordem parcial, assim a unificação é o ato de achar um encontro numa reticulação. Nesse sentido, o problema da palavra em uma reticulação possui uma solução, isto é, o conjunto de todas as palavras equivalentes é chamado de reticulação livre. Um dos casos mais bem estudados do problema da palavra é a teoria dos grupos e semigrupos. Há vários grupos para os quais o problema da palavra não é definível, e nisso não há nenhuma máquina de Turing que possa determinar a equivalência de duas palavras arbitrárias em um tempo finito.

O problema da palavra em expressão atômica (N.T átomo básico) não é definível.

O problema da palavra na álgebra de Heyting é difícil. Os únicos resultados conhecidos são de que na álgebra de Heyting, em um gerador é infinito, e que há um gerador na álgebra (livre e) completa de Heyting (e ainda possui outro elemento a mais do que a álgebra livre de Heyting).

Exemplo: um sistema de reescrita de termos para definir o problema da palavra em um grupo livre.

Bläsius e Bürckert demonstram o algoritmo Knuth-Bendix em um conjunto de grupo axiomais. O algoritmo resulta em um sistema de termo de reescrita confluente não-eteriano que transforma todo termo em uma única forma normal5. As regras de reescrita são numeradas de forma incontínuas uma vez que algumas regras se tornaram redundantes e foram deletadas durante a execução do algoritmo. A igualdade de dois termos vem dos axiomas apenas e apenas se ambos os termos são transformados literalmente no mesmo termo de forma normal. Por exemplo, os termos:

$((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$, and

$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$

Compartilham a mesma forma normal assim como, viz. $1$; portanto ambos os termos são iguais em cada grupo.

Como outro exemplo o termo $1\cdot (a\cdot b)$ e $b\cdot (1\cdot a)$ tem a forma normal $a\cdot b$ e $b\cdot a$, respectivamente. Uma vez que as formas normais são literalmente diferentes, os termos originais não podem ser iguais em todo grupo. De fato, eles são geralmente diferentes em grupos não-abelianos.

Axiomas de grupo utilizados na conclusão de Knuth-Bendix:

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

Termos do sistema reescrito obtido a partir conclusão de Knuth-Bendix:

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