Czy zajęty bóbr to najszybciej rosnąca funkcja znana człowiekowi?

24

Właśnie miałem to interesujące pytanie. Jaka jest najszybciej rosnąca funkcja znana człowiekowi? Czy to zajęty bóbr ?

Znamy funkcje takie jak $x^2$ , ale ta funkcja rośnie wolniej niż $2^x$ , co z kolei rośnie wolniej niż, który z kolei rośnie wolniej niż . Następnie możemy łączyć funkcje, aby miećktóry rośnie szybciej niż i tak dalej. $x!$ $x^x$ $(x^x)!$ $x^x$

Następnie dochodzimy do funkcji rekurencyjnych, takich jak funkcja Ackermanna która rośnie znacznie szybciej niż. Potem ludzie zastanawiają się nad zajętą funkcją bobra która rośnie nawet szybciej niż funkcja Ackermanna. $A(x,x)$ $(x^x)!$ $B(x)$

W tym momencie nie słyszałem o żadnych innych funkcjach, które rosłyby szybciej niż zajęty bóbr. Czy to oznacza, że nie ma innych funkcji, które mogłyby rosnąć szybciej niż zajęty bóbr? (Poza silnią i podobną do itp.) $B(x)$ $A(B(x), B(x))$

computability

— bodacydo
źródło

25

Zajęty bóbr ^ 2 rośnie szybciej

— artistoex

2

@vzn Dlaczego wzrost miałby sens tylko dla funkcji obliczalnych? Wzrost asymptotyczny jest matematyczną koncepcją niezwiązaną w ogóle z obliczalnością.

— Raphael

8

@vzn dla BB stopa wzrostu oznacza niepoliczalność. ale nieobliczalność nie oznacza wysokiego tempa wzrostu.

— Sasho Nikolov,

6

Cześć @vzn. Funkcja

taka, że

jeśli

-ta maszyna Turinga zatrzyma się, a

przeciwnym razie jest nieobliczalna, ale rośnie wolniej niż funkcja Ackermana. Z drugiej strony łatwo jest udowodnić, że dla niektórych stałych stałych

, dla wszystkich

, BB

Ackerman

. Gdyby tak nie było, można by rozwiązać problem zatrzymania, uruchamiając maszynę

o długości opisu

f

$f$

f (n) = 1

$f(n) = 1$

n

$n$

f (n) = 0

$f(n) = 0$

c

$c$

n > c

$n > c$

(n) >

$(n) >$

(n)

$(n)$

T

$T$

tylko dlakrokówAckermana

i sprawdzenie, czy zatrzymał się wcześniej, czy nie.

n

$n$

(n)

$(n)$

— Aaron,

4

@vzn może masz inny pomysł na „rośnie szybciej” .. to, co ja (i wierzę, że inni) mam na myśli, to częściowe uporządkowanie podane przez

.

f = ω (g)

$f = \omega(g)$

— Sasho Nikolov

49

Zajęty bóbr rośnie szybciej niż jakakolwiek funkcja obliczalna . Można go jednak obliczyć za pomocą maszyny Turinga, która otrzymała dostęp do wyroczni w celu rozwiązania problemu zatrzymania. Następnie można zdefiniować funkcję bobra zajętego „drugiego rzędu”, która rośnie szybciej niż jakakolwiek funkcja, która może być obliczona nawet przez dowolną maszynę Turinga z wyrocznią dotyczącą problemu zatrzymania. Możesz to robić wiecznie, budując hierarchię coraz szybciej rozwijających się funkcji bobra.

Zobacz doskonały esej Scotta Aaronsona na ten temat: Kto może wymienić większą liczbę? .

— Aaron
źródło

Czy masz źródło / uzasadnienie, dlaczego wyrocznia TM dla HALT_TM może rozwiązać zajęty bóbr?

— Ryan

1

Ryan: Rozwiązanie problemu zatrzymania jest (obliczeniowo) równoważne znajomości Busy Beaver. 1) Czy program[length=n]zatrzymuje się? Symuluj dla BusyBeaver(n)kroków. 2) Co to jest BusyBeaver(n)? Za każdy program o długości <n wyrzuć go, jeśli się zatrzyma, i weź maksymalny wynik spośród innych.

— ninjagecko

@ninjagecko czy masz na myśli nie przestaje

— PyRulez

35

