A1 Refereed original research article in a scientific journal

On simulating Turing machines with matrix semigroups with integrality tests



Authors: Halava, Vesa; Niskanen, Reino

Publisher: Elsevier

Publication year: 2024

Journal: Theoretical Computer Science

Journal name in source: Theoretical Computer Science

Article number: 114637

Volume: 1005

ISSN: 0304-3975

eISSN: 1879-2294

DOI: https://doi.org/10.1016/j.tcs.2024.114637

Web address : https://www.sciencedirect.com/science/article/pii/S0304397524002524

Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/404756637


Abstract
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.

Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.


Last updated on 2024-26-11 at 22:22