|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
О некоторых медленно сходящихся системах преобразований термов
Л. Д. Беклемишевa, А. А. Оноприенкоb a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва
b Механико-математический факультет,
Московский государственный университет имени М. В. Ломоносова
Аннотация:
Формулируются системы преобразований термов, число шагов работы которых на произвольном входе конечно, но не ограничивается никакой вычислимой функцией, доказуемо тотальной в арифметике Пеано $\mathsf{PA}$. Тем самым, утверждение о сходимости таких систем не доказуемо в $\mathsf{PA}$. Эти системы получаются из независимого комбинаторного утверждения, известного как принцип червя; их также можно рассматривать как вариант хорошо известной игры Геракла и гидры, введенной Дж. Парисом и Л. Кирби.
Библиография: 16 названий.
Ключевые слова:
системы преобразований термов, арифметика Пеано, принцип червя.
Поступила в редакцию: 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
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm8519https://doi.org/10.4213/sm8519 https://www.mathnet.ru/rus/sm/v206/i9/p3
|
Статистика просмотров: |
Страница аннотации: | 734 | PDF русской версии: | 205 | PDF английской версии: | 9 | Список литературы: | 69 | Первая страница: | 42 |
|