Another Look at Computability.
Florentin Ipate, Mike Holcombe · 1996
The theory of computable functions is well known and has given rise to many classes of computational models of varying power and usefullness. We take another look at this subject using the idea of a generalised machine the X-machine to provide some further insights into the issue and to discuss an elegant general approach to the question of classifying computational models including some of the socalled Super-Turing models. This paper investigates a number of classes of X-machines. It considers their relative computational capabilities and contrasts these with other important models. It is shown that a certain class of these machines the 2-stack straight move stream X-machine computes precisely the class of partial recursive functions. The importance of this work to the theory of testing of systems is