Word Problem For Groups - Partial Solution of The Word Problem

Partial Solution of The Word Problem

The word problem for a recursively presented group can be partially solved in the following sense:

Given a recursive presentation P = ⟨X|R⟩ for a group G, define:
then there is a partial recursive function fP such that:
f_P(\langle u,v \rangle) = \left\{\begin{matrix} 0 &\mbox{if}\ \langle u,v \rangle \in S \\ \mbox{undefined/does not halt}\ &\mbox{if}\ \langle u,v \rangle \notin S \end{matrix}\right.

More informally, there is an algorithm that halts if u=v, but does not do so otherwise.

It follows that to solve the word problem for P it is sufficient to construct a recursive function g such that:

g(\langle u,v \rangle) = \left\{\begin{matrix} 0 &\mbox{if}\ \langle u,v \rangle \notin S \\ \mbox{undefined/does not halt}\ &\mbox{if}\ \langle u,v \rangle \in S \end{matrix}\right.

However u=v in G if and only if uv−1=1 in G. It follows that to solve the word problem for P it is sufficient to construct a recursive function h such that:

h(x) = \left\{\begin{matrix} 0 &\mbox{if}\ x\neq1\ \mbox{in}\ G \\ \mbox{undefined/does not halt}\ &\mbox{if}\ x=1\ \mbox{in}\ G \end{matrix}\right.

Read more about this topic:  Word Problem For Groups

Famous quotes containing the words partial, solution, word and/or problem:

    “There is no luck in literary reputation. They who make up the final verdict upon every book are not the partial and noisy readers of the hour when it appears; but a court as of angels, a public not to be bribed, not to be entreated, and not to be overawed, decides upon every man’s title to fame. Only those books come down which deserve to last.”
    —Ralph Waldo Emerson (1803–1882)

    “Coming out, all the way out, is offered more and more as the political solution to our oppression. The argument goes that, if people could see just how many of us there are, some in very important places, the negative stereotype would vanish overnight. ...It is far more realistic to suppose that, if the tenth of the population that is gay became visible tomorrow, the panic of the majority of people would inspire repressive legislation of a sort that would shock even the pessimists among us.”
    —Jane Rule (b. 1931)

    “They made a paction tween them twa,
    They made it firm and sure,
    That the first word whaeer shoud speak,
    Shoud rise and bar the door.”
    —Unknown. Get Up and Bar the Door (l. 13–16)

    “I tell you, sir, the only safeguard of order and discipline in the modern world is a standardized worker with interchangeable parts. That would solve the entire problem of management.”
    —Jean Giraudoux (1882–1944)