Markov's theorem and algorithmically non-recognizable combinatorial manifolds

M. A. Shtan'ko

Izvestiya. Mathematics , Tome 68 (2004) no. 1, pp. 205-221

Résumé

We prove the theorem of Markov on the existence of an algorithmically non-recognizable combinatorial $n$-dimensional manifold for every $n\geqslant 4$. We construct for the first time a concrete manifold which is algorithmically non-recognizable. A strengthened form of Markov's theorem is proved using the combinatorial methods of regular neighbourhoods and handle theory. The proofs coincide for all $n\geqslant 4$. We use Borisov's group [8] with insoluble word problem. It has two generators and twelve relations. The use of this group forms the base for proving the strengthened form of Markov's theorem. (The author is indebted to S. I. Adian for this idea.)