On simulating Turing machines with matrix semigroups with integrality tests

: Halava, Vesa; Niskanen, Reino

Publisher: Elsevier

: 2024

: Theoretical Computer Science

: 114637

: 1005

: 0304-3975

: 1879-2294

DOI: https://doi.org/10.1016/j.tcs.2024.114637(external)

: https://www.sciencedirect.com/science/article/pii/S0304397524002524(external)

: https://research.utu.fi/converis/portal/detail/Publication/404756637(external)

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.

1-s2.0-S0304397524002524-main.pdf