|
In recent years the Church-Turing thesis has been subjected to several nontrivial revisions - not in the sense of refuting the thesis but in the sense of generalizing or refining it.
An approach initiated by Yuri Gurevich in the 1980s replaces the TM model with the more evolved abstract state machine (ASM) model. While abstract state machines yield the same class of algorithmically solvable problems as Turing machines, the ASM model has good claims to be a more direct formal counterpart of the intuitive notion of algorithm than the TM model is. This is an attempt to bridge the gap between formal models of computation and practical specification methods.
Within the approach called computability logic, which was initiated by Giorgi Japaridze in 2003, the Church-Turing thesis is generalized to the interactive level, providing a mathematical model of computation corresponding to our intuitive concept of interactive algorithm. Among the motivations for this approach is that, while most of the (algorithmic) tasks that computers perform are interactive, the TM model, as recognized by Turing himself, only captures the essentially non-interactive subclass of the entities that our intuitive notion of algorithms includes.
|