Polynomial-Computable Representation of Neural Networks in Semantic Programming

Abstract

A lot of libraries for neural networks are written for Turing-complete programming languages such as Python, C++, PHP, and Java. However, at the moment, there are no suitable libraries implemented for a p-complete logical programming language L. This paper investigates the issues of polynomial-computable representation neural networks for this language, where the basic elements are hereditarily finite list elements, and programs are defined using special terms and formulas of mathematical logic. Such a representation has been shown to exist for multilayer feedforward fully connected neural networks with sigmoidal activation functions. To prove this fact, special p-iterative terms are constructed that simulate the operation of a neural network. This result plays an important role in the application of the p-complete logical programming language L to artificial intelligence algorithms.

1. Introduction

The conception of semantic programming [1] was developed in the 1970s and 1980s. The main objective of this direction was to create a logical programming language in which programs were given by the basic constructions of mathematical logic such as formulas and terms. A hereditarily finite list superstructure $HW\left(\mathfrak{M}\right)$ of the signature $\sigma$ was chosen as the virtual execution device. At first, the programs were $\Sigma$ and ${{\Delta }}_0$-formulas [2], but this language was Turing-complete [3].

In 2017, Goncharov proposed considering the programs as the terms and presented the conception of conditional terms [4]. In the new L${}_1$ language, L${}_1$-programs and L${}_1$-formulas were inductively specified through the standard terms and ${{\Delta }}_0$-formulas of the signature $\sigma$. The polynomial-computable (p-computable) model $HW\left(\mathfrak{M}\right)$ of the signature $\sigma$ was chosen as a virtual execution device. The authors of [5] showed that any L${}_1$-program and L${}_1$-formula has a polynomial computational complexity. The question arises as to whether all algorithms of polynomial computational complexity can be represented in this language or in its polynomial-computable extensions. This has been an open problem for several years.

Only in 2021 did Goncharov and Nechesov propose the conception of the p-iterative terms [6]. Extension of the L${}_1$ language with p-iterative terms leads to the language L. In [6], it is shown that the class of all L-programs coincides with the class of all algorithms of a polynomial computational complexity P.

The main area of application of semantic programming is artificial intelligence. In artificial intelligence, the black box problem [7] has been around for a long time. Most often, AI gives a result without explaining it. It does not explicitly share how and why it reaches its conclusions. One of the main directions in AI is machine learning [8]. Most machine learning algorithms implemented using neural networks give a result but do not explain it. Our work is the first step toward the separation of artificial intelligence algorithms in the stage where a result can be logically explained and the stage where a result is given without explanation.

The main objective of this paper is to build a polynomial-computable representation [9] for multilayer feedforward fully connected neural networks [10,11] using the basic elements of the model $HW\left(\mathfrak{M}\right)$. This type of neural network plays a great role in many artificial intelligence algorithms [12], and such a library for them in the p-complete logical language L is necessary.

2. Preliminaries

The paper uses the results of the theory of semantic programming [13], which is based on a polynomial-computable hereditarily finite list superstructure $HW\left(\mathfrak{M}\right)$ of a finite signature $\sigma$. The main set of $HW\left(\mathfrak{M}\right)$ consists of the hereditarily finite list elements. The signature $\sigma$ consists of the next constant, operations and predicates:

(1)

$nil$: a constant that selects an empty list;

(2)

$hea{d}^{\left(1\right)}$: returns the last element of the list or is $nil$ otherwise;

(3)

$tai{l}^{\left(1\right)}$: returns a list without the last element or is $nil$ otherwise;

(4)

$getElemen{t}^{\left(2\right)}$: returns the ith element of the list or is $nil$ otherwise;

(5)

$NumElement{s}^{{}^{\left(1\right)}}$: returns the number of elements in the list;

(6)

$firs{t}^{\left(1\right)}$: returns the first element of the list or is $nil$ otherwise;

(7)

$secon{d}^{\left(1\right)}$: returns the second element of the list or is $nil$ otherwise;

(8)

