UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
Vesa Halava, Tero Harju, Mika Hirvensalo · International Journal of Foundations of Computer Science · 2007
There are several known undecidable problems for 3 × 3 integer matrices the proof of which use a reduction from the Post Correspondence Problem (PCP). We establish new lower bounds in the number of matrices for the mortality, zero in the left upper corner, vector reachability, matrix reachability, scalar reachability and freeness problems. Also, we give a short proof for a strengthened result due to Bell and Potapov stating that the membership problem is undecidable for finitely generated matrix semigroups R ⊆ ℤ 4×4 whether or not kI 4 ∈ R for any given |k| > 1. These bounds are obtained by using the Claus instances of the PCP.