Approximability of some program models by others (Q1858999)

The paper is devoted to the program model theory. The notion of scheme (a formalization of program algorithm) is defined as a special graph with two marked nodes - input and output. Two schemes can realize one program, if the same input implies the same output. The weaker condition, when two schemes gave the same output for any input signals \textit{from a given class}, is called \textit{equivalence of the schemes} (with respect to this class of input signals). A set of schemes with a given equivalence is called \textit{model}. For two given models \(L\) and \(M\) they say that -- \(L\) \textit{approximates} \(M\), if for any two schemes \(G_1\) and \(G_2\) their equivalence in \(M\) implies their equivalence in \(L\): \[ G_1\sim G_2 \;(mod\, M) \quad \Longrightarrow\quad G_1\sim G_2\; (mod \,L) \] -- \(L\) \textit{is equivalent} to \(M\), if for any two schemes \(G_1\) and \(G_2\) their equivalence in \(M\) is the same as their equivalence in \(L\): \[ G_1\sim G_2 \;(mod\, M) \quad \Longleftrightarrow\quad G_1\sim G_2\; (mod \,L) \] The author gives some necessary and sufficient conditions for approximability and equivalence of models.