On computations over ordered rings

We consider generalized register machines over ordered rings with an auxiliary binary operation. In particular, we consider the ring of integers, its infinite Cartesian power, and ultrapowers. The feasibility and computational complexity of some algorithms are discussed. There is also given an example of a non-factorial ring, which is elementarily equivalent to the ring of integers. It is shown that non-deterministic computations with integers can be implemented as computations over the Cartesian power of the ring of integers. It is also possible to model calculations with an oracle using such machines. This provides an algebraic approach to describing some classes of computational complexity. However, this model of computation differs significantly from alternating machines. Moreover, various types of non-deterministic machines are considered.