Исчисления с монотонными выводами и их экономическая интерпретация

Пусть возможные пути развития некоторой системы из начального состояния $X_0$ задаются дедуктивной системой $\langle\mathfrak A;X_0\rangle$ ($X_0$ – аксиома, алгорифм $\mathfrak A$ определяет отношение выводимости за один шаг). Пусть $Y_1,\dots,Y_\ell$ – все состояния, непосредственно выводимые из $X$ (т.е. $\mathfrak A(X)=\{Y_1,\dots,Y_\ell\})$. Пусть $\mathfrak P$ – алгорифм, назначающий для каждого $X$ вероятности перехода $p_1,\dots,p_\ell$, причем $p=1-\sum_{i=1}^\ell p_i$ является вероятностью перехода в специальное состояние останов. $\mathfrak P$ определяет вероятностную меру на множестве всевозможных выводов. Определим информацию в паре $\langle\mathfrak A;X_0\rangle\mathfrak P$ по формуле:
$$ \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$ – вероятность находиться в $X$ непосредственно перед остановом. Рассмотрим $\mathfrak A$, назначающий фиксированное $p$ для каждого $X$ и удовлетворяющий условию $p_1=\dots=p_\ell$. Тогда информация в $\langle\mathfrak A;X_0\rangle$ становится функцией $\text{И}_{\langle\mathfrak A_i;X_0\rangle}(p)$ от одного $p$. Существенная характеристика системы $\langle\mathfrak A;X_0\rangle$ доставляется асимптотикой $\text{И}_{\langle\mathfrak A;X_0\rangle}$ при $p\to0$. Эта характеристика хорошо согласуется с интуитивным представлением об относительной “мощности” исчислений.
Рассмотрим теперь $\text{И}_{\langle\mathfrak A;X_0\rangle}$ как функцию от $X$. Для многих типов систем выгодна стратегия максимизации этой функции (стратегия увеличения свободы выбора); рассмотрим в этой связи простейшие системы экономического характера. Пусть $X,Y,Z$-$n$-мерные вектора с неотрицательными компонентами (компоненты интерпретируются как ресурсы и продукты некоторой экономической системы, $\mathfrak A$ задает технологические возможности преобразования ресурсов). Пусть
$$ Y\in\mathfrak A(X)\Longrightarrow\forall Z(Y+Z\in\mathfrak A(X+Z)). $$

Теорема. {\it Для любого $\langle\mathfrak A;X_0\rangle$ существует такой алгорифм $\mathfrak L(p,\varepsilon)$ полиномиальной сложности ($0<p<1$, $\varepsilon>0$), что:
1) $\mathfrak L(p,\varepsilon)\in\langle\mathfrak A;X_0\rangle$;
2) $\forall Y_{Y\in\langle\mathfrak A;X_0\rangle}(\text{\rm И}_{\langle\mathfrak A;X_0\rangle}(p)\leq \text{\rm И}_{\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))$.
Предположим теперь вместо (1) условие монотонности по ресурсам: $Y\in\mathfrak A(X)\Longrightarrow\forall Z\exists Z'(Y+Z'\in\mathfrak A(X+Z))$. Исчисление $\langle\mathfrak A;X_0\rangle$ назовем слабо разрешимым, если по $X$ можно алгорифмически распознать существование такого $Z$, что $X+Z$ выводимо в $\langle\mathfrak A;X_0\rangle$. При широких предположениях $\langle\mathfrak A;X_0\rangle$ слабо разрешимо, однако существуют неразрешимые системы с $\mathfrak A$, задающим весьма простые технологические возможности.} Изучается также экономическая интерпретация доказанных результатов. Библ. – 9 назв.