Turing’s theorem

Are there any noncomputable numbers They are certain to exist since the cardinality of the set of all possible programs (which is equal to that of the integers) is less than the cardinality of the set of reals. It is, in fact, easy to construct a noncomputable number, using Turing s Halting Theorem number, in some arbitrary manner, all possible programs that run with, say, a single input instruction Pi (-> l,p2 2,...,pn n,..., and set ( = n2, where q = 1 if the... 

The previous theorem can be generalized to several other paraconsistent logics, that is, to those where a conservatively translation function from CPL can be defined taking into account that such translation function must be effectively calculated. In the other direction, the existence of uniform families of boolean circuits to every uniform family of L-circuits (for any logic L provided with PRC) is guaranteed by the classical computability of roots for polynomials over finite fields. Then, the L-circuits model does not invalidate Church-Turing s thesis. 

Cook s theorem (cf. [10]) states that any NP-problem can be converted to the satisfiability problem in CPL in poljmomial time. The proof shows, in a constructive way, how to translate a Turing machine into a set of CPL formulas in such a way that the machine outputs T if, and only if, the formulas are consistent. As mentioned in the introduction, a model of paraconsistent Turing machines presented in [1] was proved to solve Deutsch-Jozsa problem in an efficient way. We conjecture that a similar result as Cook s theorem can be proven to paraconsistent Turing machines. In this way, paraconsistent circuits could be shown to efficiently solve Deutsch-Jozsa problem. Consequences of this approach would be the definition of non-standard complexity classes relative to such unconventional models of computation founded over non-classical logics. 

---