Understanding the Computational Complexity of Diverse Classes of Turing and Super-Turing Computational Models
Ghada Abdelmoumin, Chunmei Liu, Danda B. Rawat · 2023
The need to solve scientific problems using automated means and hence analyze the performance and measure the complexities of their algorithmic solutions had led to the realization of various computational models. The underlying of these computational models are the mathematical models that provide intuitions for the problems in question and formally describe the problem(s) to be solved by a particular model. In the heart of these models of computations is the Turing Machines abstractions model, a mathematical model of computation that formed the basis of successive models of computations and provided the theoretical foundation of computability. In this paper, we explore various classes of computational models and intuitively understand their computational complexity. We focus on different Turing and super-Turing models of computations and study their complexity in terms of space and time. We provide a comparative analysis of infinitary, fuzzy, hyper and super-Turing models using computational characteristics pertinent to Turing computational models in general. Further, we show the conjectured relationships of the four models to the Turing machines and universal Turing machine.