Примитивно рекурсивные функции. ПРФ.

Здравствуйте. Решаю задачу такого типа: U(x)=[x^(1/2)] — целая часть корня из X.
Вот мои решения, но я не уверен, что я делаю так, могли бы Вы подсказать?
https://pp.userapi.com/c852128/v852128164/6f200/u6lUBlUTR7Y.jpg

Здравствуйте, Алексей! Сформулируйте, пожалуйста, задачу.

Задачу я понял так: нужно доказать, что целая часть корня — это
примитивно рекурсивная функция.
А ещё лучше в явном виде предъявить схему примитивной рекурсии.
То есть, предъявить последовательность функций, в которой каждая функция
либо является простейшей примитивно рекурсивной функцией, либо получается
из каких-нибудь предыдущих функций этой последовательности с помощью
оператора суперпозиции или оператора примитивной рекурсии.
Последней функцией в этой последовательности должна быть целая часть корня.
На рисунке Алексея я такой последовательности функций не разглядел.

Так как для функции U (целая часть квадратного корня) требуется дать
рекурсивное определение, нужно подумать, как связаны между собой
значения U(x+1) и U(x).
Чаще всего, U(x+1) = U(x),
но иногда происходит скачок на единичку: U(x+1) = U(x)+1.
При каком условии происходит скачок? Скачок происходит, если (x+1) — квадрат.
А более точно, если x+1 = (U(x)+1)^2. А нет скачка, если x+1 < (U(x)+1)^2.
Получаем рекурсивное определение функции U:

