|
Дана примитивно рекурсивная функция $%g(x)$%. Докажите, что следующая функция является примитивно рекурсивной: $%nt(x, y) =$% количество натуральных чисел $%i$% из отрезка $%[0, y]$%, для которых $%g(i) = x$% задан 15 Мар '19 16:43 
Orange |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
15 Мар '19 16:43
показан
707 раз
обновлен
15 Мар '19 17:44
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Условие 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|).