Export Citation
Export Citation
Halava, V and Niskanen, R 
ORCID: 0000-0002-2210-1481
(2024)
On simulating Turing machines with matrix semigroups with integrality tests.
Theoretical Computer Science, 1005.
ISSN 0304-3975
Preview |
Text
On simulating Turing machines with matrix semigroups with integrality tests.pdf - Published Version Available under License Creative Commons Attribution. Download (588kB) | Preview |
Publisher URL: http://doi.org/10.1016/j.tcs.2024.114637
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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | 01 Mathematical Sciences; 08 Information and Computing Sciences; Computation Theory & Mathematics |
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
| Divisions: | Computer Science and Mathematics |
| Publisher: | Elsevier |
| Date of acceptance: | 14 May 2024 |
| Date of first compliant Open Access: | 23 May 2024 |
| Date Deposited: | 23 May 2024 11:33 |
| Last Modified: | 04 Jul 2025 11:45 |
| DOI or ID number: | 10.1016/j.tcs.2024.114637 |
| URI: | https://researchonline.ljmu.ac.uk/id/eprint/23352 |
 |
View Item |