(1) [m]\left\{\begin{array}{l}U(0)=0,\\U(x+1)=\left\{\begin{array}{l}U(x),\quad \quad \quad (x+1) < (U(x)+1)^2,\\U(x)+1,\quad(x+1)=(U(x)+1)^2.\\ \end{array}\right.\\ \end{array}\right.[/m]

Но задача ещё не решена до конца, так как нужно всё свести к простейшим
рекурсивным функциям.
Введём вспомогательную функцию [m]\delta[/m] двух аргументов:

(2) [m]\delta(y,z)=\left\{\begin{array}{l}0,\quad\quad y<z,\\1,\quad\quad y=z,\\...\quad\quad y>z.\\ \end{array}\right.[/m]

(Нам не важно, какие значения будет иметь функция [m]\delta[/m] при y>z.)
Тогда рекурсивное определение (1) функции U перепишется так:

(3) [m]\left\{\begin{array}{l}U(0)=0,\\U(x+1)=U(x)+\delta\Bigl(x+1,\bigl(U(x)+1\bigr)^2\Bigr).\end{array}\right.[/m]

Введём вспомогательную функцию [m]\Delta[/m] двух аргументов:

(4) [m]\Delta(t,w) = w+\delta \bigl( t+1,(w+1)^2 \bigr).[/m]

Тогда рекурсивное определение (3) функции U перепишется так:

(5) [m]\left\{\begin{array}{l}U(0)=0,\\U(x+1)=\Delta(x,U(x)).\end{array}\right.[/m]

Компактно это принято записывать так:
(6) [m]U=R(0,\Delta)[/m], где R — так называемый оператор примитивной рекурсии.
А вообще, запись h=R(c,g), где c — константа, а g — функция двух аргументов,
означает, что h — функция с одним аргументом, причём

(7) [m]\left\{\begin{array}{l}h(0)=c,\\h(x+1)=g(x,h(x)).\end{array}\right.[/m]

Займёмся теперь рекурсивным определением функции [m]\Delta[/m].
Будем использовать стандартные обозначения [m]I^2_1[/m] и [m]I^2_2[/m]
для простейших рекурсивных функций двух аргументов, возвращающих
соответственно значения первого и второго аргументов (функции-проекции):
[m]I^2_1(x,y)=x, \quad I^2_2(x,y)=y.[/m]
Простейшую рекурсивную функцию прибавления единицы будем обозначать s: s(x)=x+1.
Функцию суммы двух аргументов будем обозначать add: add(x,y)=x+y.
Функцию возведения в квадрат будем обозначать sqr: [m]sqr(x)=x^2[/m].

Через S будем обозначать оператор суперпозиции (подстановки).
Тогда определение функции [m]\Delta[/m] перепишется так:

(8) [m]\Delta=S\biggl(add,\;I^2_2,\;S\Bigl(\delta,\,S(s,I^2_1),\,S\bigl(sqr,S(s,I^2_2)\bigr)\Bigr)\biggr).[/m]

Слегка прокомментируем эту не вполне привычную запись.
Например, фрагмент S(s,I^2_2) в этой формуле означает суперпозицию двух
функций: I^2_2 и s.
К паре аргументов применяется сначала функция [m]I^2_2[/m], а потом функция s.
Если пара аргументов — это (t,w), то первая фукция возвращает w, а вторая w+1.
Фрагмент [m]S\bigl(sqr,S(s,I^2_2)\bigr)[/m]
тоже означает суперпозицию двух функций:
к паре аргументов сначала применяется функция
[m]S(s,I^2_2)[/m], а потом функция sqr.
Если пара аргументов — это (t,w), то первая фукция возвращает w+1
(как мы уже знаем), а вторая $(w+1)^2$. Ну, и так далее.

Обозначим через d функцию, вычитающую единицу из положительного числа
и оставляющую 0 на месте:

(9) [m]\left\{\begin{array}{l}d(0)=0,\\d(x+1)=x.\end{array}\right.[/m]

Используя оператор R примитивной рекурсии, формулы (9) можно переписать так:
(10) [m]d=R(0,I^2_1)[/m].

Обозначим через minus функцию "усечённой разности".
Она равна обычной разности двух своих аргументов, если эта разность
неотрицательна, и равна 0 в противном случае:

(11) [m]\left\{\begin{array}{l}minus(x,0)=x,\\minus(x,y+1)=d(minus(x,y)).\end{array}\right.[/m]

Формулы (11) можно переписать так:

(12) [m]minus=R(I^1_1, S(d, I^3_3))[/m].

В данном случае оператор примитивной рекурсии R применяется к двум функциям,
первая из которых — функция одного аргумента, вторая — функция трёх аргументов.
Первая функция [m]I^1_1[/m] — тождественная: [m]I^1_1(x)=x[/m].
Вторая функция — это композиция функции [m]I^3_3[/m], возвращающей третий
аргумент и функции [m]d[/m] "усечённого вычитания единицы".
Результат оператора [m]R[/m] — функция minus двух аргументов.

А вообще, запись h=R(f,g), где f — функция одного аргумента, а g — функция
трёх аргументов, означает, что функция h имеет два аргумента, причём

(13) [m]\left\{\begin{array}{l}h(x,0)=f(x),\\h(x,y+1)= g(x,y,h(x)).\end{array}\right.[/m]

Подставляя в (12) выражение (10) для функции d, получаем формулу, которая
выражает функцию minus только через простейшие примитивно рекурсивные
функции:

(14) [m]minus=R\Bigl(I^1_1,S\bigl(R(0,I^2_1),I^3_3\bigr)\Bigr)[/m].

Через функцию minus выражается функция [m]\delta[/m]:
(15) [m]\delta(y,z) = minus(y+1,z)[/m].
Или:
(16) [m]\delta=S\Bigl(minus,\;S(s,I^2_1),\;I^2_2 \Bigr)[/m].

Подставляя в (16) выражение (14) для функции minus, получаем формулу, которая
выражает функцию [m]\delta[/m] только через простейшие примитивно рекурсивные
функции:

(17) [m]\delta=S\Bigl(R\Bigl(I^1_1,S\bigl(R(0,I^2_1),I^3_3\bigr)\Bigr),\;S(s,I^2_1), \; I^2_2 \Bigr)[/m].

Для функции add имеем:

(18) [m]\left\{\begin{array}{l}add(x,0)=x,\\ add(x,y+1)=add(x,y)+1.\end{array}\right.[/m]

Или:
(19) [m]add=R \bigl( I^1_1, S(s, I^3_3) \bigr)[/m].

Для функции возведения в квадрат sqr имеем:
(20) [m]\left\{\begin{array}{l}sqr(0)=0,\\sqr(x+1)= sqr(x)+x+x+1.\end{array}\right.[/m]

Или:
(21) [m]sqr=R \Bigl( 0, S \bigl(s, S(add, I^2_1, add) \bigr) \Bigr) [/m].

Подставляя в (21) выражение (19) для функции add, получаем формулу, которая
выражает функцию sqr только через простейшие примитивно рекурсивные функции:

(22) [m]sqr=R \Bigl( 0, S \Bigl( s, S \Bigl( R \bigl( I^1_1, S(s, I^3_3) \bigr), I^2_1, R \bigl( I^1_1, S(s, I^3_3) \bigr) \Bigr) \Bigr) \Bigr) [/m].

Теперь надо бы в формулу (8) для [m]\Delta[/m]
подставить выражение (19) для add, выражение (17) для [m]\delta[/m]
и выражение (22) для sqr.
Выражение, которое получится для [m]\Delta[/m], останется подставить в (6),
и мы получим выражение для искомой функции U через простейшие примитивно
рекурсивные функции.
Но для этого у меня уже нет сил.
Лучше я попробую выписать последовательность примитивно рекурсивных
функций, о которой я писал в #3.
Члены этой последовательности я буду нумеровать, используя несколько
иной стиль, чем использовал до этого для нумерации формул.

(-1-) Константа 0 — нульместная простейшая примитивно рекурсивная функция,

(-2-) s — одноместная простейшая примитивно рекурсивная функция,
прибавляющая к аргументу единицу,

(-3-) [m]I^1_1[/m] — одноместная простейшая примитивно рекурсивная функция,
тождественная,

(-4-) [m]I^2_1[/m] — двуместная простейшая примитивно рекурсивная функция,
возвращающая первый аргумент,

(-5-) [m]I^2_2[/m] — двуместная простейшая примитивно рекурсивная функция,
возвращающая второй аргумент,

(-5-) [m]I^3_3[/m] — трёхместная простейшая примитивно рекурсивная функция,
возвращающая третий аргумент,

(-6-) [m]S(s, I^3_3)[/m] — трёхместная функция, прибавляющая единицу
к третьему аргументу, суперпозиция функций (-2-) и (-5-),

(-7-) [m]add=R \bigl( I^1_1, S(s, I^3_3) \bigr)[/m] — двуместная функция,
возвращающая сумму аргументов, получается применением оператора
примитивной рекурсии к функциям (-3-) и (-6-),

(-8-) [m]S(add, I^2_1, add)[/m] — двуместная функция,
возвращающая сумму удвоенного первого аргумента и второго аргумента;
получается подстановкой в add на место одного из аргументов самой add,
на место другого аргумента — первой проекции; то есть, суперпозиция
функций (-4-) и (-7-),

(-9-) [m]S \bigl(s, S(add, I^2_1, add) \bigr)[/m] — двуместная функция,
возвращающая на 1 большее значение, чем предыдущая функция;
суперпозиция функций (-2-) и (-8-),

(-10-) [m]sqr=R\Bigl(0,S\bigl(s,S(add,I^2_1,add)\bigr)\Bigr)[/m]
- одноместная функция возведения в квадрат; получается применением оператора
примитивной рекурсии к функциям (-1-) и (-9-),

(-11-) [m]d=R(0,I^2_1)[/m] — одноместная функция усечённого вычитания единицы;
получается применением оператора примитивной рекурсии к функциям (-1-) и (-4-),

(-12-) [m]S(d, I^3_3)[/m] — трёхместная функция, вычитающая единицу (усечённо)
из своего третьего аргумента; суперпозиция функций (-5-) и (-11-),

(-13-) [m]minus=R(I^1_1, S(d, I^3_3))[/m] — двуместная функция усечённой
разности; получается применением оператора примитивной рекурсии
к функциям (-3-) и (-12-),

(-14-) [m]S(s,I^2_1)[/m] — двуместная функция, прибавляющая единицу
к своему первому аргументу; суперпозиция функций (-2-) и (-4-),

(-15-) [m]\delta = S \Bigl(minus, \; S(s,I^2_1), \; I^2_2 \Bigr)[/m] — двуместная
функция, получающаяся подстановкой в функцию (-13-) функций (-14-) и (-5-),

(-16-) [m]S(s,I^2_2)[/m] — двуместная функция, прибавляющая единицу к своему
второму аргументу; суперпозиция функций (-2-) и (-5-),

(-17-) [m]S \bigl( sqr, S(s,I^2_2) \bigr)[/m] — двуместная функция, прибавляющая
единицу к своему второму аргументу и результат возводящая в квадрат;
суперпозиция функций (-10-) и (-16-),

(-18-) [m]S \Bigl( \delta, \, S(s,I^2_1), \, S \bigl( sqr, S(s,I^2_2) \bigr) \Bigr)[/m] —
двуместная функция; результат подстановки в функцию (-15-) функций (-14-) и (-17-),

(-19-) [m]\Delta = S \biggl( add, \; I^2_2, \; S \Bigl( \delta, \, S(s,I^2_1), \, S \bigl( sqr, S(s,I^2_2) \bigr) \Bigr) \biggr) [/m]
- двуместная функция; результат подстановки в функцию (-7-)
функций (-5-) и (-18-),

(-20-) [m]U = R(0, \Delta)[/m] — искомая одноместная функция, целая часть
квадратного корня; получается применением оператора примитивной рекурсии
к функциям (-1-) и (-19-).

У меня получилась цепочка из 20 примитивно рекурсивных функций.
Предлагаю участникам форума задачу: либо придумать более короткую цепочку,
либо доказать, что более короткой цепочки не существует.

Юрий Анатольевич,
почтение за верстку в ответах!

Не могу решить задачу по геометрии, не понимаю что к чему.
Задача:Площадь прямоугольного треугольника равна 32√3/3 один из острых углов рвыен 60° найдите длину катета, лежавшего напротив этого угла.
Что значит делаю я:
Угол С=60° потом 32 заганаю под корень к трем, получаем √32*3 :3 =32.
Вроде понимаю, что нужно по т. Пефагора. Но не понимаю как:(

Под каким углом пересекает ось ОХ график функции y=x^2+x-2.
У меня не сходится с ответом. Делаю, как указано. Строю касательные, нахожу углы пересечения касательной с осью, с ответом не сходится.

Сыну в школе дали уравнение [x]^2+10x+16. [ ]-целая часть числа. Вопрос: сколько решений у этого уравнения. Я никогда не сталкивался с такими уравнениями.

Ну и от меня разминка на утро.
1) [x]*{x}<x-1, где [x]-целая часть, {x} — дробная часть.
2) Найти максимальное значение выражения x^2*y-y^2*x, где 0<=х<=1, 0<=y<=1.
3) В треугольнике АВС длины всех сторон целые числа,причем длины АВ и ВС простые, величина угла В — 120 градусов.Найти АС.

При каких действительных р уравнение имеет решение
4^x+2^(x+2)+7=p-4^(-x)-2*2^(1-x)
Делаю замену 2^x+2^(-x)=t
t^2+4t+5-p=0
Преобразовываю, нахожу р>5, а в ответе р>13
Где ошибка?