On simulating Turing machines with matrix semigroups with integrality tests

DOI10.1016/J.TCS.2024.114637MaRDI QIDQ6562876

Reino Niskanen, Vesa Halava

Publication date: 27 June 2024

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

zbMATH Keywords

undecidabilitysimulationTuring machinesmatrix semigroupidentity problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Reachability problems in quaternion matrix and rotation semigroups
• How hard is it to verify flat affine counter systems with the finite monoid property?
• On undecidability bounds for matrix decision problems
• Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• Computer Aided Verification
• Unsolvability in 3 × 3 Matrices
• Termination of Integer Linear Programs
• A variant of a recursively unsolvable problem
• What else is undecidable about loops?
• The identity problem in nilpotent groups of bounded class

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)