✦ LIBER ✦

Augmented loop languages and classes of computable functions

✍ Scribed by Michael Machtey

Publisher: Elsevier Science
Year: 1972
Tongue: English
Weight: 1024 KB
Volume: 6
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(72)80032-1

No coin nor oath required. For personal study only.

✦ Synopsis

A classification of all the computable functions is given in terms of subrecursive programming languages. These classes are those which arise from the relation "primitive recursive in." By distinguishing between honest and dishonest classes the classification is related to the computational complexity of the functions classified, and the classification has a wide degree of measure invariance. The structure of the honest and dishonest classes under inclusion is explored. It is shown that any countable partial ordering can be embedded in the dishonest classes, and that the dishonest classes are dense in the honest classes. Every honest class is minimal over some dishonest class, but there are dishonest classes with no honest class minimal over them.

📜 SIMILAR VOLUMES

Completeness problems in classes of comp

Completeness problems in classes of computable named functions

✍ D. B. Bui; B. V. Gubskii; V. N. Red'ko 📂 Article 📅 1989 🏛 Springer US 🌐 English ⚖ 988 KB

Growth functions of some classes of lang

Growth functions of some classes of languages

✍ V. I. Trofimov 📂 Article 📅 1981 🏛 Springer US 🌐 English ⚖ 396 KB

Derivatives of Computable Functions

✍ Ning Zhong 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 665 KB

## Abstract As is well known the derivative of a computable and __C__^1^ function may not be computable. For a computable and __C__∞ function __f__, the sequence {__f__^(__n__)^} of its derivatives may fail to be computable as a sequence, even though its derivative of any order is computable. In th

Dm-automata and classes of context-free

Dm-automata and classes of context-free languages

✍ A. B. Stavrovskii; O. Yu. Pavliv 📂 Article 📅 1993 🏛 Springer US 🌐 English ⚖ 520 KB

Uniformly computable aspects of inner fu

Uniformly computable aspects of inner functions: estimation and factorization

✍ Timothy H. McNicholl 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB

## Abstract The theory of inner functions plays an important role in the study of bounded analytic functions. Inner functions are also useful in applied mathematics. Two foundational results in this theory are Frostman's Theorem and the Factorization Theorem. We prove a uniformly computable version

On algebraic and logical specifications

On algebraic and logical specifications of classes of regular languages

✍ Bakhadyr Khoussainov 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 231 KB

The paper studies classes of regular languages based on algebraic constraints imposed on transitions of automata and discusses issues related to speciÿcations of these classes from algebraic, computational and logical points of view.