A1 Refereed original research article in a scientific journal
On Markov's undecidability theorem for integer matrices
Authors: Halava V, Harju T
Publisher: SPRINGER
Publication year: 2007
Journal:: Semigroup Forum
Journal name in source: SEMIGROUP FORUM
Journal acronym: SEMIGROUP FORUM
Volume: 75
Issue: 1
First page : 173
Last page: 180
Number of pages: 8
ISSN: 0037-1912
DOI: https://doi.org/10.1007/s00233-007-0714-x
Abstract
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.
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.
UTU Research Portal