Polynomial Analogue of Gandy’s Fixed Point Theorem

Sergey Goncharov and Andrey Nechesov
Additional contact information
Sergey Goncharov: Sobolev Institute of Mathematics, Academician Koptyug Ave., 4, 630090 Novosibirsk, Russia
Andrey Nechesov: Sobolev Institute of Mathematics, Academician Koptyug Ave., 4, 630090 Novosibirsk, Russia

Mathematics, 2021, vol. 9, issue 17, 1-11

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 ? ? ( x ) ? ? and states that the smallest fixed point of this operator is a ? -set. Our work uses 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.

Keywords: polynomial computability; p-computability; Gandy’s fixed point theorem; semantic programming; polynomial operators; ? 0 p; computer science (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/17/2102/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/17/2102/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:17:p:2102-:d:625932

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().