Пусть $%p_i$% - функции из предыдущего вопроса. Пусть S - множество конечных последовательностей натуральных чисел. Определим $$f:S\to N$$ $$\epsilon\mapsto p_2(0,0)\\n\mapsto p_2(0,n+1)\\ (n_1,\dots, n_k)\mapsto p_2(k-1,p_k(n_1,\dots,n_k))$$

  • Докажите, что $%f$% биективна
  • Пусть $%l:N\to N$% - функция, сопоставляющая числу $%n$% длину последовательности $%f^{-1}(n)$%. Докажите, что $%l$% примитивно рекурсивна.

задан 31 Окт '19 2:42

Здесь рассматривается единая нумерация для всех конечных последовательностей. Зная номер последовательности, применяем к нему функцию a, находя первую компоненту пары с номером n. Это почти всегда k-1, то есть длина последовательности f^{-1}(n) равна a(n)+1. Исключение составляет случай n=0, когда длина равна нулю.

Биективность очевидна ввиду наличия обратной операции. Чтобы восстановить непустую последовательность по её номеру, находим k=a(n)+1, а потом к b(n) применяем функции f с индексами из "параллельного" вопроса.

(31 Окт '19 3:27) falcao

Это почти всегда k-1... Исключение составляет случай n=0 Почему "почти"? Если n=0, то a(n)=0=k-1 для k=1.

когда длина равна нулю. Почему только нулю? Длина может быть равна и единице же?

И как всё это доказывает примитивную рекурсивность?

(31 Окт '19 3:41) logic

@logic: длина пустой последовательности равна нулю. То есть этот случай являет собой исключение.

Про функцию a(n)+1 мы знаем, что она примитивно-рекурсивна, а если изменить значение в одной точке, то очевидно, что это никак не влияет на свойство.

(31 Окт '19 11:08) falcao

А как именно невлияние изменения значения в одной точке на примитивную рекурсивность следует из определения примитивно рекурсивной функции?

(1 Ноя '19 23:20) logic

@logic: это простое техническое упражнение из начальной части изложения. Есть конструкция "разветвления", которая Вам известна. Напомню, что там есть две примитивно-рекурсивные функции, и значение f равно той или другой на двух разных множествах, у которых индикаторы примитивно-рекурсивны. Тогда f равно f1 умножить на индикатор A плюс f2 умножить на индикатор дополнения.

Здесь достаточно показать, что смена значения в одной точке не влияет на свойство примитивной рекурсивности, что очевидно, так как предикат x=a примитивно рекурсивен для любой константы a.

(2 Ноя '19 5:22) falcao

Насчет конструкции восстановления непустой последовательности по ее номеру: она ведь доказывает только сюръективность? А инъективность наверное просто следует из инъективности p_2.

(3 Ноя '19 0:02) logic

А вместо предиката x=a можно же использовать $%\{k\in N: k>0\}$%?

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

Ваш ответ

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

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

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

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

отмечен:

×49

задан
31 Окт '19 2:42

показан
259 раз

обновлен
3 Ноя '19 1:12

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

по почте:

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

по RSS:

Ответы

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

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