PR - это класс сложности всех примитивных рекурсивных функций или, что то же самое, набор всех формальных языков, которые могут быть определены с помощью такой функции. Это включает в себя сложение, умножение, возведение в степень, тетрацию и т. Д.
Функция Аккермана является примером функции, которая не является примитивно рекурсивной, показывая, что PR строго содержится в R (Cooper 2004: 88).
С другой стороны, мы можем «пронумеровать» любое рекурсивно перечислимое множество (см. Также его класс сложности RE ) примитивно-рекурсивной функцией в следующем смысле: дан вход ( M , k ), где M - машина Тьюринга и k - целое число, если M останавливается в течение k шагов, выведите M ; в противном случае ничего не выводить. Тогда объединение выходов по всем возможным входам ( M , k ) - это в точности набор M, которые останавливаются.
PR строго содержит НАЧАЛЬНОЕ .
PR не содержит "PR-полных" проблем (предполагая, например, сокращения, которые принадлежат ELEMENTARY). На практике многие проблемы, которые не связаны с пиаром, а выходят за его рамки, являются завершенными (Schmitz, 2016).
Ссылки [ править ]
- С. Барри Купер (2004), Теория вычислимости , Chapman & Hall. ISBN 1-58488-237-9
- Герберт Эндертон (2011), Теория вычислимости , Academic Press. ISBN 978-0-12-384-958-8
- Сильвен Шмитц (2016), « Иерархии сложности за пределами элементарных », ACM-транзакции по теории вычислений 8. doi : 10.1145 / 2858784
Внешние ссылки [ править ]
- Зоопарк сложности : PR .
