Suppose $G$ is a finitely generated subgroup of $GL_n(Z)$, $n\ge 3$. I suspect that there is no decision procedure for deciding whether or not such $G$ is finitely presented. How can this proved?

4$\begingroup$ Yes, it's impossible for $n>3$ by Mikhailova's construction. Open problem, essentially due to Serre, for $n=3$. $\endgroup$ – Misha Sep 13 '12 at 13:10

5$\begingroup$ Even more interestingly, there are examples due to Bridson and HW where you have a fp subgroup for which one cannot compute a finite presentation! $\endgroup$ – Misha Sep 13 '12 at 13:25

1$\begingroup$ @Misha: Your second comment cannot be correct. For any given finitely generated subgroup the question of finding a finite presentation is not a "mass" problem. So the statement "we cannot..." does not make sense. Moreover, if you consider the mass problem where the input is a finitely presented subgroup of $SL_n(\mathbb{Z})$ and the output its finite presentation, then it is not clear that this problem is undecidable for any given $n$. Bridson and HW proved that here are recursive sequences of hyperbolic groups $\Gamma_n$ and of finite sets $S_n⊂\Gamma_n×\Gamma_n$ for which the group $A_n$ ... $\endgroup$ – user6976 Sep 13 '12 at 22:06

$\begingroup$ cont: generated by $S_n$ is f.p. but there is no algorithm that, given $n$ computes a finite presentation of $A_n$. They use a Dani Wise version of the Rips' construction to construct $\Gamma_n$. So each $\Gamma_n$ is linear but the degree of the linear presentation of $\Gamma_n$ depends on $n$. $\endgroup$ – user6976 Sep 13 '12 at 22:08

$\begingroup$ Mark, you are right, I was sloppy here. $\endgroup$ – Misha Sep 14 '12 at 0:04
Various forms of this question were discussed on MO several times, see e.g. here. The key is that $SL(4,Z)$ contains $H=F_2\times F_2$, direct product of rank 2 free groups. Then for every finitelypresented group $Q$ (i.e., a group $Q$ with a given finite presentation), there is an epimorphism $H\to Q$ with finitelygenerated kernel $K$, see e.g. here; this is called Mikhailova's construction. Unless $Q$ is finite, $K$ is not finitelypresented, see the same link. Now, take a finitelypresented group $Q$ for which it is undecidable if it is finite or not. Then for $K$ it will be undecidable if it is fp or not.
Situation is different for $GL(3,Z)$ as it contains no direct products of free nonabelian groups. It is an open problem due to J.P. Serre (1979 or so, depending how you count), if $SL(3,Z)$ is coherent (i.e., if every finitelygenerated subgroup of $SL(3,Z)$ is also finitelypresentable). Situation with $GL(3,Z)$ is the same, of course. At this moment, all known (say, torsionfree) f.g. subgroups of $SL(3,Z)$ fall into the following classes:
a. Finite index. b. Closed surface subgroups. c. Free subgroups. d. NonZariski dense in $SL(3,R)$ subgroups (abelian subgroups and semidirect products of free groups of rank $1\le r< \infty$ with $Z^2$).
All of such subgroups are finitelypresented, of course, so, for all what we know, $SL(3,Z)$ is coherent, in which case your question has obvious answer. If $SL(3,Z)$ is not coherent, who knows...

1$\begingroup$ @Misha, this is a nice answer. There is a very slight misstatement. There is no such thing as a single finite presentation for which it is undecidable whether the group is finite or not. Either the Turing machine that says yes or the one which says no is correct. What is undecidable is the uniform problem. Similarly finite presentability is undecidable as a uniform problem, not for a fixed subgroup. On the other hand the generalized word problem is unsolvable for a fixed subgroup. $\endgroup$ – Benjamin Steinberg Sep 14 '12 at 2:05