RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1979 Volume 88, Pages 90–105 (Mi znsl3106)

Calculuses with monotone deductions and their economic interpretation

S. Yu. Maslov


Abstract: 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.

UDC: 510.66


 English version:
Journal of Soviet Mathematics, 1982, 20:4, 2314–2321

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024