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:

    “And meanwhile we have gone on living,
    Living and partly living,
    Picking together the pieces,
    Gathering faggots at nightfall,
    Building a partial shelter,
    For sleeping and eating and drinking and laughter.”
    —T.S. (Thomas Stearns)

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

    “The word “tomorrow” was invented for indecisive people and for children.”
    —Ivan Sergeevich Turgenev (1818–1883)

    “The thinking person has the strange characteristic to like to create a fantasy in the place of the unsolved problem, a fantasy that stays with the person even when the problem has been solved and truth made its appearance.”
    —Johann Wolfgang Von Goethe (1749–1832)