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)

    “To the questions of the officiously meddling police Falter replied absently and tersely; but, when he finally grew tired of this pestering, he pointed out that, having accidentally solved “the riddle of the universe,” he had yielded to artful exhortation and shared that solution with his inquisitive interlocutor, whereupon the latter had died of astonishment.”
    —Vladimir Nabokov (1899–1977)

    “The word “forbearance” is the key to a happy home.”
    —Chinese proverb.

    “The problem ... is emblematic of what hasn’t changed during the equal opportunity revolution of the last 20 years. Doors opened; opportunities evolved. Law, institutions, corporations moved forward. But many minds did not.”
    —Anna Quindlen (b. 1952)