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

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

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



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






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


Матем. сб., 2015, том 206, номер 9, страницы 3–20 (Mi msb8519)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

О некоторых медленно сходящихся системах преобразований термов

Л. Д. Беклемишевa, А. А. Оноприенкоb

a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва
b Механико-математический факультет, Московский государственный университет имени М. В. Ломоносова

Аннотация: Формулируются системы преобразований термов, число шагов работы которых на произвольном входе конечно, но не ограничивается никакой вычислимой функцией, доказуемо тотальной в арифметике Пеано $\mathsf{PA}$. Тем самым, утверждение о сходимости таких систем не доказуемо в $\mathsf{PA}$. Эти системы получаются из независимого комбинаторного утверждения, известного как принцип червя; их также можно рассматривать как вариант хорошо известной игры Геракла и гидры, введенной Дж. Парисом и Л. Кирби.
Библиография: 16 названий.

Ключевые слова: системы преобразований термов, арифметика Пеано, принцип червя.

Финансовая поддержка Номер гранта
Российский научный фонд 14-50-00005
Исследование Л. Д. Беклемишева выполнено за счет гранта Российского научного фонда (проект № 14-50-00005) в Математическом институте им. В. А. Стеклова Российской академии наук. Параграфы 1–5 выполнены Л. Д. Беклемишевым, а § 6 – совместно Л. Д. Беклемишевым и А. А. Оноприенко.


DOI: https://doi.org/10.4213/sm8519

Полный текст: PDF файл (524 kB)
Первая страница: PDF файл
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Sbornik: Mathematics, 2015, 206:9, 1173–1190

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

Тип публикации: Статья
УДК: 510.23+510.58
MSC: 68Q42, 03D03, 03F45, 03F30
Поступила в редакцию: 25.03.2015 и 21.06.2015

Образец цитирования: Л. Д. Беклемишев, А. А. Оноприенко, “О некоторых медленно сходящихся системах преобразований термов”, Матем. сб., 206:9 (2015), 3–20; L. D. Beklemishev, A. A. Onoprienko, “On some slowly terminating term rewriting systems”, Sb. Math., 206:9 (2015), 1173–1190

Цитирование в формате AMSBIB
\RBibitem{BekOno15}
\by Л.~Д.~Беклемишев, А.~А.~Оноприенко
\paper О некоторых медленно сходящихся~системах преобразований термов
\jour Матем. сб.
\yr 2015
\vol 206
\issue 9
\pages 3--20
\mathnet{http://mi.mathnet.ru/msb8519}
\crossref{https://doi.org/10.4213/sm8519}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3438593}
\zmath{https://zbmath.org/?q=an:06537974}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2015SbMat.206.1173B}
\elib{http://elibrary.ru/item.asp?id=24073839}
\transl
\by L.~D.~Beklemishev, A.~A.~Onoprienko
\paper On some slowly terminating term rewriting systems
\jour Sb. Math.
\yr 2015
\vol 206
\issue 9
\pages 1173--1190
\crossref{https://doi.org/10.1070/SM2015v206n09ABEH004493}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000366131200001}
\elib{http://elibrary.ru/item.asp?id=24973592}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84947776409}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/msb8519
  • https://doi.org/10.4213/sm8519
  • http://mi.mathnet.ru/rus/msb/v206/i9/p3

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. A. Cordón-Franco, D. Fernández-Duque, J. J. Joosten, F. F. Lara-Martín, “Predicativity through transfinite reflection”, J. Symb. Log., 82:3 (2017), 787–808  crossref  mathscinet  zmath  isi  scopus
    2. L. D. Beklemishev, “On the reflection calculus with partial conservativity operators”, Logic, language, information, and computation, Lecture Notes in Comput. Sci., 10388, Springer, Berlin, 2017, 48–67  mathnet  crossref  mathscinet  zmath  isi  scopus
  • Математический сборник Sbornik: Mathematics (from 1967)
    Просмотров:
    Эта страница:337
    Литература:41
    Первая стр.:42

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018