Рассмотрим функцию $%c(n)$%

$%c(0)=1,c(n+1)=\sum_{k=0}^nc_kc_{n-k}$%

Докажите, что $%c$% примитивно рекурсивна

задан 30 Ноя 6:33

изменен 30 Ноя 6:33

Для чисел Каталана есть формула c(n)=(2n)!/(n!(n+1)!). Факториал примитивно рекурсивен; деление реализуем через целочисленное частное quo, которое легко выражается по рекурсии. Ещё можно использовать то, что отношение c(n+1)/c(n) равно (4n+2)/(n+2) с той же идеей.

(30 Ноя 10:06) falcao

Вообще это упражнение на рекурсию курсом значений (course-of-values recursion). Как бы с его помощью доказать оригинальное утверждение?

(30 Ноя 22:49) logic

@logic: какие конкретно средства разрешено использовать?

(30 Ноя 23:23) falcao

предлагается использовать результат math.hashcode.ru/questions/188644/ и вроде бы предлагается доказывать, что функция из условия может быть определена курсом значений (https://en.wikipedia.org/wiki/Course-of-values_recursion ), и использовать, что это эквивалентно примитивной рекурсивности.

(30 Ноя 23:45) logic

@logic: такой подход в принципе имеет смысл, так как вместо чисел Каталана, для которых есть "обходной" путь, утверждение верно для любых других последовательностей, где (n+1)-й член явно выражен через предыдущие. В принципе, это чисто техническая вещь, и она может быть осуществлена или через гёделеву нумерацию (подробности см. в Мендельсоне), или через однозначную нумерацию числовых последовательностей. Если брать всё в целом, то это довольно длинно, хотя сам способ не представляется трудным в плане общей идеи.

(30 Ноя 23:50) falcao

Если способ нетрудный, то хотелось бы хотя бы увидеть "плановое доказательство" через однозначную нумерацию последовательностей (это, я так понимаю, связано с утверждением из вопроса по ссылке) с опусканием доказательств технических деталей. На Мендельсона я посмотрел, но главы про теорию вычислимости там в достаточно незнакомой терминологии изложены, а изучение нумерации Геделя при наличии некоторого знакомства с нумерацией последовательностей представляется неоправданным.

(1 Дек 6:14) logic

@logic: здесь сама идея очень простая: вместо работы с отдельными f(n) брать номера последовательностей <f(0),...,f(n)>, и по рекурсии от номера переходить к следующему, то есть к номеру <f(0),...,f(n),f(n+1)>. Зная номер, мы умеем переходить к компонентам по явным формулам (они уже как-то обсуждались), а через компоненты явно выражается f(n+1), который далее подставляем в формулу для вычисления номера новой последовательности.

(1 Дек 12:24) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,190
×812

задан
30 Ноя 6:33

показан
49 раз

обновлен
1 Дек 12:24

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

по почте:

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

по RSS:

Ответы

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

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