Here are my questions:
(Weakened Word Problem) Let $\langle X |R\rangle$ be a finite presentation of a group $G$, and let $w$ be an element of the free group $F(X)$. Does there exist an algorithm (allowed to depend on $w$ as well as the presentation) that determines whether or not $w=_G 1$? If not, is there a concrete counterexample? Is this weakened problem easier than the classical Word Problem?
(Weakened Isomorphism Problem) Let $\langle X |R\rangle$ and $\langle Y |S\rangle$ be finite presentations of groups $G$ and $H$ respectively. Does there exist an algorithm (allowed to depend on the two presentations) that determines whether or not $G$ and $H$ are isomorphic? If not, is there a concrete counterexample? Is this problem easier than the classical Isomorphism Problem?
My understanding, which may be mistaken, is that the nub of the Word Problem is whether there is a uniform algorithm for deciding whether a word in a group is equal to the identity. It is now well known that there is no such algorithm in general, though if one restricts to groups belonging to various classes then the Word Problem is decidable. Similar remarks apply to the other classical group theoretic decision problems.
Is it true – perhaps trivially true – that if the algorithm is allowed to change with the input then these problems are solvable?
I see that in Magnus, Karrass and Solitar's book for example, the Isomorphism Problem is stated in terms of a fixed $G$ and a varying $H$ which suggests that the algorithm is allowed to be tailored to $G$ although not to $H$. This would appear to lie between the two alternative statements
(Classical Isomorphism Problem) $(\exists A)(\forall G, H)(\ldots)$ There exists an algorithm such that for all pairs of finite presentations$\ldots$
and
(Weakened Isomorphism Problem) $(\forall G,H)(\exists A)(\ldots)$ Fix finite presentations of $G$ and $H$. There exists an algorithm that decides$\ldots$
Of course if $G$ and $H$ are isomorphic, there is a finite string of Tietze transformations that demonstrate that they are isomorphic, so this gives the algorithm in this case; but what if the groups are not isomorphic?
We are used to showing groups are not isomorphic by pointing out natural group-theoretic properties enjoyed by one but not the other, such as finiteness, torsion, being abelian etc. But it seems unlikely to me that for every pair of non-isomorphic groups there exists some group theoretic property – detectable from the presentations, no less! – that distinguishes them.
On the other hand, are there examples of a pair of presentations where it is an open question whether or not they are isomorphic? Perhaps there are examples where deciding isomorphism would amount to finding, say, the smallest counterexample to a known conjecture. But in this case perhaps the statement that there exists an algorithm to determine isomorphism or non-isomorphism is demonstrably true, even if the algorithm itself and its output are not known.
(Similar remarks and questions apply with the Isomorphism Problem replaced by the Word Problem.)
Best Answer
The answer to both of your questions is yes. In the first case, either the algorithm that outputs "Yes, $w=_G 1$", or the algorithm that outputs "no, $w \ne_G 1$" correctly determines whether $w =_G 1$. The fact that we might not know which of these is the correct algorithm does not alter the fact that such an algorithm exists.
A similar argument applies to the second question (and also to questions like "Is Goldbach's Conjecture true").