The Orbit Problem is Decidable

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 q 1 to a given state q 2 . Harrison [7] showed that this problem is reducible to the “orbit problem:” Given AεQ n×n does there exist iεN such that A i x =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 {A i x: i = 0,1,2,...}. (A 0 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.

Authors

• Ravindran Kannan
• Richard J. Lipton

Keywords

No keywords are indexed for this paper.