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:

    “You must not be partial in judging: hear out the small and the great alike; you shall not be intimidated by anyone, for the judgment is God’s.”
    —Bible: Hebrew, Deuteronomy 1:17.

    “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)

    “Here lies our Sovereign Lord, the King
    Whose word no man relies on:
    He never said a foolish thing
    Nor ever did a wise one.”
    —John Wilmot, 2nd Earl Of Rochester (1647–1680)

    “A serious problem in America is the gap between academe and the mass media, which is our culture. Professors of humanities, with all their leftist fantasies, have little direct knowledge of American life and no impact whatever on public policy.”
    —Camille Paglia (b. 1947)