Как доказать, что функция, сопоставляющая числу n n-е число Фибоначчи, примитивно рекурсивна? В указаниях - воспользоваться функцией спаривания Кантора.

задан 23 Окт '19 18:26

Идея в том, что мы следим за парами при помощи их номеров. От пары (a,b) мы переходим к следующей паре в ряду Фибоначчи -- это (b,a+b). По рекурсии задаётся множество номеров пар. Начальная пара задана (скажем, (1,1)), а номер (n+1)-й пары выражается через номер n-й. Это легко делается при помощи формулы для п и формул для проекций на компоненты -- там всё примитивно-рекурсивно.

(23 Окт '19 20:07) falcao

На интуитивном уровне понятно, но понятно не настолько, чтобы можно было это реализовать. То есть не понятно например, что на формальном уровне значит "переходим к следующей паре". Сначала как-то строится функция NxN -> NxN а потом применяется функция Кантора? Как всё это записать в терминах функции Кантора?

(24 Окт '19 5:51) logic

@logic: пусть в начале была последовательность Фибоначчи 1, 1, 2, 3, 5, ... . Ставим ей в соответствие последовательность пар (1,1), (1,2), (2,3), (3,5), ... . У каждой пары (x,y) есть номер п(x,y), где п -- спаривание. Получается последовательность номеров, то есть функция f одного аргумента. Её и строим. Сначала задаём f(1)=п(1,1). Теперь f(n+1) выражаем через f(n) по рекурсии. Пусть g, h -- проекции на компоненты. Берём a=g(f(n)), b=h(f(n)). Это значит, что f(n) -- номер пары (a,b). За ней в списке идёт пара (b,a+b). Её номер f(n+1)=п(h(f(n),g(f(n))+h(f(n))). Это рекурсия.

(24 Окт '19 13:05) falcao

Но эта функция f сама не является функцией, сопоставляющей числу n n-е число Фибоначчи, верно? Она сопоставляет числу n код n-го числа Фибоначчи (код 1 - это п(1,1); код 2 - это пи(1,2) и т.д.). Чтобы получить функцию, сопоставляющую n n-е число Фибоначчи, наверное, надо f скомпозировать с функцией, которая сопоставляет коду n-го числа Фибоначчи само число. Почему такая функция примитивно рекурсивна?

(25 Окт '19 18:30) logic

@logic: я при объяснениях стараюсь опускать вещи, которые сами собой разумеются (хотя бы по причине ограничений на длину комментария).

Функция f примитивно рекурсивна по построению. Она даёт номер пары, в которой первое число есть n-е число Фибоначчи. Чтобы получить последнее, нужно применить оператор подстановки, то есть f(n) подставить в функцию g проекции на первую компоненту. То есть a=g(f(n)) уже звучало в промежуточной конструкции. То, что g и h примитивно рекурсивны, входит в "комплект" знаний о спаривании.

(25 Окт '19 18:54) falcao

(Комментарий, не связанный с самым последним комментарием) Я верю, что формула f(n+1)=п(h(f(n),g(f(n))+h(f(n))) задает примитивно рекурсивную функцию, но "вся" функция f определена "кусочно" - f(1)=п(1,1) и f(n+1)=п(h(f(n),g(f(n))+h(f(n))). Почему эта кусочная функция примитивно рекурсивна? Применить последний "синий треугольник" из определения https://i.stack.imgur.com/wC8Iq.png не получается, т.к. у нашей функции f всего один аргумент.

(27 Окт '19 5:39) logic

@logic: не понимаю, что Вы имеете в виду под "кусочностью". Рекурсия означает, что мы задаём начальное значение функции, и формулу, которая следующее значение выражает через предыдущее. Случай, когда у функции f ровно один аргумент, соответствует случаю, когда вектор bar{x} из определения -- пустой, то есть k=0. При этом f(0)=const, f(y+1) есть функция (ранее построенная) от y, f(y). В комментарии роль "игрека" (переменной, по которой идёт индукция-рекурсия) играет n.

Очень многие функции одной переменной именно так и строятся. Например, декремент: d(x)=0 при x=0, d(x)=x-1 при x>=1.

(27 Окт '19 5:56) falcao

Тогда надо определить f(0)=п(1,1), а не f(1)=п(1,1)? То есть f(0)=п(1,1), f(n+1)=п(h(f(n),g(f(n))+h(f(n))). Тогда вроде определение будет соблюдаться.

(27 Окт '19 6:04) logic

@logic: есть равноценные версии -- когда натуральные числа берутся с нулём (я больше люблю этот вариант), и когда без нуля. Ряд Фибоначчи тоже можно начинать с 0, 1, а можно с 1, 1. Одно в другое легко "конвертируется". Здесь, поскольку ряд "классический", я взял за основу вариант с N={1,2,3,..} и нумерацию пар брал для этого случая. Но это сущие мелочи.

(27 Окт '19 6:18) falcao
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×49

задан
23 Окт '19 18:26

показан
376 раз

обновлен
27 Окт '19 6:18

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

по почте:

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

по RSS:

Ответы

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

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