Semantic programming: method of Δ_0^p-enrichments and polynomial analogue of the Gandy fixed point theorem
share
Computer programs fast entered in our life and the questions associated with the execution of these programs have become the most relevant in our days. Programs should work efficiently, i.e. work as quickly as possible and spend as little resources as possible. Most often, such a "measure of efficiency" is the polynomial program execution time of the length of the input data. Such programs have great importance in the direction of smart contracts on blockchain. In this article will be introduced the method of Δ_0^p-enrichments which will show how to switch from the usual polynomial model of M^(0) using Δ_0^p-enrichments to a model with new properties and new elements so that the new model will also be polynomial. Δ_0^p-enrichments: M^(0)→ ... →M^(i)→ ...→M This method based on theory of semantic programming entered in 1970s and 1980s, academics Ershov and Goncharov and professor Sviridenko. New element w for M^(i+1) and not in M^(i) generate with some Δ_0^p-formula Φ_k from family F_j for one place predicate P_j: M^(i)Φ_k(w_1,...,w_n_k), where w is finite list w = <w_1,...,w_n_k> and now M^(i+1) P_j(w). Then we will create an operator Γ_F_P_1^+,...,F_P_N^+^M^(i) and prove polynomial analogue of the Gandy fixed point theorem. It allows us to take a different look on polynomial computability. Let Γ^*: Γ_F_P_1^+,...,F_P_N^+^M(Γ^*) = Γ^* Theorem (polynomial analogue of the Gandy fixed point theorem) Fixed point Γ^* is Δ_0^p-set and P_1,...,P_N - Δ_0^p-predicates on M
READ FULL TEXT