Hypercomputation by definition

DOI10.1016/J.TCS.2003.12.011MaRDI QIDQ1434375zbMATH OpenOpenAlexFDO

Publication date 4 August 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2003.12.011

Church-Turing thesis computability decidable theories hypercomputation pseudorecursive theory varieties of semigroups

Equational classes, universal algebra in model theory (03C05) Complexity of computation (including implicit computational complexity) (03D15) Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40) Varieties and pseudovarieties of semigroups (20M07) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

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.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Hypercomputation by definition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1434375)