Back to Search
Start Over
DECIDABILITY AND UNIVERSALITY IN THE AXIOMATIC THEORY OF COMPUTABILITY AND ALGORITHMS.
- Source :
- International Journal of Foundations of Computer Science; Nov2012, Vol. 23 Issue 7, p1465-1480, 16p
- Publication Year :
- 2012
-
Abstract
- In this paper, we study to what extent decidability is connected to universality. A natural context for such a study is provided by the axiomatic theory of computability, automata and algorithms. In Section 2, we introduce necessary concepts, constructions, axioms, postulates, conditions and problems. Section 3 contains the main results of the paper. In particular, it is demonstrated (Theorems 1 and 2) that undecidability of algorithmic problems does not depend on existence of universal algorithms and may be caused by weaker conditions. At the same time, results of Theorems 2 and 3 demonstrate that decidability is incompatible with universality. It is also proved (Theorem 5) that sufficiently big classes of total algorithms/automata, such as the class of all primitive recursive functions, cannot have universal algorithms/automata. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 23
- Issue :
- 7
- Database :
- Complementary Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 85190233
- Full Text :
- https://doi.org/10.1142/S012905411240059X