Дана примитивно рекурсивная функция $%g(x)$%. Докажите, что следующая функция является примитивно рекурсивной: $%nt(x, y) =$% количество натуральных чисел $%i$% из отрезка $%[0, y]$%, для которых $%g(i) = x$%

задан 15 Мар '19 16:43

1

Условие g(i)=x равносильно |g(i)-x|=0, и равносильно ss(|g(i)-x|)=1, где ss обозначает сигнум с чертой. Это примитивно-рекурсивная функция от i,x. Суммирование по i от 0 до y даёт nt(x,y). То, что суммировать можно, объяснено в учебнике Мендельсона.

Можно напрямую задать nt по схеме рекурсии: nt(x,0)=ss(|g(0)-x|); nt(x,y+1)=nt(x,y)+ss(|g(y+1)-x|).

(15 Мар '19 17:44) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,126
×710
×281
×197

задан
15 Мар '19 16:43

показан
514 раз

обновлен
15 Мар '19 17:44

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru