Comments 12
Никогда не понимал стремление получить функцию которая растёт быстрее других. Всегда же можно придумать что-то растущее быстрее, или нет? Вот возьмём:
A(A(n)), она же растёт быстрее чем A(n)?
A(A(n)), она же растёт быстрее чем A(n)?
Можно придумать, но расти это будет все равно не так быстро. Математики придумали кучу всяких операций для выражения действительно больших чисел :) О действительно БОЛЬШИХ числах (часть 1), Гугология (это не опечатка) для программистов.
она будет примитивно-рекурсивной?
Да, такая функция будет расти, конечно, быстрее :)
Вообще, действительно, придумать быстрорастущую функцию — не rocket science. Тут вся суть утверждения в том, что ПРФы в принципе не способны расти сколь угодно быстро.
Ну а ещё для нас важно, что функция Аккермана растёт быстро, потому что это значит, что обратная к ней функция растёт медленно. И этим обосновывается «почти константная» асимптотика методов DSU.
Вообще, действительно, придумать быстрорастущую функцию — не rocket science. Тут вся суть утверждения в том, что ПРФы в принципе не способны расти сколь угодно быстро.
Ну а ещё для нас важно, что функция Аккермана растёт быстро, потому что это значит, что обратная к ней функция растёт медленно. И этим обосновывается «почти константная» асимптотика методов DSU.
Грубо говоря, примитивно-рекурсивные функции — это всё, что получается из простейших с помощью итерации. Итерируем прибавление единицы — получаем сложение. Итерируем сложение — получаем умножение. Итерируем умножение — получаем экспоненту. Итерируем экспоненту — получаем гиперэкспоненту. Итерируем гиперэкспоненту — получаем чёрт знает что, но его тоже можно дальше итерировать. А теперь возьмём функцию, которая «итерирует сама себя». Точнее, возьмём функцию с дополнительным аргументом n, причём функция A(n+1,...) получается итерацией функции A(n,...) Это и есть функция Аккермана.
Итерируем экспоненту — получаем гиперэкспоненту. Итерируем гиперэкспоненту — получаем чёрт знает что, но его тоже можно дальше итерировать.
А теперь возьмём функцию, которая «итерирует сама себя». Точнее, возьмём функцию с дополнительным аргументом n, причём функция A(n+1,...) получается итерацией функции A(n,...)
Это выражается всего лишь цепочками Конвея. Есть и более быстрорастущие функции, которые выражаются с помощью массивной нотации.
Эта функция появилась не просто так. Математики хотели максимально подробно изучить класс всех частично-рекурсивных функций, т.е. вычислимых. Оказалось, что аккермановская функция не является ПРФ, но остается ЧРФ, мало того, она еще и тотальна (всюду определена). Но и теории алгоритмов, и в основаниях математики нас больше интересует доказуемость тотальности, т.е. доказательство того, что алгоритм сходится на любом входе. И вот тут начинаются проблемы.
Про ПРФ и Аккермана мы можем не более чем двумя вложенными индукциями доказать их тотальность. Но если мы теперь в схеме построения рекурсий в качестве базовой функции вместо S(x)=x+1 возьмем аккермана и точно так же выстроим последовательность быстрорастущих функций, то для доказательства их тотальности потребуется еще больше вложенных индукций. И так далее.
Сложность этих функций и соответствующих им формальных арифметических теорий, способных доказывать их тотальность, измеряется ординалами. Так, аксиоматика EA позволяет строить рекурсии только до ординала \omega^\omega, а арифметика Пеано первого порядка (PA) — до ординала \epsilon_0.
Оказывается, что класс доказуемо тотальных функций арифметики PA хоть и большой (он включает ПРФ и аккермана), но не покрывает все вычислимые функции.
Если мы в описанной иерархии дойдем до функции с номером epsilon_0, то она уже не будет лежать в данном классе.
Тем самым мы умеем сравнивать силу формальных систем с помощью ординалов. Этими вопросами занимается ординальная теория доказательств. На основе этой шкалы мы также можем судить, каким формализмом (читай — языком программирования) лучше пользоваться, если мы хотим гарантировать сходимость алгоритмов.
PS. Функция Гудстейна, например, имеет такую скорость роста, что ее тотальность недоказуема в арифметике первого порядка. Поэтму и сама теорема Гудстейна являет нам пример недоказуемого и неопровержимого утверждения для арифметики Пеано.
Про ПРФ и Аккермана мы можем не более чем двумя вложенными индукциями доказать их тотальность. Но если мы теперь в схеме построения рекурсий в качестве базовой функции вместо S(x)=x+1 возьмем аккермана и точно так же выстроим последовательность быстрорастущих функций, то для доказательства их тотальности потребуется еще больше вложенных индукций. И так далее.
Сложность этих функций и соответствующих им формальных арифметических теорий, способных доказывать их тотальность, измеряется ординалами. Так, аксиоматика EA позволяет строить рекурсии только до ординала \omega^\omega, а арифметика Пеано первого порядка (PA) — до ординала \epsilon_0.
Оказывается, что класс доказуемо тотальных функций арифметики PA хоть и большой (он включает ПРФ и аккермана), но не покрывает все вычислимые функции.
Если мы в описанной иерархии дойдем до функции с номером epsilon_0, то она уже не будет лежать в данном классе.
Тем самым мы умеем сравнивать силу формальных систем с помощью ординалов. Этими вопросами занимается ординальная теория доказательств. На основе этой шкалы мы также можем судить, каким формализмом (читай — языком программирования) лучше пользоваться, если мы хотим гарантировать сходимость алгоритмов.
PS. Функция Гудстейна, например, имеет такую скорость роста, что ее тотальность недоказуема в арифметике первого порядка. Поэтму и сама теорема Гудстейна являет нам пример недоказуемого и неопровержимого утверждения для арифметики Пеано.
Sign up to leave a comment.
Примитивно-рекурсивные функции и функция Аккермана