On simulating Turing machines with matrix semigroups with integrality tests

Tietueen suppeat tiedot
dc.contributor.authorHalava, Vesa
dc.contributor.authorNiskanen, Reino
dc.contributor.organizationfi=matematiikka|en=Mathematics|
dc.contributor.organization-code1.2.246.10.2458963.20.41687507875
dc.converis.publication-id404756637
dc.converis.urlhttps://research.utu.fi/converis/portal/Publication/404756637
dc.date.accessioned2025-08-27T21:41:33Z
dc.date.available2025-08-27T21:41:33Z
dc.description.abstractWe 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.
dc.identifier.eissn1879-2294
dc.identifier.jour-issn0304-3975
dc.identifier.olddbid200892
dc.identifier.oldhandle10024/183919
dc.identifier.urihttps://www.utupub.fi/handle/11111/47294
dc.identifier.urlhttps://www.sciencedirect.com/science/article/pii/S0304397524002524
dc.identifier.urnURN:NBN:fi-fe2025082785171
dc.language.isoen
dc.okm.affiliatedauthorHalava, Vesa
dc.okm.discipline111 Mathematicsen_GB
dc.okm.discipline111 Matematiikkafi_FI
dc.okm.internationalcopublicationinternational co-publication
dc.okm.internationalityInternational publication
dc.okm.typeA1 ScientificArticle
dc.publisherElsevier
dc.publisher.countryNetherlandsen_GB
dc.publisher.countryAlankomaatfi_FI
dc.publisher.country-codeNL
dc.relation.articlenumber114637
dc.relation.doi10.1016/j.tcs.2024.114637
dc.relation.ispartofjournalTheoretical Computer Science
dc.relation.volume1005
dc.source.identifierhttps://www.utupub.fi/handle/10024/183919
dc.titleOn simulating Turing machines with matrix semigroups with integrality tests
dc.year.issued2024

Tiedostot

Näytetään 1 - 1 / 1
Name:
1-s2.0-S0304397524002524-main.pdf
Size:
574.75 KB
Format:
Adobe Portable Document Format
Lataa

Kokoelmat

Rinnakkaistallenteet