Polynomial analogue of gandy’s fixed point theorem Full article
| Journal |
Mathematics
, E-ISSN: 2227-7390 |
||
|---|---|---|---|
| Output data | Year: 2021, Volume: 9, Number: 17, Article number : 2102, Pages count : DOI: 10.3390/math9172102 | ||
| Tags | Computer science; Gandy’s fixed point theorem; P-computability; Polynomial computability; Polynomial operators; Semantic programming; ∆p0-operators | ||
| Authors |
|
||
| Affiliations |
|
Abstract:
The paper suggests a general method for proving the fact whether a certain set is p-computable or not. The method is based on a polynomial analogue of the classical Gandy’s fixed point theorem. Classical Gandy’s theorem deals with the extension of a predicate through a special operator ΓΩ∗ and states that the smallest fixed point of this operator is a Σ-set. Our work uses Φ(x) a new type of operator which extends predicates so that the smallest fixed point remains a p-computable set. Moreover, if in the classical Gandy’s fixed point theorem, the special Σ-formula Φ(x) is used in the construction of the operator, then a new operator uses special generating families of formulas instead of a single formula. This work opens up broad prospects for the application of the polynomial analogue of Gandy’s theorem in the construction of new types of terms and formulas, in the construction of new data types and programs of polynomial computational complexity in Turing complete languages. © 2021 by the authors. Licensee MDPI, Basel, Switzerland.
Cite:
Goncharov S.
, Nechesov A.
Polynomial analogue of gandy’s fixed point theorem
Mathematics. 2021. V.9. N17. 2102 . DOI: 10.3390/math9172102 WOS Scopus OpenAlex
Polynomial analogue of gandy’s fixed point theorem
Mathematics. 2021. V.9. N17. 2102 . DOI: 10.3390/math9172102 WOS Scopus OpenAlex
Identifiers:
| Web of science: | WOS:000694371300001 |
| Scopus: | 2-s2.0-85114235544 |
| OpenAlex: | W3196772415 |