Hypercomputation by definition (Q1434375): Difference between revisions

This paper considers computability problems on the border of logic and algebra. The author gives a review of some results concerning decidability of algebraic theories. The main accent is laid on `mediate computability', which is interpreted in the paper as the situation that the whole theory \(T\) has higher complexity than subtheories \(T_n\) with no more than \(n\) distinct variables. In this context the most interesting case seems to be: if \(T_n\) is recursive for all \(n\), but \(T\) is not recursive -- such theories are called pseudorecursive. The question of whether such theories, presented in the article, can be interpreted as decidable is discussed by the author. Especially the idea of concrete extensions of computing models corresponding to finitely based pseudorecursive theories is pointed as unsolved yet. Finally, this situation is indicated as the starting point of some research on the middle ground between recursive and recursively enumerable sets.