  We describe a method to axiomatize computations in deterministic Turing
machines. When applied to computations in non-deterministic Turing machines,
this method may produce contradictory (and therefore trivial) theories,
considering classical logic as the underlying logic. By substituting in such
theories the underlying logic by a paraconsistent logic we define a new
computation model, the paraconsistent Turing machine. This model allows a
partial simulation of superposed states of quantum computing. Such a feature
allows the definition of paraconsistent algorithms which solve (with some
restrictions) the well-known Deutsch's and Deutsch-Jozsa problems. This first
model of computation, however, does not adequately represent the notions of
entangled states and relative phase, which are key features in quantum
computing. In this way, a more sharpened model of paraconsistent Turing
machines is defined, which better approaches quantum computing features.
Finally, we define complexity classes for such models, and establish some
relationships with classical complexity classes.
