Помогите доказать, что функция примитивно рекурсивная

[Artur5463]

Помогите, пожалуйста, доказать, что заданная функция - примитивно рекурсивная функция.

$$f(x)=2x-3=\begin{cases} 2x-3,&\text{если $2x>3$;}\\ 0,&\text{если $2x<3$;}\\ \end{cases}$$

Попытки решения:
Имеется случай $n=0$, то есть
$f(0)=g(x)$
$f(x+1)=h(x,f(x))$
Составим схему примитивной рекурсии.
$f(0)=2\cdot0\dot{-}3=0$
$f(1)=2\cdot1\dot{-}3=0$
$f(2)=2\cdot2\dot{-}3=1$
$f(3)=2\cdot3\dot{-}3=3$
$f(4)=2\cdot4\dot{-}3=5$
$f(5)=2\cdot5\dot{-}3=7$
$f(6)=2\cdot6\dot{-}3=9$
Отсюда делаем вывод, что
$f(x+1)=(f(x)+1+1)\dot{-}(2\dot{-}x)$
Тогда
$h(x+1,y)=(y+1+1)\dot{-}(2\dot{-}x)$
Верно ли я нашел $h(x,y)$ ?
И как можно иначе найти $f(x+1)$ ?

[Pphantom]

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

- не набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- не уверен, что это проблема (возможно, просто я не в курсе), но лично мне сокращение ПРФ ни о чем не говорит.

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

[Pphantom]

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

[mihaild]

Artur5463 в сообщении #1458829 писал(а):

$h(x+1,y)=(y+1+1)\dot{-}(2\dot{-}x)$
Верно ли я нашел $h(x,y)$ ?

В принципе правильно, но в этой части ИМХО лучше максимально следить за строгостью, а формально вы не выразили $h(x, y)$ - в левой части у вас $h(x + 1, y)$.

Artur5463 в сообщении #1458829 писал(а):

И как можно иначе найти $f(x+1)$ ?

Найти - по формуле Доказать примитивную рекурсивность - наверное проще было бы доказать отдельно примитивную рекурсивность $u(x) = 2x$ и $v(x) = 3$, и дальше воспользоваться подстановкой $f(x) = \cdot(3x, 3)$ (предполагая, что примитивная рекурсивность усеченной разности уже известна, иначе её тоже надо выразить).

[Artur5463]

mihaild в сообщении #1458881 писал(а):

Artur5463 в сообщении #1458829 писал(а):

$h(x+1,y)=(y+1+1)\dot{-}(2\dot{-}x)$
Верно ли я нашел $h(x,y)$ ?

В принципе правильно, но в этой части ИМХО лучше максимально следить за строгостью, а формально вы не выразили $h(x, y)$ - в левой части у вас $h(x + 1, y)$.

Artur5463 в сообщении #1458829 писал(а):

И как можно иначе найти $f(x+1)$ ?

Найти - по формуле Доказать примитивную рекурсивность - наверное проще было бы доказать отдельно примитивную рекурсивность $u(x) = 2x$ и $v(x) = 3$, и дальше воспользоваться подстановкой $f(x) = \cdot(3x, 3)$ (предполагая, что примитивная рекурсивность усеченной разности уже известна, иначе её тоже надо выразить).

Спасибо. А как можно найти сразу $f(x+1)$ без нахождения $f(0)...; f(1)...$, пытаясь выразить старую первоначальную функцию?

[mihaild]

Artur5463 в сообщении #1458884 писал(а):

А как можно найти сразу $f(x+1)$, пытаясь выразить старую первоначальную функцию?

Не очень понял вопрос. Есть базовые функции, и есть два способа получения из имеющихся функций новые. Что значит "найти $f(x + 1)$"?