Примитивно-рекурсивная функция

[arhimedius]

Ребята, недавно наткнулся на такую задачу:

Цитата:

Докажите примитивно-рекурсивность следующей функции:
$I_{3}^4(z_{1},z_{2},z_{3},z_{4})=z_{3}$

Но, как мне известно, функция выбора и так является примитивно-рекурсивной функцией!?
Тогда, собственно, в чем вопрос?

P.S. Не нашел кнопку "Создать новую тему". В интернете не нашел ответа на свой вопрос.

[arseniiv]

arhimedius в сообщении #949585 писал(а):

Но, как мне известно, функция выбора I(x1,..,xn) и так является примитивно-рекурсивной функцией!?
Тогда, собственно, в чем вопрос?

В контексте. Видимо, у вас он какой-то не совсем обычный — что там написано в определениях?

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[arhimedius]

arseniiv в сообщении #949590 писал(а):

arhimedius в сообщении #949585 писал(а):

Но, как мне известно, функция выбора I(x1,..,xn) и так является примитивно-рекурсивной функцией!?
Тогда, собственно, в чем вопрос?

В контексте. Видимо, у вас он какой-то не совсем обычный — что там написано в определениях?

Здравствуйте!
Видимо переборщил насчет примтивно-рекурсивности функции выбора.
По определениям:

Функция называется простейшей, если она является одной из следующих функций:
$O(x)=0$ - тождественный нуль;
$S(x)= x+1$ - следующее число (плюс один);
функции выбора аргумента $I_{m}^n (x_{1}, ... ,x_{n})=x_{m} (1 \leqslant m \leqslant n)$

Функция f называется частично рекурсивной функцией (ч.р.ф.), если она является одной из простейших функций или может получиться из них с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации, т.е. существует последовательность функций $f_{1},f_{2},..., f_{n}=f$, каждая из которых является либо простейшей, либо получена из предыдуших с помощью одного из указанных операторов. Указанная последовательность функций называется частично рекурсивным описанием функции f.

Функция f называется примитивно рекурсивной функцией (п.р.ф.), если она частично рекурсивна и для нее существует частично рекурсивное описание, использующее лишь операторы суперпозиции и примитивной рекурсии.

Т.е. мне нужно найти последовательность функции $f_{1},...,f_{n}$? Ничего не приходить на ум, кроме такого бреда:
$I_{3}^4(z_{1}, z_{2},z_{3},z_{4})=I_{1}^1(z_{3}) $

[arseniiv]

Да не, последнее действительно писать не нужно.

Получается, у вас просто $n = 1, f_1 = I_3^4$ — и ничего лишнего. И такие задания бывают.

[arhimedius]

Спасибо!)