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)

    “The Settlement ... is an experimental effort to aid in the solution of the social and industrial problems which are engendered by the modern conditions of life in a great city. It insists that these problems are not confined to any one portion of the city. It is an attempt to relieve, at the same time, the overaccumulation at one end of society and the destitution at the other ...”
    —Jane Addams (1860–1935)

    “I askèd a thief to steal me a peach
    He turned up his eyes
    I ask’d a lithe lady to lie her down
    Holy & meek she cries—

    As soon as I went
    An angel came.
    He wink’d at the thief
    And smild at the dame—

    And without one word said
    Had a peach from the tree
    And still as a maid
    Enjoy’d the lady.”
    —William Blake (1757–1827)

    “It is very comforting to believe that leaders who do terrible things are, in fact, mad. That way, all we have to do is make sure we don’t put psychotics in high places and we’ve got the problem solved.”
    —Tom Wolfe (b. 1931)