Tools
Tools
Halava, V and Niskanen, R (2024) On simulating Turing machines with matrix semigroups with integrality tests. Theoretical Computer Science, 1005. ISSN 0304-3975
|
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 & Mathematics |
| Publisher: | Elsevier |
| SWORD Depositor: | A Symplectic |
| Date Deposited: | 23 May 2024 11:33 |
| Last Modified: | 29 May 2024 09:00 |
| DOI or ID number: | 10.1016/j.tcs.2024.114637 |
| URI: | https://researchonline.ljmu.ac.uk/id/eprint/23352 |
 |
View Item |