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)

    “Any solution to a problem changes the problem.”
    —R.W. (Richard William)

    “But the word Miracle, as pronounced by Christian churches, gives a false impression; it is Monster. It is not one with the blowing clover and falling rain.”
    —Ralph Waldo Emerson (1803–1882)

    “The family environment in which your children are growing up is different from that in which you grew up. The decisions our parents made and the strategies they used were developed in a different context from what we face today, even if the “content” of the problem is the same. It is a mistake to think that our own experience as children and adolescents will give us all we need to help our children. The rules of the game have changed.”
    —Lawrence Kutner (20th century)