A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On simulating Turing machines with matrix semigroups with integrality tests
Tekijät: Halava, Vesa; Niskanen, Reino
Kustantaja: Elsevier
Julkaisuvuosi: 2024
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: Theoretical Computer Science
Artikkelin numero: 114637
Vuosikerta: 1005
ISSN: 0304-3975
eISSN: 1879-2294
DOI: https://doi.org/10.1016/j.tcs.2024.114637
Verkko-osoite: https://www.sciencedirect.com/science/article/pii/S0304397524002524
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/404756637
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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
