Recognizing the 4-sphere and the Adjan--Rabin theorem The problem of recognizing the standard $S^n$ is the following:
Given some simplicial complex $M$ with rational vertices representing a closed manifold,
can one decide (in finite time) if $M$ is homeomorphic to $S^n$. 
For $n=1$, this is obvious,
and for $n=2$,
one can solve it by computing $\chi(M)$.
A solution for $n=3$ is due to 
J.H. Rubinstein. An algorithm to recognize the 3-sphere. In Pro-
ceedings of the International Congress of Mathematicians, vol-
ume 1, 2, pages pp. 601–611, Basel, 1995. Birkhäuser.
By a theorem of S.P. Novikov,
the problem is unsolvable if $n\geq 5$.
The idea is the following: By the Adjan--Rabin theorem,
there is a sequence of super-perfect groups $\pi_i$ for which the triviality problem is unsolvable. 
Now construct homology spheres $\Sigma_i$ with fundamental groups $\pi_i$.
If one can decide which of the $\Sigma_i$ are standard spheres,
then one can solve the triviality problem for the fundamental groups.
Question: Is the recognition problem for $S^4$ solvable?
The problem with this proof of S.P. Novikov's theorem is that there is no result that asserts that for any given super-perfect group $\pi$ there is a homology $4$-sphere satisfying $\pi_1(\Sigma) = \pi$.
However,
Kervaire has proved that every perfect group with the same amount of generators and relators may be realized as the fundamental group of a homology $4$-sphere.
Thus the question:
Is there an improved Adjan--Rabin theorem that asserts the existence of a sequence of perfect groups $\pi_i$ with the same amount of generators and relators,
the triviality problem of which is unsolvable?
 A: As mentioned algorithmic 4-sphere recognition is an open problem.    Since Rubinstein's solution to the 3-sphere recognition problem is so simple and elegant, perhaps the first thing you might guess is, why not try those techniques in dimension 4?  Normal surfaces, crushing normal 3-spheres, searching for almost-normal 3-spheres.  
That theory is still in its infancy.  Rubinstein and his former student Bell Foozwell have been developing normal co-dimension one manifold theory in triangulated manifolds.   They have a "normalization" process that follows Rubinstein's general normal/almost-normal schema but it appears to do a fair bit of damage to the manifolds, so it's not clear to me if anything like this could eventually be used for 4-sphere recognition, but maybe some creative variant of the idea will work-out. 
Another closely-related problem would be an algorithmic Schoenflies theorem, to determine if a normal 3-sphere bounds a ball. 
A: A presentation with the same number of generators and relations is called balanced.  The triviality problem for balanced presentations (indeed, the word problem for balanced presentations) is a major unsolved problem.  Googling the phrase 'triviality problem for balanced presentations' will give lots of references.  Note that you may automatically assume that your groups $\pi_i$ are perfect, since the class of perfect groups is recursive.
A: Recognition of $S^4$ is listed as an open problem in the survey of Shmuel Winberger "Homology Manifolds" (page 1088): http://www.maths.ed.ac.uk/~aar/homology/shmuel2.pdf with exactly the same reasoning that HW explained. Note that fundamental groups of homology 4-spheres need not be balanced (an example of Hausmann and Weinberger from 1984), still, nobody so far was able to exploit this. 
