|
Zapiski Nauchnykh Seminarov 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.
Citation:
S. Yu. Maslov, “Calculuses with monotone deductions and their economic interpretation”, Studies in constructive mathematics and mathematical logic. Part VIII, Zap. Nauchn. Sem. LOMI, 88, "Nauka", Leningrad. Otdel., Leningrad, 1979, 90–105; J. Soviet Math., 20:4 (1982), 2314–2321
Linking options:
https://www.mathnet.ru/eng/znsl3106 https://www.mathnet.ru/eng/znsl/v88/p90
|
Statistics & downloads: |
Abstract page: | 259 | Full-text PDF : | 82 |
|