Является ли занятой бобр самой быстрорастущей функцией, известной человеку?

24

У меня просто был этот интересный вопрос. Какая самая быстрорастущая функция известна человеку? Это бобр занят ?

Мы знаем такие функции, как , но эта функция растет медленнее, чем , что, в свою очередь, растет медленнее, чем, который, в свою очередь, растет медленнее, чем . Затем мы можем объединить функции, чтобы иметь (х ^ х)! который растет быстрее, чем х ^ х , и так далее.2 х х ! х х ( х х ) !x22xx!xx(xx)!xx

Затем мы приходим к рекурсивным функциям, таким как функция Аккермана A(x,x) которая растет намного быстрее, чем (xx)!, Тогда люди думают о функции занятого бобра B(x) которая растет даже быстрее, чем функция Аккермана.

На данный момент я не слышал ни о каких других функциях, которые растут быстрее, чем занятые бобра. Означает ли это, что нет других функций, которые могли бы расти быстрее, чем занятый бобер? (Помимо факториала B(x) и тому подобного A(B(x),B(x)) и т. Д.)

bodacydo
источник
25
Занятый бобер ^ 2 растет быстрее
artistoex
2
@vzn Почему рост имеет смысл только для вычислимых функций? Асимптотический рост - это математическая концепция, вообще не связанная с вычислимостью.
Рафаэль
8
@vzn для BB скорость роста подразумевает невычислимость. но невычислимость не подразумевает высокие темпы роста.
Сашо Николов
6
Привет @vzn. Функция такая, что если -тая машина Тьюринга останавливается, а противном случае невычислима, но растет медленнее, чем функция Аккермана. С другой стороны, легко доказать, что для некоторой фиксированной константы , для всех , BB Ackerman . Если бы это было не так, вы могли бы решить проблему остановки, запустив машину Тьюринга с длиной описания только для шагов Аккермана и посмотрев, остановилась ли она раньше или нет. f ( n ) = 1 n f ( n ) = 0 c n > c ( n ) > ( n ) T n ( n )ff(n)=1nf(n)=0cn>c(n)>(n)Tn(n)
Аарон
4
@vzn, может быть, у вас есть другая идея «растет быстрее» ... что я (и я верю другим) имею в виду, это частичный порядок, заданный . f=ω(g)
Сашо Николов

Ответы:

49

Функция занятого бобра растет быстрее, чем любая вычисляемая функция . Однако его можно вычислить на машине Тьюринга, которой был предоставлен доступ к оракулу для решения проблемы остановки. Затем вы можете определить функцию занятого бобра «второго порядка», которая будет расти быстрее, чем любая функция, которая может быть вычислена даже любой машиной Тьюринга с оракулом для решения проблемы остановки. Вы можете продолжать делать это вечно, создавая иерархию все более быстро растущих загруженных функций бобра.

См. Превосходное эссе Скотта Ааронсона на эту тему, Кто может назвать большее число? ,

Аарон
источник
У вас есть ресурс / рассуждение о том, почему оракул TM для HALT_TM может решить занятого бобра?
Райан
1
Райан: Решение проблемы остановки (в вычислительном отношении) эквивалентно знанию Busy Beaver. 1) program[length=n]останавливается? Смоделируйте это для BusyBeaver(n)шагов. 2) что есть BusyBeaver(n)? Для каждой программы длины <n выбросьте ее, если она остановится, и возьмите максимальный балл среди других.
ninjagecko
@ninjagecko ты имеешь в виду не останавливается
PyRulez
35

f,g:NNgf

limng(n)f(n)=.
fgf
g(n)=nf(n).
fng
g(n)=nmaxmnfm(n).
Естественный вопрос - существует ли «масштаб» наиболее быстро растущих функций? Это хорошо упорядоченный набор функций который является «cofinal», то есть для любой функции существует быстро растущая функция . (Вместо хорошо упорядоченного набора мы можем эквивалентно говорить о цепочке, то есть любые две функции в наборе должны быть сопоставимы.) Существование шкалы не зависит от ZFC: при условии, что CH, есть шкала, в то время как в модели Коэна, которая фальсифицирует CH (добавляя реалов), масштаб не существует.gαfgαω1
Юваль Фильмус
источник
5

Другие ответы касаются вопроса напрямую. Для более глубокого понимания этой статьи Lafitte на эту тему рассматривается более широкий контекст функций, похожих на занятых бобров. У этого также есть некоторые результаты и теоремы, вписывающие идею в более общую структуру. Это показывает, что (неформально) «занятые бобероподобные функции» имеют тесную связь с явлениями неполноты Чайтина (теорема 2.1). Это также показывает, что существуют теории, которые не являются «достаточно мощными», чтобы «постичь» занятые бобоподобные функции, т.е. они недоказуемы в этих теориях из-за неполноты, связанной с Годелем. Это показывает идею принятия занятых бобровидных результатов в качестве аксиом и логическое развитие теорий, которые приводят к подобным идеям, изначально предполагаемым Тьюрингом.

[1] Грегори Лафитт сходит с ума от занятых бобров . Аннотация:

Мы показываем некоторые результаты неполноты а-ля Chaitin с использованием функций занятого бобра. Затем с помощью порядковых логик мы покажем, как получить теорию, в которой значения доказательств занятых функций бобра можно доказуемо установить, и использовать ее для выявления структуры доказуемости значений этих функций.

ВЗН
источник
другой ответ совершенно другой. хммм, говоря о «акценте на язык», может ли модератор сказать «черт возьми нет» ? в любом случае, сокращения можно рассматривать как щедрый дар людям, которые любят зарабатывать +2 за правки =)
vzn
1
Вы сами говорите, что это не отвечает напрямую, так почему вы не разместили в качестве комментария?
Рафаэль
0

Теоремы иерархии времени и пространства Хартманиса-Стернса доказывают, что не существует «наиболее быстро растущей» функции с точки зрения времени или пространства, поскольку масштаб не ограничен. Но он дает такой порядок , что все «хорошо себя ведущие» вычислимые / рекурсивные функции можно сравнивать. Но многие «быстро растущие» математические функции, по-видимому, до сих пор не были оценены с точки зрения сложности времени / пространства, несмотря на то, что это несколько очевидный или даже вопиющий теоретический «пробел» для заполнения. Это может привести к важным "теоремам моста".

ВЗН
источник