On simulating Turing machines with matrix semigroups with integrality tests

DOI10.1016/J.TCS.2024.114637MaRDI QIDQ6562876FDO

Authors Vesa Halava, Reino Niskanen

Publication date 27 June 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

simulationundecidabilityTuring machinesmatrix semigroupidentity problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3550181 (Why is no real title available?)
• scientific article; zbMATH DE number 1954380 (Why is no real title available?)
• scientific article; zbMATH DE number 7561611 (Why is no real title available?)
• scientific article; zbMATH DE number 7407773 (Why is no real title available?)
• scientific article; zbMATH DE number 7407775 (Why is no real title available?)
• A variant of a recursively unsolvable problem
• Computer Aided Verification
• How hard is it to verify flat affine counter systems with the finite monoid property?
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
• On undecidability bounds for matrix decision problems
• Reachability problems in quaternion matrix and rotation semigroups
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Termination of Integer Linear Programs
• The identity problem in nilpotent groups of bounded class
• Undecidability bounds for integer matrices using Claus instances
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words
• Unsolvability in 3 × 3 Matrices
• What else is undecidable about loops?

This page was built for publication: On simulating Turing machines with matrix semigroups with integrality tests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6562876)