On undecidability bounds for matrix decision problems

Bell, Paul

Abstract

In this paper we consider several reachability problems such as vector reachability, membership in matrix semigroups and reachability problems in piecewise linear maps. Since all of these questions are undecidable in general, we work on lowering the bounds for undecidability. In particular, we show an elementary proof of undecidability of the reachability problem for a set of 5 two-dimensional affine transformations. Then, using a modified version of a standard technique, we also prove that the vector reachability problem is undecidable for two (rational) matrices in dimension 11. The above result can be used to show that the system of piecewise linear functions of dimension 12 with only two intervals has an undecidable set-to-point reachability problem. We also show that the “zero in the upper right corner” problem is undecidable for two integral matrices of dimension 18 lowering the bound from 23.

Citation

Bell, P. (2008). On undecidability bounds for matrix decision problems. Theoretical Computer Science, 3 - 13. https://doi.org/10.1016/j.tcs.2007.10.025

• Acceptance Date: Oct 23, 2007
• Publication Date: Feb 4, 2008
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Pages: 3 - 13
• DOI: https://doi.org/10.1016/j.tcs.2007.10.025
• Public URL: https://keele-repository.worktribe.com/output/423607
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S0304397507007840?via%3Dihub