On simulating Turing machines with matrix semigroups with integrality tests.

We present a construction to simulate Turing machines with 3 × 3 matrices over rationals. The correctness of simulation is guaranteed by testing that the matrices have integral elements during the simulation. This construction implies an undecidability result for a special identity problem for semigroups of 3 × 3 -matrices. • Direct simulation of a Turing machine with 3 × 3 rational matrices with integrality test. • The elements of the matrices in the simulation are significantly smaller than in the classical simulations using the PCP. • Undecidability of the Identity matrix problem in a special case for 3 × 3 rational matrices. [ABSTRACT FROM AUTHOR]