${\in }^{\left(2\right)}$: the predicate “to be an element of a list”;

(9)

${\subseteq }^{\left(2\right)}$: the predicate“to be an initial segment of a list”.

Let us define the conception of L${}_0$-formulas and L${}_0$-programs in the basic language L${}_0$ as ${{\Delta }}_0$-formulas and standard terms of the signature $\sigma$, respectively.

The language L${}_1$ is defined as an inductive extention of the basic language L${}_0$ with conditional terms of the following form:

$$Cond(t_1,{\phi }_1,\cdots ,t_{n+1})=\left\{\begin{array}{c}{t}_0,\mathrm{if}HW\left(\mathfrak{M}\right)\models {\phi }_0\hfill \\ t_1,\mathrm{if}HW\left(\mathfrak{M}\right)\models {\phi }_1\&\neg {\phi }_0\hfill \\ \cdots \hfill \\ t_n,\mathrm{if}HW\left(\mathfrak{M}\right)\models {\phi }_n\&\neg {\phi }_0\&\cdots \&\neg {\phi }_{n-1}\hfill \\ t_{n+1},\mathrm{otherwise}\hfill \end{array}\right.$$

(1)

The conceptions of the L-formula, L-program and p-iterative term are defined as follows.

Basis of induction: Any L${}_1$-program is an L-program, and any L${}_1$-formula is an L-formula.

Induction step: Let $g\left(x\right)$ be an L-program and $\phi \left(x\right)$ be an L-formula, where there is a constant $C_g$ such that for any w, the following inequality is true:

$$\left|g\left(w\right)\right|\le \left|w\right|+C_g$$

(2)

The notation $g^i\left(x\right)$ means the L-program g is applied i times:

$$g^i\left(x\right)=g\left(g^{i-1}\left(x\right)\right)\mathrm{where}{g}^0\left(x\right)=x$$

Suppose that there is a constant $C_g$ such that for any $w\in HW\left(M\right)$, the following is true:

$$\left|g\left(w\right)\right|\le \left|w\right|+C_g$$

The notation of the p-iterative term [6] is defined as follows:

$$Iteratio{n}_{g,\phi }(w,n)=\left\{\begin{array}{c}{g}^i\left(w\right),\mathrm{if}i\le nHW\left(\mathfrak{M}\right)\models \phi \left(g^i\left(w\right)\right)\hfill \\ \mathrm{and}\forall j<iHW\left(\mathfrak{M}\right)⊭\phi \left(g^j\left(w\right)\right)\hfill \\ false,\mathrm{otherwise}\hfill \end{array}\right.$$

(3)

The L-program definitions in the inductive step are as follows:

• $Iteratio{n}_{g,\phi }(t_1,t_2)$ is an L-program, where $g,t_1,t_2$ are L-programs and $\phi$ is an L-formula;
• $Cond(t_1,{\phi }_1,\cdots ,t_n,{\phi }_n,t_{n+1})$ is an L-program, where $t_1,\cdots ,t_{n+1}$ are L-programs and ${\phi }_1,{\phi }_n$ are L-formulas;
• $F(t_1,\cdots ,t_n)$ is an L-program, where $F\in \sigma$ and $t_1,\cdots ,t_n$ are L-programs

The L-formula definitions in the inductive step are as follows:

• $t_1=t_2$ is an L-formula, where $t_1,t_2$ are L-programs;
• $P(t_1,\cdots ,t_n)$ is an L-formula, where $P\in \sigma$ and $t_1,\cdots ,t_n$ are L-programs;
• $\mathsf{\Phi }\&\mathsf{\Psi }$, $\mathsf{\Phi }\vee \mathsf{\Psi }$, $\mathsf{\Phi }\to \mathsf{\Psi }$, $\neg \mathsf{\Phi }$ are L-formulas, where $\mathsf{\Phi }$, $\mathsf{\Psi }$ are L-formulas
• $\exists x\delta t\mathsf{\Phi }$, $\forall x\delta t\mathsf{\Phi }$ are L-formulas, where t is an L-program, $\mathsf{\Phi }$ is an L-formula and $\delta \in \{\in ,\subseteq ,\le \}$.

Theorem 1

((Solution to the problem P = L) [6]). Let $HW\left(\mathfrak{M}\right)$ be a p-computable hereditarily finite list superstructure $HW\left(\mathfrak{M}\right)$ of the finite signature σ. Then, the following are true:

(1) 

Any L-program has polynomial computational complexity.

(2) 

For any p-computable function, there is a suitable L-program that implements it.

In the current work, we modify the conception of the p-iterative term, and instead of the inequality $\left|g\left(x\right)\right|\le \left|x\right|+C_g$, we require fulfillment of some conditions for an L-program g and L-formula $\phi$.

Suppose the L-program $g\left(x\right)$ for a fixed $n\in N$ and some polynomial $h\left(x\right)$ are defined as follows:

$$g\left(w\right)=\left\{\begin{array}{c}{w}^{*},\mathrm{if}w=<w_1,\cdots ,w_n>\hfill \\ false,\mathrm{otherwise}\hfill \end{array}\right.$$

(4)

where $w^{*}=<w_1^{*},\cdots ,w_n^{*}>$ and the following conditions are fulfilled (up to a permutation):

(1)

$|w_1^{*}|\le |w_1|+C·{\sum }_{i=2}^n{\left|w_i\right|}^p$;

(2)

$|w_i^{*}|\le |w_i|$, for all $i\in [2,\cdots ,n]$.

The next lemma almost completely repeats the proof of Theorem 1 from [6]. The same length and complexity estimates are used:

Lemma 1.

The term$Iteratio{n}_{g,\phi }$from Equation (3) with conditions (1–2) from Equation (4) on g is a p-computable function.

3. Neural Networks

This work will consider multilayer feedforward fully connected neural networks of the type in [10] (see also [14,15]), which has one incoming layer, one output layer and several hidden layers. For simplicity of presentation, we will assume that there are no bias neurons in such neural networks. However, all results of this work for neural networks with bias neurons are also valid.

For example, such a neural network with one hidden layer has the following form:

By default, for all neurons of the neural network, the activation function will be a sigmoid of the form:

$$Sig\left(x\right)=\frac{1}{1+e^{-x}}$$

The derivative of this function has the form:

$$Si{g}^{\prime }\left(x\right)=Sig\left(x\right)·(1-Sig\left(x\right))$$

Consider the approximation [16] for the function $e^{-x}$ as the Taylor series expansion up to nine terms of the form:

$$e^{-x}=1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+\cdots +\frac{{(-1)}^n{x}^n}{n!}$$

(5)

Denote the function f as the sigmoid approximation, which uses the Taylor series from Equation (5) for $e^{-x}$. In addition, denote $f^{\prime }\left(x\right)=f\left(x\right)(1-f\left(x\right))$ as an approximation for a derivative function $Si{g}^{\prime }\left(x\right)$:

Remark 1.

$f$and$f^{\prime }$are p-computable functions.

Let $c(x,y):N\times N\to N$ be a standard pair numbering function:

$$c(x,y)=\frac{(x+y+1)·(x+y)}{2}+y,\mathrm{where}x,y\in N$$

Let us define the notation for the mth neuron in kth layer of the neural network N as $n_{c(k,m)}$. Each neuron has the following list representation:

$$\underline{n_i}:<\underline{f},<w_{i{j}_1},\cdots ,w_{i{j}_k}>>$$

where $\underline{f}$ is a constant symbol in a signature $\sigma$ for an activation function and $w_{ij}$ are the weights of the synapses which occur from neuron $n_i$ to neuron $n_j$.

Neuron $n_i$ of the output layer has the form:

$$\underline{n_i}:<\underline{f},<>>$$

Let us define the p-computable predicate $Neuron$ which selects the list encodings of the neurons. A characteristic function for this predicate is defined as follows:

$$Cond(1,\mathsf{\Phi }(x),0)$$

where $Cond$ is a condition term from Equation (1) and $\mathsf{\Phi }\left(x\right)$ has the following form:

$$\begin{array}{c}\mathsf{\Phi }\left(x\right):(first\left(x\right)=\underline{f})\&(NumElements\left(x\right)=2)\&\hfill \\ \&\left(\right(second\left(x\right)=nil)\vee (\forall l\in second\left(x\right)Number\left(l\right))\hfill \end{array}$$

(6)

For some layer with a number i for our neural network, we can define the following code:

$$\underline{s_i}:<\underline{n_{c(i,1)}},\cdots ,\underline{n_{c(i,n_i)}}>$$

(7)

Let us define the p-computable predicate $Layer$ which selects a layer. A characteristic function for this predicate is defined as follows:

$$Cond(1,\mathsf{\Phi }(x),0)$$

where $\mathsf{\Phi }\left(x\right)$ has the form:

$$\begin{array}{c}\mathsf{\Phi }\left(x\right):\forall l\in xNeuron\left(l\right)\hfill \end{array}$$

(8)

Then, the following code is the list encoding for neural network $N_i$:

$$\underline{N_i}:<\underline{s_1},\cdots ,\underline{s_k}>$$

(9)

Let us define the p-computable predicate $NeuralNetwork$ which selects a list encoding of the neural network. A characteristic function for this predicate is defined as follows:

$$Cond(1,\mathsf{\Phi }(x),0);$$

where $\mathsf{\Phi }\left(x\right)$ has the form:

$$\begin{array}{c}\mathsf{\Phi }\left(x\right):\forall l\in xLayer\left(l\right)\&(\forall i\le NumElements(x)-1\forall w\in getElement(x,i)\hfill \\ NumElements\left(second\right(w\left)\right)=NumElements\left(getElement\right(x,i+1\left)\right))\&\hfill \\ \&(\forall w\in head(x\left)second\right(w)=nil)\hfill \end{array}$$

(10)

Remark 2.

Any neural network N is uniquely restored from the list encoding $\underline{N}$.

Consider the p-computable hereditarily finite list superstructure $HW\left(\mathfrak{M}\right)$ of the signature

$${\sigma }^{*}=\sigma \cup \{NeuralNetwor{k}^{\left(1\right)},Laye{r}^{\left(1\right)},Neuro{n}^{\left(1\right)}\}$$

where neural networks are encoded as elements in $HW\left(M\right)$.

Let a be the number. Then, we define a function × as follows:

$$a\times l=\left\{\begin{array}{c}<a·b_1,\cdots ,a·b_k>,\mathrm{where}l=<b_1,\cdots ,a·b_k>\mathrm{and\; all} b_{\mathrm{i}} \mathrm{are\; numbers}\hfill \\ false,\mathrm{otherwise}\hfill \end{array}\right.$$

(11)

Remark 3.

× is a p-computable function.

Let us define the function ⊎ as follows:

$$l\uplus w=\left\{\begin{array}{c}<a_1+b_1,\cdots ,a_k+b_k>,\mathrm{if}l=<a_1,\cdots ,a_k>,w=<b_1,\cdots ,b_k> \mathrm{and\; all} a_i,b_i \mathrm{are\; members}\hfill \\ false,\mathrm{otherwise}\hfill \end{array}\right.$$

(12)

Remark 4.

⊎ is a p-computable function.

Let us define the operation ⊗ as follows:

$$<a_1,\cdots ,a_{m_i}>\otimes \underline{s_i}=\left\{\begin{array}{c}<b_1,\cdots ,b_{m_{i+1}}>,\mathrm{if}{s}_i\mathrm{is}\mathrm{non}\text{-}\mathrm{output}\mathrm{layer}\hfill \\ <c_1,\cdots ,c_{m_i}>,\mathrm{if}{s}_i\mathrm{is}\mathrm{output}\mathrm{layer}\hfill \\ false,\mathrm{otherwise}\hfill \end{array}\right.$$

(13)

where

$$b_m=\sum _{j=1}^{m_i}f\left(a_j\right)·GetElement(second\left(\underline{n_{c(i,j)}}\right),m),m\in [1,\cdots ,m_{i+1}]$$

and where

$$\underline{n_{c(i,j)}}:GetElement(\underline{s_i},j)$$

and

$$c_m=f\left(a_m\right),m\in [1,\cdots ,m_i]$$

Lemma 2.

⊗ is a p-computable function.

Proof. 

We prove this lemma using the construction of the p-iterative term $Iteratio{n}_{g,\phi }$. Let us define the operation of the L-program g for the non-output layer $s_i$ as follows:

$$\begin{array}{c}g(<<a_1,\cdots ,a_{m_i}>,\underline{s_i},<>>)=\hfill \\ =<<a_1,\cdots ,a_{m_i-1}>,tail\left(\underline{s_i}\right),<b_1^{\left(1\right)},\cdots ,b_{m_{i+1}}^{\left(1\right)}>>\hfill \end{array}$$

where

$$<b_1^{\left(1\right)},\cdots ,b_{m_{i+1}}^{\left(1\right)}>=f\left(a_{m_i}\right)\times second\left(head\left(\underline{s_i}\right)\right)$$

and on the jth step, we have

$$\begin{array}{c}g(<<a_1,\cdots ,a_{m_i-j}>,tai{l}^j\left(\underline{s_i}\right),<b_1^{\left(j\right)},\cdots ,b_{m_{i+1}}^{\left(j\right)}>>)=\hfill \\ =<<a_1,\cdots ,a_{m_i-j-1}>,tai{l}^{j+1}\left(\underline{s_i}\right),<b_1^{(j+1)},\cdots ,b_{m_{i+1}}^{(j+1)}>>\hfill \end{array}$$

where the notation $tai{l}^j$ means that the list function $tail$ is applied j times:

$$<b_1^{(j+1)},\cdots ,b_{m_{i+1}}^{(j+1)}>=<b_1^{\left(j\right)},\cdots ,b_{m_{i+1}}^{\left(j\right)}>\uplus f\left(a_j\right)\times second\left(head\left(tai{l}^j\left(\underline{s_i}\right)\right)\right)$$

Using Remarks 3 and 4, we find that g is a p-computable function.

The L-formula $\phi$ is defined as follows:

$$\phi :second\left(x\right)=nil$$

Conditions (1–2) from Equation (4) for the p-iterative term $Iteratio{n}_{g,\phi }$ are met, and therefore, by Lemma 1 the operation ⊗ is a p-computable function where $s_i$ is non-output layer.

If $s_k$ is an output layer, then

$$\begin{array}{c}g(<<a_1,\cdots ,a_{m_k}>,\underline{s_k}>)=<f\left(a_1\right),\cdots ,f\left(a_{m_k}\right)>\hfill \end{array}$$

□

Let us define the operation W as follows:

$$W(<a_1,\cdots ,a_{m_1}>,\underline{N})=<o_1,\cdots ,o_{m_k}>$$

where $\underline{N}=<\underline{s_1},\cdots ,\underline{s_k}>$, $a_i$ is the incoming signals and $o_i$ is the outputs of the output layer neurons:

Lemma 3.

W is a p-computable function.

Proof. 

We prove this fact by construction of a p-iterative term $Iteratio{n}_{g,\phi }$. The function g is defined as follows:

$$g(<<a_1,\cdots ,a_{m_i}>,<\underline{s_i},\cdots ,\underline{s_k}>>)=<<a_1,\cdots ,a_{m_i}>\otimes \underline{s_i},<\underline{s_{i+1}},\cdots ,\underline{s_k}>>$$

The construction g implies that g is a p-computable function.

The L-formula $\phi$ is defined as $head\left(x\right)=nil$.

Conditions (1–2) from Equation (4) for the p-iterative terms $Iteratio{n}_{g,\phi }$ are met, and therefore, by Lemma 1, the function W is a p-computable function. □

Let us define the function O as follows:

$$O(\underline{a},<\underline{s_1},\cdots ,\underline{s_k}>)=<\underline{s{o}_1},\cdots ,\underline{s{o}_k}>$$

where $\underline{s{o}_i}=<o_{c(i,1)},\cdots ,o_{c(i,m_i)}>$ represents the neuron outputs for the ith layer:

Lemma 4.

O is a p-computable function.

Proof. 

The proof almost repeats the proof of Lemma 3 □

The backpropagation [17,18] algorithm will be used to configure the neural network. First, it is necessary to find the coefficients as follows:

$${\delta }_j=\left\{\begin{array}{c}(o_j-t_j)·o_j·(1-o_j),\mathrm{if}\mathrm{j}\mathrm{is}\mathrm{an}\mathrm{output}\mathrm{neuron}\hfill \\ \left(\sum _{l\in L}{w}_{jl}{\delta }_l\right)·o_j·(1-o_j),\mathrm{if}\mathrm{j}\mathrm{is}\mathrm{an}\mathrm{inner}\mathrm{neuron}\hfill \end{array}\right.$$

where $t_j$ is a target output for the jth neuron of the output layer.

The corrective weights are defined by the formula:

$${\Delta }{w}_{ij}=-\eta ·o_i·{\delta }_j$$

where $\eta$ is a learning rate (some fixed constant ordinary from $[0,1]$).

Let $\underline{a}=<a_1,\cdots ,a_{m_1}>$ be an input and $\underline{s{o}_i}$ be the neuron outputs for the ith layer.

Let us define the function ${\Delta }$ as follows:

$${\Delta }(\underline{a},\underline{t},<\underline{s_1},\cdots ,\underline{s_k}>)=<\underline{s{\delta }_1},\cdots ,\underline{s{\delta }_k}>$$

where $\underline{s{\delta }_i}=<{\delta }_{c(i,1)},\cdots ,{\delta }_{c(i,m_i)}>$:

Lemma 5.

Δ is a p-computable function.

Proof. 

We build the p-iterative term $Iteratio{n}_{g,\phi }$, which simulates the operation of a function Δ as follows:

$$\begin{array}{c}g(<<>,<\underline{s{o}_1},\cdots ,\underline{s{o}_k}>,<\underline{s_1},\cdots ,\underline{s_k}>,\underline{t}>)=\hfill \\ =<<\underline{s{\delta }_k}>,<\underline{s{o}_1},\cdots ,\underline{s{o}_k}>,<\underline{s_1},\cdots ,\underline{s_{k-1}}>,<>>\hfill \end{array}$$

where

$${\delta }_{c(k,j)}=(o_{c(k,j)}-t_{c(k,j)})o_{c(k,j)}(1-o_{c(k,j)}),j\in [1,\cdots ,m_k]$$

$$\begin{array}{c}g(<<\underline{s{\delta }_{j+1}},\cdots ,\underline{s{\delta }_k}>,<\underline{s{o}_1},\cdots ,\underline{s{o}_{j+1}}>,<\underline{s_1},\cdots ,\underline{s_j}>,<>>)=\hfill \\ =<<\underline{s{\delta }_j},\cdots ,\underline{s{\delta }_k}>,<\underline{s{o}_1},\cdots ,\underline{s{o}_j}>,<\underline{s_1},\cdots ,\underline{s_{j-1}}>,<>>\hfill \end{array}$$

where

$${\delta }_{c(j,i)}=\left(\sum _{l\in L}{w}_{c(j,i)c(j+1,l)}{\delta }_{c(j+1,l)}\right)o_{c(j,i)}(1-o_{c(j,i)})$$

The L-formula $\phi$ is defined as follows:

$$\phi :head\left(tail\right(x\left)\right)=nil$$

Conditions (1–2) from Equation (4) for the p-iterative term $Iteratio{n}_{g,\phi }$ are met, and therefore, by Lemma 1 the operation ${\Delta }$ is a p-computable function. □

When all the parameters for weight correction are found, the weights can be changed using the formula:

$$w_{ij}^{*}=w_{ij}+{\Delta }{w}_{ij}=w_{ij}-\eta ·o_i·{\delta }_j$$

Let us define the function T as follows:

$$T(<<\underline{s_1},\cdots ,\underline{s_k}>,<\underline{s{o}_1},\cdots ,\underline{s{o}_k}>,<\underline{s{\delta }_1},\cdots ,\underline{s{\delta }_k}>>)=<{\underline{s_1}}^{*},\cdots ,{\underline{s_k}}^{*}>$$

where the weights of the neurons $\underline{n_i^{*}}\in {\underline{s_m}}^{*}$ are derived from the weights of the neurons $\underline{n_i}\in \underline{s_m}$ by adding ${\Delta }{w}_{ij}$, where $j\in [1,\cdots ,m_{i+1}]$:

Lemma 6.

T is a p-computable function.

Proof. 

The proof of this lemma is achieved by constructing a suitable p-iterative term $Iteratio{n}_{g,\phi }$ as well as Lemma 5. □

The following theorem statement follows automatically from Remarks 3 and 4 and Lemmas 2–6:

Theorem 2.

Let $HW\left(\mathfrak{M}\right)$ of the signature σ be a p-computable model.

Then, $HW\left(\mathfrak{M}\right)$ of the signature $\sigma \cup \{NeuralNetwork,Layer,Neuron\}\cup \{\times ,\uplus ,\otimes ,W,O,{\Delta },T\}$ is a p-computable model.

4. Materials and Methods

This paper used the main tools and methods of semantic programming such as p-iteration terms, conditional terms and a p-computable hereditarily finite list superstructure $HW\left(\mathfrak{M}\right)$ of the signature $\sigma$. These techniques allowed us to encode the elements of the multilayer feedforward fully connected neural networks with a sigmoidal activation function using hereditarily finite lists so that the p-iterative term satisfied conditions (1–2) from Equation (4) simulated the operation of the neural network itself. Moreover, the construction of the p-iterative term guarantees polynomial computational complexity of the neural network operation, as well as the backpropagation algorithm.

5. Results

The main result of this work is the construction of a polynomial-computable representation for a multilayer feedforward fully connected neural network with the sigmoidal activation function for a p-complete logical programming language L. This result is equivalent to the statement of the Theorem 2 and allows the introduction and use of neural networks as a basic library of L.

6. Discussion

A polynomial-computable representation of neural networks in the p-complete logical programming language L is extremely important in practice. This allows artificial intelligence algorithms to be implemented without the problems that arise in Turing-complete languages. One such problem is the halting problem.

An open question is the existence of polynomial-computable representations for other types of neural networks, such as recurrent neural networks [19], and modular neural networks [20]. Most often, the answer to the existence of such representations for neural networks in a general case will be negative. Is it possible to find such limitations for such a representation should exist?

Moreover, we are interested not only in the existence of such representations but also constructive implementations within the framework of the theory of semantic programming and p-complete language L.

7. Conclusions

This paper shows a constructive method for polynomial-computable representation of neural networks in the p-complete logical programming language L. Now, we can add a library for neural networks to the p-complete language L, which will allow us to implement algorithms both using a logical language and neural networks. Neural networks play a great role in any direction of AI, so this p-computable representation will help expand the expressive power of our core language L.

Since accuracy, speed and a logical explanation of the result are important criteria for the implementation of artificial intelligence algorithms, the given p-complete logical programming language L solves artificial intelligence problems much better than a similar implementation in Turing-complete languages. Moreover, in this language, there is no halting problem, which is very important for the stability and reliability of software solutions.

The main applications of this result are blockchains, smart contracts, robotics and artificial intelligence. Moreover, these results will be applied in the conception of building smart cities [21], where almost all possible options for artificial intelligence are involved: image recognition, data mining, machine learning, neural networks, smart contracts, robotics, finance based on cryptocurrencies and blockchains.