On Markov's undecidability theorem for integer matrices. (Q2460065)

The general problem under consideration here is to determine whether or not two finitely generated matrix semigroups possess a common element. In 1947 A. Markov showed this question was undecidable for semigroups of \(4\times 4\) matrices even in a very restricted form, while Krom proved in 1981 that the problem in the \(3\times 3\) case was similarly undecidable. This paper gives a new proof for the \(3\times 3\) case by proving, among other results, that given non-singular \(3\times 3\) integer matrices \(X_i\) (\(1\leq i\leq n\)), it is undecidable whether or not there is a common matrix \(X\) that is a product of the \(X_i\) (allowing repeats) and a product of another given pair of matrices \(A_1\) and \(A_2\) (and indeed stronger but more technical results along these lines are proved).