Calculuses with monotone deductions and their economic interpretation

S. Yu. Maslov

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VIII, Tome 88 (1979), pp. 90-105

Résumé

Let the possible ways of development of some system from an initial state $X_0$ be given by a deductive system $\langle\mathfrak A;X_0\rangle$ ($X_0$ is the axiom, the algorithm $\mathfrak A$ defines the relation of onestep deducibility. Let $Y_1,\dots,Y_\ell$ be all the states which are onestep deducible from $X$ (i.e. $\mathfrak A(X)=\{Y_1,\dots,Y_\ell\})$. Let $\mathfrak P$ be an algorithm assigning to every $X$ the transition probabilityes $p_1,\dots,p_\ell$ and $p=1-\sum_{1\leq i\leq\ell}p_i$ be the probability of the transition to the special state STOP. $\mathfrak P$ defines a probabilistic measure on the set of all deduction. The information in the pair $\langle\mathfrak A;X_0\rangle$, $\mathfrak P$ is defined by the formuls: $$ \text{И}_{\langle\mathfrak A;X_0\rangle},\mathfrak P =-\sum_{X\in\langle\mathfrak A;X_0\rangle}p_X\log_2p_X, $$ ($p_X$ is the probability of $X$ being the last state before STOP). Consider $\mathfrak A$ assigning the fixed $p$ to every $X$ and satisfying the condition $p_1=\dots=p_\ell$. Then the information in $\langle\mathfrak A;X_0\rangle$ becomes the function $\text{И}_{\langle\mathfrak A;X_0\rangle}(p)$ of $p$ only. The essential characteristic of $\langle\mathfrak A;X_0\rangle$ is given by the assymptotics of $\text{И}_{\langle\mathfrak A;X_0\rangle}$ as $p\to0$. This characteristic has a good correspondence with intuitive notions about relative “power” of calculuses. Now let us consider $\text{И}_{\langle\mathfrak A;X_0\rangle}(p)$ as a function of $X$. For many kinds of actual systems the strategy of favorable development has a strong correlation with maximizing this function; let us consider here the simplest variant systems of economical character. Let $X,Y,Z$ stand for $n$-ary vectors with nonnegative integer components. In interpretation the components are resourses (and products), $\mathfrak A$ represents the technological possibilities of transformations of resourses. Assume $$ Y\in\mathfrak A(X)\Longrightarrow\forall Z(Y+Z\in\mathfrak A(X+Z)). $$ Theorem. {\it For every $\langle\mathfrak A;X_0\rangle$ there exists such an algorithm $\mathfrak L(p,\varepsilon)$ of polinomial complexity ($0<p<1$, $\varepsilon>0$) that: 1) $\mathfrak L(p,\varepsilon)\in\langle\mathfrak A;X_0\rangle$; 2) $\forall Y_{Y\in\langle\mathfrak A;X_0\rangle} (\text{И}_{\langle\mathfrak A;X_0\rangle}(p)\leq \text{И}_{\langle\mathfrak A; \mathfrak L(p,\varepsilon)\rangle}(p)+\varepsilon)$; 3) $\exists\bar p(\bar p>0\&\forall p_1p_2\varepsilon_1\varepsilon_2 (\bar p\geq p_1\geq p_2\&\varepsilon_1\geq\varepsilon_2 \Longrightarrow\mathfrak L(p_2,\varepsilon_2)\in\langle\mathfrak A; \mathfrak L(p_1,\varepsilon_1)\rangle))$. Instead of (1) now assume the condition of monotonicity $Y\in\mathfrak A(X)\Longrightarrow\forall Z\exists Z'(Y+Z'\in\mathfrak A(X+Z))$. System $\langle\mathfrak A;X_0\rangle$ is weak-decidible if for every $X$ we can algorithmically recognize an existence of such $Z$ that $X+Z$ is deducible in $\langle\mathfrak A;X_0\rangle$. Under broad conditions $\langle\mathfrak A;X_0\rangle$ is weak-decidable, but there are undecidable systems for $\mathfrak A$ which describe very symple technological possibilities.} The economical interpretation of results is studied.