Частично-рекурсивная функция

[buzanovn]

Необходимо доказать, что существует такая функция $g(x)$, что $g(x) > f(x)$, где $f(x)$ -- любая частично-рекурсивная функция. Была дана подсказка, что $g(x)$ не вычислимая. И по-моему нужно отталкиваться от нумерации частично-рекурсивных функций.
Была идея взять частично-рекурсивную не вычислимую функцию (и слегка её видоизменить)

$$g(x) = \left\{ \begin{aligned} & f(x) + 1, \text{если $f(x)$ -- определена} \\ & 0 \text{, если $f(x)$ -- не определена} \right. \end{aligned} $$

но возникает вопрос, а что тогда такое $f(x)$ в этой формуле, если $f(x)$ -- любая.

[Sonic86]

buzanovn в сообщении #1089247 писал(а):

Необходимо доказать, что существует такая функция $g(x)$, что $g(x) > f(x)$, где $f(x)$ -- любая частично-рекурсивная функция.

Вопрос сформулирован криво. На автомате он читается как
"Необходимо доказать, что существует такая функция $g(x)$, что $(\forall x)g(x) > f(x)$, где $f(x)$ -- любая частично-рекурсивная функция.", что, очевидно, неверно.

buzanovn в сообщении #1089247 писал(а):

И по-моему нужно отталкиваться от нумерации частично-рекурсивных функций.

Ага, вот и оттолкнитесь.
Про функцию Аккермана слыхали? Вот и ...

[buzanovn]

Цитата:

Вопрос сформулирован криво. На автомате он читается как
"Необходимо доказать, что существует такая функция $g(x)$, что $(\forall x)g(x) > f(x)$, где $f(x)$ -- любая частично-рекурсивная функция.", что, очевидно, неверно.

Всё таки "Необходимо доказать, что существует такая функция $g(x)$, что $\forall f(x)\text{ -- ч.р.ф.} : g(x) > f(x)$".

Прочитал про функцию Аккермана, понятно что она растёт быстро (вероятно быстрее любой другой ч.р.ф), но причем тут нумерация. Раз мы берем любую $f(x)$, то и номер гёделев получается любой. По сути $g(x) = A(x,x)$, но совершенно не обязательно, что условие $g(x) > f(x)$ выполнится.

[Someone]

buzanovn в сообщении #1089299 писал(а):

Всё таки "Необходимо доказать, что существует такая функция $g(x)$, что $\forall f(x)\text{ -- ч.р.ф.} : g(x) > f(x)$".

В каком смысле здесь нужно понимать знак неравенства? То, что Вы написали, понимается как

Sonic86 в сообщении #1089273 писал(а):

"Необходимо доказать, что существует такая функция $g(x)$, что $(\forall x)g(x) > f(x)$, где $f(x)$ -- любая частично-рекурсивная функция.",

и такой функции заведомо нет.

[buzanovn]

Видимо я неверно трактую вашу запись и пардон мою глупость, но: "существует ли функция $g(x)$, значение которой строго больше чем значение любой частично-рекурсивной функции $f(x)$ " не много отличается от вашей записи.

[arseniiv]

Если вопрос всё-таки «существует ли», то ответ, как уже сказали, отрицательный. Рассмотрите хотя бы как источник $f$ множество всех константных функций. Так что надо уточнить условие, по-другому никак.