Hypercomputation by definition (Q1434375): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1231120 |
Changed an Item |
||
Property / author | |||
Property / author: Benjamin B. jun. Wells / rank | |||
Normal rank |
Revision as of 16:29, 22 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hypercomputation by definition |
scientific article |
Statements
Hypercomputation by definition (English)
0 references
4 August 2004
0 references
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.
0 references
hypercomputation
0 references
pseudorecursive theory
0 references
varieties of semigroups
0 references
Church-Turing thesis
0 references
decidable theories
0 references
computability
0 references