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:

    “We were soon in the smooth water of the Quakish Lake,... and we had our first, but a partial view of Ktaadn, its summit veiled in clouds, like a dark isthmus in that quarter, connecting the heavens with the earth.”
    —Henry David Thoreau (1817–1862)

    “There is a lot of talk now about metal detectors and gun control. Both are good things. But they are no more a solution than forks and spoons are a solution to world hunger.”
    —Anna Quindlen (b. 1953)

    “Well, most men have bound their eyes with one or another handkerchief, and attached themselves to some of these communities of opinion. This conformity makes them not false in a few particulars, authors of a few lies, but false in all particulars. Their every truth is not quite true. Their two is not the real two, their four not the real four; so that every word they say chagrins us and we know not where to set them right.”
    —Ralph Waldo Emerson (1803–1882)

    “How much atonement is enough? The bombing must be allowed as at least part-payment: those of our young people who are concerned about the moral problem posed by the Allied air offensive should at least consider the moral problem that would have been posed if the German civilian population had not suffered at all.”
    —Clive James (b. 1939)