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