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