Очень быстро растущая функция

[Padawan]

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

В связи с этой проблемой рассматривается функция
\varphi (n) = максимальное количество шагов до остановки. Максимум берется по всем машинам Т. с кодом длины \leq n, которые останавливаются .

Очевидно, \varphi (n) -- не убывающая функция.

Эта функция не является ОРФ (обще-рекурсивной функцией), потому что если бы у нас был алгоритм, вычисляющий её для любого n, то, имея код МТ длины n, мы бы посчитали \varphi (n), запустили бы эту МТ и посмотрели, остановится она за \varphi (n) шагов или нет. Остановится -- хорошо, не остановится -- значит не остановится и дальше по определению \varphi (n).

Точно также показывается, что \varphi (n) не может иметь обще-рекурсивную мажоранту, т.е. не существует ОРФ f(n) такой, что для всех натуральных n выполнено \varphi(n) \leq f(n).

Это означает, что \varphi (n) в некотором смысле растет очень быстро.

Вопрос состоит в следующем:
верно ли , что \varphi (n) начиная с некоторого номера обгоняет любую ОРФ?
Точнее: верно ли, что для любой ОРФ f(n) найдется номер N такой, что при n>N \varphi(n) \geq f(n) ?

Если для \varphi это и не так, то существуют ли вообще такие функции?

[Руст]

Padawan писал(а):

В связи с этой проблемой рассматривается функция
\varphi (n) = максимальное количество шагов до остановки. Максимум берется по всем машинам Т. с кодом длины \leq n, которые останавливаются .

Мне кажется, что дело не в том, что эта функция растёт очень быстро, а в том, что она не определена конструктивно. Максимум берётся среди тех которые останавливаются. А известно, что множество машин Тьюринга, которые останавливается, не является конструктивным (не существует алгоритма, определяющего, останавливается машина Тьюринга или нет).

[zw0rk]

Рискну сморозить глупость, потому что курс ТА помню довольно смутно. Но:
1) Что такое "код машины Тьюринга"? Таблица чтоли? Или разложение на "элементарные" машины?
2) Остановится == остановится на любом наборе входящих данных? (то есть при любом состоянии ленты)

[Padawan]

zw0rk писал(а):

Рискну сморозить глупость, потому что курс ТА помню довольно смутно. Но:
1) Что такое "код машины Тьюринга"? Таблица чтоли? Или разложение на "элементарные" машины?
2) Остановится == остановится на любом наборе входящих данных? (то есть при любом состоянии ленты)

1) Не важно, как не определяй, придем к одному и тому же
2) На пустой ленте. Да, мой косяк.

Добавлено спустя 5 минут 25 секунд:

Re: Очень быстро растущая функция

Руст писал(а):

Мне кажется, что дело не в том, что эта функция растёт очень быстро, а в том, что она не определена конструктивно. Максимум берётся среди тех которые останавливаются. А известно, что множество машин Тьюринга, которые останавливается, не является конструктивным (не существует алгоритма, определяющего, останавливается машина Тьюринга или нет).

Просто мне хочется построить функцию, которая будет расти быстрее любой функции, определённой конструктивно. \varphi почти подходит -- её нельзя мажорировать ОРФ

[PAV]

Padawan писал(а):

Просто мне хочется построить функцию, которая будет расти быстрее любой функции, определённой конструктивно. \varphi почти подходит -- её нельзя мажорировать ОРФ

Ну, формально это можно сделать проще. Общерекурсивных функций счетное число, так как каждой соответствует алгоритм вычисления. Перенумеруем их. Теперь определим функцию $\phi$ так: чтобы найти $\phi(n)$, возьмем первые $n$ ОРФ и множество всех значений, которые они принимают на числах от 1 до $n$. В качестве результата $\phi(n)$ вернем любое число, большее всех перечисленных. Так определенная функция удовлетворяет Вашему условию.

