|
Записки научных семинаров ЛОМИ, 1977, том 68, страницы 115–122
(Mi znsl2004)
|
|
|
|
Доказательство несовпадения классов простых
примитивно рекурсивных функций
С. В. Пахомов
Аннотация:
Пусть $X$, $Y$ – классы примитивно рекурсивных функций (сокращенно
прф) и пусть требуется доказать следующее утверждение:
(1) неверно, что всякая функция из класса $X$ принадлежит
классу $Y$. Такое утверждение обычно доказывается указанием
прф из класса $X$, растущей быстрее любой прф из класса $Y$,
или “простой” прф, например $\lambda x(x+1)$, $\lambda xy(x+y)$, из класса $X$,
которая не принадлежит классу $Y$. Предлагается метод, позволяющий
доказывать утверждения вида (1) для некоторых классов прф
и $Y$ таких, что во-первых, функции класса $X$ растут не быстрее
функций класса $Y$, во-вторых, класс $Y$ содержит “простые” прф,
такие как $\lambda xy(x+y)$, $\lambda xy(x-y)$ и др.
Предлагаемый метод заключается в следующем. Выбирается некоторый
класс прф $Z$ и для каждой прф $f$ строится такая операция $\delta_f$ над функциями из класса $Z$, что для всякой $f$ из $Y$ класс $Z$ замкнут относительно операции $\delta_f$, с другой стороны
неверно, что для всякой $f$ из $X$ класс $Z$ замкнут относительно $\delta_f$.
Опишем одно из возможных применений предлагаемого метода.
Не будем различать словарные и числовые прф и предикаты, имея в виду следующее взаимно однозначное соответствие между словами в алфавите $\{1,2\}$ и натуральными числами: слову $a_na_{n-1}\dots a_1a_0$ в алфавите $\{1,2\}$ соответствует число $\sum^n_{i=0}a_i2^1$. Пусть $\nu(x,i)$
равно $i$-ому знаку в слове $x$ (последняя буква считается
$0$-ым знаком), $|x|$–длина $x$; $\operatorname{con}(x,y)$ – результат приписывания
справа к слову $x$ слова $y$; $\theta$, $\overline\theta$ – характеристические функции
равенства и неравенства. Пусть $RF$ – класс прф, получаемых
из прф $\theta$, $\overline\theta$, $\operatorname{con}$, $\lambda x0$, $\sigma$, $I^n_k$ посредством операции ограниченной минимизации и подстановки функций. Отметим, что класс отношений класса $RF$ равен классу рудиментарных отношений. Пусть $R_sF(f_1,\dots,f_l)$ – класс прф, получаемых из прф $f_1,\dots,f_l$ посредством операции подстановки и операции, ставящей в соответствие функции $g$, такую $f$, что $f(\overline x,y)=\mu t_{\leqslant y}[tPy\& g(\overline x,t)=0]$, где $tPy\leftrightharpoons t$ – подслово $y$. Отметим, что характеристическая функция всякого $s$-рудиментарного предиката принадлежит $R_sF_\alpha(\theta,\overline\theta,\operatorname{con},\lambda x0,\sigma,I^n_k)$. В качестве $Z$ возьмем класс таких $\alpha$ из $RF$, которые принимают значения 0, 1, 2 и если $\alpha(\overline z,i)=0$, то $\forall\,k[\alpha(\overline z,i+k)=0]$. Операция $\delta_f$, такова, что $[\delta_f(\alpha_1,\dots,\alpha_n)](\overline x,\overline z,j)=\nu(f(\sum^{x_1}_{i=0}\alpha_1(\overline z,i),2^i),j)$. Предложенным методом можно доказать утверждение вида (1), если в качестве $X$ взять $RF$, в качестве $Y-R_sF_\alpha(\theta,\overline\theta,\operatorname{con},\lambda x0,\sigma,I^n_k,\lambda xy(x+y),\lambda xy(x-y),\lambda xf(|x|),\lambda x2^{g(|x|)})$, где $f$ и $g$ принадлежат классу $RF$. Библ. 7 назв.
Образец цитирования:
С. В. Пахомов, “Доказательство несовпадения классов простых
примитивно рекурсивных функций”, Теоретические применения методов математической логики. II, Зап. научн. сем. ЛОМИ, 68, Изд-во «Наука», Ленинград. отд., Л., 1977, 115–122; J. Soviet Math., 15:1 (1981), 63–67
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl2004 https://www.mathnet.ru/rus/znsl/v68/p115
|
Статистика просмотров: |
Страница аннотации: | 186 | PDF полного текста: | 48 |
|