Undecidability and Complexity for Super-Turing Models of Computation

Abstract

It seems that intelligent complex systems will require formalisms having richer behavior than Turing machines. Very little is known about the relations (e.g., the expressiveness and/or effectiveness) between new super-Turing models of computation. The objective of this paper is an attempt to establish a hierarchy of expressiveness of super-Turing models. Truly, a new theory of undecidability and complexity for super-Turing models has to be developed. Some preliminary steps have been done in this paper by introducing a-decidable and i-decidable algorithms and U-complete, D-complete, and H-complete complexity classes that were inspired by NP-complete and PSPACE-complete classes for intractable problems. This paper should be understood as a preliminary step leading to feasible approximate solutions of Turing machine undecidable problems, in a similar way as approximate, randomized, and parallel algorithms allow for feasible solutions for intractable problems.

Keywords

• undecidability
• intractability
• super-Turing computation
• super-recursive algorithms
• a-decidability
• i-decidability