Reachability problems in quaternion matrix and rotation semigroups
We examine computational problems on quaternion matrix and rotation semigroups. It is shown that in the ultimate case of quaternion matrices, in which multiplication is still associative, most of the decision problems for matrix semigroups are undecidable in dimension two. The geometric interpretation of matrix problems over quaternions is presented in terms of rotation problems for the 2- and 3-sphere. In particular, we show that the reachability of the rotation problem is undecidable on the 3-sphere and other rotation problems can be formulated as matrix problems over complex and hypercomplex numbers. (c) 2008 Elsevier Inc. All rights reserved.
quaternions rotation semigroups matrix semigroups undecidability membership problem post's correspondence problem