Другое дело, что тут мы вступаем на довольно шаткую область, в которой нужно каждый раз задумываться над смыслом слова "определено". Я лично в эту область соваться не рискую. Можно ли считать, что объекты, которыми мы так легко оперируем, определены? Я лично не знаю ответа на этот вопрос. Можно ли считать определенной Вашу функцию, если ее даже теоретически нельзя посчитать в некоторой точке? Я не знаю, равно как и относительно моей функции.

[Руст]

PAV писал(а):

Ну, формально это можно сделать проще. Общерекурсивных функций счетное число, так как каждой соответствует алгоритм вычисления. Перенумеруем их. Теперь определим функцию $\phi$ так: чтобы найти $\phi(n)$, возьмем первые $n$ ОРФ и множество всех значений, которые они принимают на числах от 1 до $n$. В качестве результата $\phi(n)$ вернем любое число, большее всех перечисленных. Так определенная функция удовлетворяет Вашему условию.
Другое дело, что тут мы вступаем на довольно шаткую область, в которой нужно каждый раз задумываться над смыслом слова "определено". Я лично в эту область соваться не рискую. Можно ли считать, что объекты, которыми мы так легко оперируем, определены? Я лично не знаю ответ

Я думаю здесь то же заблуждение, функцией как таковой не существует. Если бы такая функция существовала, то она и так была бы общерекурсивной, что приводит к противоречию.
Я думаю здесь подвох в постановке. Если функция растёт быстрее любой ОРФ, то такая функция не рекурсивна. Поэтому, имеет ли смысль попытаться определить не рекурсивную функцию в явном виде.

[Padawan]

Руст писал(а):

PAV писал(а):

Ну, формально это можно сделать проще. Общерекурсивных функций счетное число, так как каждой соответствует алгоритм вычисления. Перенумеруем их. Теперь определим функцию $\phi$ так: чтобы найти $\phi(n)$, возьмем первые $n$ ОРФ и множество всех значений, которые они принимают на числах от 1 до $n$. В качестве результата $\phi(n)$ вернем любое число, большее всех перечисленных. Так определенная функция удовлетворяет Вашему условию.
Другое дело, что тут мы вступаем на довольно шаткую область, в которой нужно каждый раз задумываться над смыслом слова "определено". Я лично в эту область соваться не рискую. Можно ли считать, что объекты, которыми мы так легко оперируем, определены? Я лично не знаю ответ

Я думаю здесь то же заблуждение, функцией как таковой не существует. Если бы такая функция существовала, то она и так была бы общерекурсивной, что приводит к противоречию.
Я думаю здесь подвох в постановке. Если функция растёт быстрее любой ОРФ, то такая функция не рекурсивна. Поэтому, имеет ли смысль попытаться определить не рекурсивную функцию в явном виде.

Нет, PAV построил хороший пример, мне очень понравился. В качестве N, начиная с которого \phi превосходит любую ОРФ, берём её номер.

Противоречия нет -- конструктивно PAV ничего не определил -- он сказал "занумеруем все ОРФ" -- а эта нумерация не конструктивна. По данному коду МТ мы не можем определить задаёт он ОРФ или нет.

[Руст]

Чтобы вычислить значения функции вам необходимо конструировать рекурсивную нумерацию ОРФ. А этого нельзя сделать. Следовательно нельзя посчитать значения. Понятие существования не конструктивных объектов (если даже об этом можно говорить) имеет совсем другой смысл (непривычный нам).

[Padawan]

Руст писал(а):

Чтобы вычислить значения функции вам необходимо конструировать рекурсивную нумерацию ОРФ. А этого нельзя сделать. Следовательно нельзя посчитать значения. Понятие существования не конструктивных объектов (если даже об этом можно говорить) имеет совсем другой смысл (непривычный нам).

А аксиомой выбора Вы пользуетесь?

[Руст]

Padawan писал(а):

А аксиомой выбора Вы пользуетесь?

Аксиома выбора говорит только о существовании таких неконструктивных объектов. В данном случае, "существует" такая нумерация. Но здесь существует нельзя писать без кавычки. Его нельзя осуществить конструктивно, соответственно его смысл другой. Лично для меня он не существует.