Polynomial Analogue of Gandy’s Fixed Point Theorem

Sergey Goncharov; Andrey Nechesov

doi:10.3390/math9172102

journal article Open Access Aug 31, 2021

Polynomial Analogue of Gandy’s Fixed Point Theorem

Sergey Goncharov

Andrey Nechesov

Mathematics Vol. 9 No. 17 pp. 2102 · MDPI AG

View at Publisher Save 10.3390/math9172102

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.

Topics

No keywords indexed for this article. Browse by subject →

References

14

[1]

Barwise, J. (1975). Admissible Sets and Structures, Springer. 10.1007/978-3-662-11035-5

[2]

Ershov, Y.L. (1996). Definability and Computability, Springer.

[3]

Lewis, H., and Papadimitriou, C. (1998). Elements of the Theory of Computation, Prentice-Hall. 10.1145/300307.1040360

[4]

Alaev "Structures Computable in Polynomial Time" Algebra Log. (2017) 10.1007/s10469-017-9416-y

[5]

Alaev "Existence and Uniqueness of Structures Computable in Polynomial Time" Algebra Log. (2016) 10.1007/s10469-016-9377-6

[6]

Alaev "Polynomial computability of fields of algebraic numbers" Dokl. Math. (2018) 10.1134/s1064562418050137

[7]

Cenzer "Polynomial-time versus recursive models" Ann. Pure Appl. Log. (1991) 10.1016/0168-0072(91)90008-a

[8]

Ospichev "On the complexity of formulas in semantic programming" Sib. Electron. Math. Rep. (2018)

[9]

Conditional terms in semantic programming

S. S. Goncharov

Siberian Mathematical Journal 2017 10.1134/s0037446617050068

[10]

Ershov, Y.L., Goncharov, S.S., and Sviridenko, D.I. (1986, January 1–5). Semantic programming. Proceedings of the Information Processing 86: IFIP 10th World Computer Congress, Dublin, Ireland.

[11]

Goncharov "Logical language of description of polynomial computing" Dokl. Math. (2019) 10.1134/s1064562419020030

[12]

Goncharov "Recursive terms in semantic programming" Sib. Math. J. (2018) 10.1134/s0037446618060058

[13]

Goncharov "The expressiveness of looping terms in the semantic programming" Sib. Electron. Math. Rep. (2020)

[14]

Goncharov "Σ-programming" Transl. II. Ser. Am. Math. Soc. (1989) 10.1090/trans2/142/10

Metrics

11

Citations

14

References

Details

Published: Aug 31, 2021
Vol/Issue: 9(17)
Pages: 2102
License: View

Authors

S

Sergey Goncharov

Sobolev Institute of Mathematics, Academician Koptyug Ave., 4, 630090 Novosibirsk, Russia

A

Andrey Nechesov

Sobolev Institute of Mathematics, Academician Koptyug Ave., 4, 630090 Novosibirsk, Russia

Cite This Article

Sergey Goncharov, Andrey Nechesov (2021). Polynomial Analogue of Gandy’s Fixed Point Theorem. Mathematics, 9(17), 2102. https://doi.org/10.3390/math9172102

Polynomial Analogue of Gandy’s Fixed Point Theorem

You May Also Like