RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Зап. научн. сем. ЛОМИ, 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}…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,…,f_l)$ – класс прф, получаемых из прф $f_1,…,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,…,\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 назв.

Полный текст: PDF файл (381 kB)

Англоязычная версия:
Journal of Soviet Mathematics, 1981, 15:1, 63–67

Реферативные базы данных:

УДК: 51.01, 518.5

Образец цитирования: С. В. Пахомов, “Доказательство несовпадения классов простых примитивно рекурсивных функций”, Теоретические применения методов математической логики. II, Зап. научн. сем. ЛОМИ, 68, Изд-во «Наука», Ленинград. отд., Л., 1977, 115–122; J. Soviet Math., 15:1 (1981), 63–67

Цитирование в формате AMSBIB
\RBibitem{Pak77}
\by С.~В.~Пахомов
\paper Доказательство несовпадения классов простых
примитивно рекурсивных функций
\inbook Теоретические применения методов математической логики.~II
\serial Зап. научн. сем. ЛОМИ
\yr 1977
\vol 68
\pages 115--122
\publ Изд-во «Наука», Ленинград. отд.
\publaddr Л.
\mathnet{http://mi.mathnet.ru/znsl2004}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=536679}
\zmath{https://zbmath.org/?q=an:0449.03031|0358.02045}
\transl
\jour J. Soviet Math.
\yr 1981
\vol 15
\issue 1
\pages 63--67
\crossref{https://doi.org/10.1007/BF01404108}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/znsl2004
  • http://mi.mathnet.ru/rus/znsl/v68/p115

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Записки научных семинаров ПОМИ
    Просмотров:
    Эта страница:144
    Полный текст:41
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020