Skip to main content
fixed an error; added 154 characters in body
Source Link
user6976
user6976

The question is a little vague but here is the answer to one possible interpretation of it. Let $G$$R$ be a group given by finite group presentation with finite generating set $R$$X$, $u$ is a word in $X$. Suppose we know that   $G$ is generated by $X$, and finite. Then, then we there existsis an algorithm to solve the word problemfind out if $u=1$ in $G$$X$ (the word problem in every finite group is decidable), but. But there is no way we can know this algorithm explicitely, i.e.if there is noexists a universal algorithm which,that given $R$ and the information that $G$ is finite, writes down an explicit Turing machine solving the word problem$u$ tells if $u=1$ in every finite group generated by $G$$X$ that satisfies $R$ (i.e. the uniform word problem in finite groups is undecidable, see Slobodskoĭ, A. M. Undecidability of the universal theory of finite groups. Algebra i Logika 20 (1981), no. 2, 207–230.). In fact that situation is quite normal. Decidability of a mass problem means an algorithm to solve it exist, but often it is a pure existence statement.

The question is a little vague but here is the answer to one possible interpretation of it. Let $G$ be a group given by finite presentation $R$. Suppose we know that $G$ is finite. Then there exists an algorithm to solve the word problem in $G$ (the word problem in every finite group is decidable), but there is no way we can know this algorithm explicitely, i.e. there is no algorithm which, given $R$ and the information that $G$ is finite, writes down an explicit Turing machine solving the word problem in $G$ (i.e. the uniform word problem in finite groups is undecidable, see Slobodskoĭ, A. M. Undecidability of the universal theory of finite groups. Algebra i Logika 20 (1981), no. 2, 207–230.)

The question is a little vague but here is the answer to one possible interpretation of it. Let $R$ be a finite group presentation with finite generating set $X$, $u$ is a word in $X$. Suppose   $G$ is generated by $X$, and finite, then we there is an algorithm to find out if $u=1$ in $X$ (the word problem in every finite group is decidable). But there is no way we can know if there exists a universal algorithm that given $R$ and $u$ tells if $u=1$ in every finite group generated by $X$ that satisfies $R$ (i.e. the uniform word problem in finite groups is undecidable, see Slobodskoĭ, A. M. Undecidability of the universal theory of finite groups. Algebra i Logika 20 (1981), no. 2, 207–230). In fact that situation is quite normal. Decidability of a mass problem means an algorithm to solve it exist, but often it is a pure existence statement.

Source Link
user6976
user6976

The question is a little vague but here is the answer to one possible interpretation of it. Let $G$ be a group given by finite presentation $R$. Suppose we know that $G$ is finite. Then there exists an algorithm to solve the word problem in $G$ (the word problem in every finite group is decidable), but there is no way we can know this algorithm explicitely, i.e. there is no algorithm which, given $R$ and the information that $G$ is finite, writes down an explicit Turing machine solving the word problem in $G$ (i.e. the uniform word problem in finite groups is undecidable, see Slobodskoĭ, A. M. Undecidability of the universal theory of finite groups. Algebra i Logika 20 (1981), no. 2, 207–230.)