Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)We describe a method to axiomatize computations in deterministic Turing machines (TMs). When applied to computations in non-deterministic TMs, 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 TMs is defined, which better approaches quantum computing features. Finally, we define complexity classes for such models, and establish some relationships with classical complexity classes.202573595Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)FAPESP [2004/14107-2]