Nie ma czegoś takiego jak „najszybciej rosnąca funkcja”. W rzeczywistości nie ma nawet sekwencji najszybciej rosnących funkcji. Zostało to już pokazane przez Hausdorffa. Biorąc pod uwagę dwie funkcje , powiedzmy, że rośnie szybciej niż jeśli $f,g\colon \mathbb{N} \longrightarrow \mathbb{N}$ $g$ $f$ Biorąc pod uwagę funkcję, następująca funkcjarośnie szybciej niż:Biorąc pod uwagę sekwencję funkcji, następująca funkcjarośnie szybciej niż wszystkie:

lim_{n \to \infty} \frac{g (n)}{f (n)} = \infty .

$\lim_{n\rightarrow\infty} \frac{g(n)}{f(n)} = \infty.$

f

$f$

g

$g$

f

$f$

g (n) = n f (n) .

$g(n) = nf(n).$

f_{n}

$f_n$

g

$g$

g (n) = n max_{m \leq n} f_{m} (n) .

$g(n) = n \max_{m \leq n} f_m(n).$ Naturalnym pytaniem jest to, czy istnieje „skala” najszybciej rosnących funkcji. Jest to dobrze uporządkowany zestaw funkcji

który jest „cofinal”, co oznacza, że przy dowolnej funkcji

istnieje szybciej rosnąca funkcja

. (Zamiast dobrze uporządkowanego zestawu, możemy w równoważny sposób mówić o łańcuchu, to znaczy, że dowolne dwie funkcje w zestawie muszą być porównywalne.) Istnienie skali jest niezależne od ZFC: zakładając, że CH, istnieje skala, natomiast w modelu Cohena że fałszuje CH (dodanie

Real) nie istnieje waga.

g_{α}

$g_\alpha$

f

$f$

g_{α}

$g_\alpha$

ω_{1}

$\omega_1$

— Yuval Filmus
źródło

5

Inne odpowiedzi odnoszą się bezpośrednio do pytania. Aby uzyskać więcej i głębsze tło, ten artykuł autorstwa Lafitte na ten temat rozważa szerszy kontekst zajętych funkcji podobnych do bobrów. Ma również pewne wyniki i twierdzenia pasujące do pomysłu w bardziej ogólnych ramach. Pokazuje, że (nieformalnie) „zajęte funkcje podobne do bobrów” mają ścisły związek ze zjawiskiem niekompletności Chaitin (Twierdzenie 2.1). Pokazuje także, że istnieją teorie, które nie są „wystarczająco mocne”, aby „zrozumieć” zajęte funkcje podobne do bobrów, tj. Są nie do udowodnienia w tych teoriach z powodu niekompletności związanej z Godlem. Pokazuje ideę zakładania zajętych wyników podobnych do bobrów jako aksjomatów i logicznego postępu teorii, które dają wyniki podobne do pomysłów pierwotnie przewidzianych przez Turinga.

[1] Zajęte bobry oszalały przez Grégory Lafitte. Abstrakcyjny:

Pokazujemy niektóre wyniki niekompletności à la Chaitin przy użyciu zajętych funkcji bobra. Następnie, za pomocą logiki porządkowej, pokazujemy, jak uzyskać teorię, w której można ustalić wartości zajętych funkcji bobra, i wykorzystać to do ujawnienia struktury sprawdzalności wartości tych funkcji.

— vzn
źródło

druga odpowiedź jest zupełnie inna. hmmm, mówiąc o „nacisku na język”, czy przykładem może być moderator mówiący „piekło nie” ? w każdym razie skróty mogą być postrzegane jako hojny prezent dla osób, które lubią zarabiać +2 za edycję =)

— dniu

1

Mówisz sobie, że to nie odpowiada bezpośrednio, więc dlaczego nie opublikowałeś komentarza?

— Raphael

0

Twierdzenia o hierarchii czasu i przestrzeni Hartmanisa-Stearnsa dowodzą, że nie ma funkcji „najszybciej rosnącej” pod względem czasu lub przestrzeni, ponieważ skala jest nieograniczona. Ale daje takie uporządkowanie , że można porównać wszystkie „dobrze wychowane” funkcje obliczeniowe / rekurencyjne. Jednak wiele „szybko rosnących” funkcji matematycznych nie wydaje się jak dotąd ocenianych pod względem złożoności czasu / przestrzeni, mimo że jest to dość oczywista, a nawet rażąca teoretyczna „luka” do wypełnienia. Może to doprowadzić do powstania ważnych „twierdzeń pomostowych”.

— vzn
źródło