![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Операции суперпозиции и примитивной рекурсии сохраняют:
1. всюду определённость функций;
2. интуитивную вычислимость функций.
Доказательство проведем для операции суперпозиции. Пусть m -арная функция получена в результате операции суперпозиции из функций
и
.
1. Если все функции и
– всюду определённые, то функция
всюду определена. Функция
будет не всюду определённой, если одна из функций
не всюду определена или если можно найти такие
, что
,
,
, но значение
неопределено.
2. Если каким-либо образом можно вычислять значения функций и
, то ясно, как можно вычислить значение функции
. Придадим переменным
некоторые значения
. Вычислим все
,
. Получим значения
,
,
. Вычисляя теперь
, получим, что
. Таким образом, если функции
и
интуитивно вычислимы, то и функция
интуитивно вычислима.
Предложение доказано.
Функция f называется примитивно рекурсивной (п.р.ф.), если ее можно получить из простейших функций с помощью конечного числа операций суперпозиции и примитивной рекурсии.
Свойства примитивно рекурсивных функций характеризует следующее
Дата публикования: 2015-03-26; Прочитано: 276 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!