Hypercomputation by definition (Q1434375)

From MaRDI portal
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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references