The orbit problem is decidable
Ravindran Kannan, Richard J. Lipton · 1980
The “accessibility problem” for linear sequential machines (Harrison [7]) is the problem of deciding whether there is an input x that sends such a machine from a given state q1 to a given state q2. Harrison [7] showed that this problem is reducible to the “orbit problem:” Given AεQn×n does there exist iεN such that Aix =y.* We will call this the “orbit problem” because the question can be rephrased as: Does y belong to the orbit of x under A where the “orbit of x under A” is the set {Aix: i = 0,1,2,...}. (A0 is the identity matrix I.) In Harrison's original problem the elements of A,x, and y were members of an arbitrary “computable” field. In view of the lack of structure of such fields, we study only the rationals. Shank [13] proves that the orbit problem is decidable for the rational case when n=2. The current paper establishes that for the general rational case, the problem is decidable - and in fact polynomial-time decidable.