On Markov's undecidability theorem for integer matrices.
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).
- Examples of undecidable problems for 2-generator matrix semigroups
- On factorizations of upper triangular nonnegative matrices of order three
- On undecidability bounds for matrix decision problems
- Improved matrix pair undecidability results
- Post Correspondence Problem and Small Dimensional Matrices
- Products of matrices and recursively enumerable sets
- scientific article; zbMATH DE number 2087212 (Why is no real title available?)
- On upper triangular nonnegative matrices.
- A note on the emptiness of semigroup intersections
- ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
- Number theory of matrix semigroups
- Semigroup intersection problems in the Heisenberg groups
- Undecidability in matrices over Laurent polynomials.
- Probabilistic finite automaton emptiness is undecidable for a fixed automaton
- Reachability problems in quaternion matrix and rotation semigroups
This page was built for publication: On Markov's undecidability theorem for integer matrices.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2460065)
