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

[rwanda]

Добрый вечер!
Прошу сведущих проверить мое решение. Не закидывайте, пожалуйста, помидорами, если ошибки кажутся Вам очевидными, освоение темы ведется собственными силами, книги читаются, лекции смотрятся, но занятия с преподавателем мне, к сожалению, не доступны. На усвоение элементарных вещей уходит не один час гугла и медитации в книги.

Итак, условие:
Докажите, что функция $f(x) = [\log_2 x + 1]$ является примитивно рекурсивной.

Решение:
Так, чтобы избежать необходимости возиться с ограниченной минимизацией [много времени потрачено, идея ясна, но понятных примеров, как корректно использовать, не нашлось :(], делаем преобразование. $f(x) = [\log_2 x + 1]=[\log_2 x + \log_2 2]=[\log_2 (x+1)]$. Все, теперь нам не страшно значение $x$ в нуле.

База индукции:
$f(0) = [\log_2 (0 + 1)]=0$

Суть рекурсивной функции, как я поняла, в том, что мы можем получить ответ для $x+1$, зная ответ для $x$. То есть функция построена таким образом, что обращается к "предыдущим" значениям.

Вот мое представление $f(x) = [\log_2 x + 1]$ в подобном виде.
$f(x+1) = f(x) + sg((x+2) \dot{-} 2^{f(x)})$

Пример,
(1)
$x=5=4+1 $
$f(4)=3 $
$f(4+1)=3+0=3$
(2)
$x=8=7+1 $
$f(7)=3 $
$f(7+1)=3+1=4$

Скажите, достаточно ли приведенного для доказательства к задаче? Есть ли ошибки? Где? Как исправить?

[Someone]

rwanda в сообщении #1295901 писал(а):

Суть рекурсивной функции, как я поняла, в том, что мы можем получить ответ для $x+1$, зная ответ для $x$.

Суть рекурсивной функции. Вы теорию вычислимости изучаете?

[rwanda]

Someone
Тогда то, что я там написала в "сути" это доказательство по индукции?
Да, ее.

-- 07.03.2018, 21:00 --

Someone
Можете дать комментарий по решению? Достаточным ли является доказательство?
$f(0) = [\log_2 (0 + 1)]=0$
$f(x+1) = f(x) + sg((x+2) \dot{-} 2^{f(x)})=g(x,f(x))$

[rwanda]

UPD.
Очень глупая ошибка с преобразованием. Теперь нужна будет ограниченная минимизация.
$f(x) = [\log_2 x + 1]=[\log_2 x + \log_2 2]=[\log_2 2x]$

(страшно стыдно за такую глупость)

-- 08.03.2018, 00:12 --

Не понятно, что делать дальше, но, как минимум, формула будет такой.
$f(x+1) = f(x) + sg((x+1) \dot{-} 2^{f(x)})$