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$
(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.)