On Markov's undecidability theorem for integer matrices



: Halava V, Harju T

Publisher: SPRINGER

: 2007

Semigroup Forum

SEMIGROUP FORUM

: SEMIGROUP FORUM

: 75

: 1

: 173

: 180

: 8

: 0037-1912

DOI: https://doi.org/10.1007/s00233-007-0714-x


We study a problem considered originally by A. Markov in 1947: Given two finitely generated matrix semigroups, determine whether or not they contain a common element. This problem was proved undecidable by Markov for 4 x 4 matrices, even in a very restrict form, and for 3 x 3 matrices by Krom in 1981. Here we give a new proof in the 3 x 3 case which gives undecidability in ail almost as restricted form as the result of Markov.



Last updated on 2025-14-10 at 10:00