• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Математический сборник. 2015. Т. 206. № 9. С. 3-20.
Беклемишев Л. Д., Оноприенко А. А.

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

Библиография: 16 названий.