Apakah berang-berang yang sibuk merupakan fungsi dengan pertumbuhan tercepat yang diketahui manusia?

24

Saya hanya punya pertanyaan menarik ini. Apa fungsi yang paling cepat diketahui manusia? Apakah ini berang-berang yang sibuk ?

Kita tahu fungsi seperti , tetapi fungsi ini tumbuh lebih lambat dari , yang pada gilirannya tumbuh lebih lambat dari, yang pada gilirannya tumbuh lebih lambat dari . Kami kemudian dapat menggabungkan fungsi, untuk memilikiyang tumbuh lebih cepat dari , dan seterusnya. $x^2$ $2^x$ $x!$ $x^x$ $(x^x)!$ $x^x$

Kemudian kita sampai pada fungsi rekursif seperti fungsi Ackermann yang tumbuh jauh lebih cepat daripada. Kemudian orang-orang berpikir tentang fungsi berang-berang yang sibuk yang tumbuh lebih cepat daripada fungsi Ackermann. $A(x,x)$ $(x^x)!$ $B(x)$

Pada titik ini saya belum pernah mendengar adanya fungsi lain yang tumbuh lebih cepat daripada berang-berang yang sibuk. Apakah ini berarti bahwa tidak ada fungsi lain yang dapat tumbuh lebih cepat daripada berang-berang yang sibuk? (Selain faktorial dan seperti , dll.) $B(x)$ $A(B(x), B(x))$

computability bodacydo
sumber

25

Berang-berang yang sibuk ^ 2 tumbuh lebih cepat

artistoex

2

@vzn Mengapa pertumbuhan hanya masuk akal untuk fungsi yang dapat dihitung? Pertumbuhan asimptotik adalah konsep matematika yang tidak terkait dengan kemampuan komputasi sama sekali.

Raphael

8

@vzn untuk BB tingkat pertumbuhan menyiratkan tidak dapat dikomputasi. tetapi tidak dapat diperhitungkan tidak berarti tingkat pertumbuhan yang tinggi.

Sasho Nikolov

6

Hai @vzn. Fungsi sedemikian rupa sehingga jika mesin Turing berhenti, dan sebaliknya tidak dapat dihitung tetapi tumbuh lebih lambat daripada fungsi Ackerman. Di sisi lain, mudah untuk membuktikan bahwa untuk beberapa konstanta tetap , untuk semua , BB Ackerman . Jika ini bukan masalahnya, Anda dapat memecahkan masalah penghentian dengan menjalankan mesin turing dengan panjang deskripsi hanya untuk langkah-langkah Ackerman dan melihat apakah berhenti sebelum itu atau tidak.

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$

n

$n$

(n)

$(n)$

Aaron

4

@vzn mungkin Anda memiliki gagasan lain tentang "tumbuh lebih cepat" .. apa yang saya (dan saya percaya orang lain) maksud adalah urutan parsial yang diberikan oleh .

f = ω (g)

$f = \omega(g)$

Sasho Nikolov

49

Fungsi berang-berang yang sibuk tumbuh lebih cepat daripada fungsi yang dapat dihitung . Namun, itu dapat dihitung dengan mesin Turing yang telah diberi akses ke oracle untuk memecahkan masalah penghentian. Anda kemudian dapat menetapkan fungsi berang-berang sibuk "urutan kedua", yang tumbuh lebih cepat daripada fungsi apa pun yang dapat dihitung bahkan oleh mesin Turing apa pun dengan oracle untuk masalah penghentian. Anda dapat terus melakukan ini selamanya, membangun hierarki fungsi berang-berang sibuk yang semakin cepat berkembang.

Lihat esai Scott Aaronson yang sangat baik tentang topik ini, Who Can Name the Bigger Number? .

Harun
sumber

Apakah Anda memiliki sumber daya / alasan mengapa TM oracle untuk HALT_TM dapat menyelesaikan berang-berang yang sibuk?

Ryan

1

Ryan: Memecahkan masalah penghentian adalah (secara komputasi) setara dengan mengetahui Busy Beaver. 1) Apakah program[length=n]berhenti? Simulasikan untuk BusyBeaver(n)langkah - langkahnya. 2) Apa itu BusyBeaver(n)? Untuk setiap program dengan panjang <n, buanglah jika terhenti, dan ambil skor maksimum di antara yang lain.

ninjagecko

@ninjagecko maksudmu tidak berhenti

PyRulez

35

Tidak ada yang namanya "fungsi yang paling cepat berkembang". Bahkan, bahkan tidak ada urutan fungsi yang paling cepat berkembang. Ini sudah ditunjukkan oleh Hausdorff. Diberikan dua fungsi , katakan bahwa tumbuh lebih cepat dari jika $f,g\colon \mathbb{N} \longrightarrow \mathbb{N}$ $g$ $f$ Diberikan fungsi, fungsi berikuttumbuh lebih cepat dari:Dengan urutan fungsi, fungsi berikuttumbuh lebih cepat daripada semuanya:Pertanyaan alami untuk ditanyakan adalah apakah ada "skala" fungsi yang tumbuh paling cepat. Ini adalah satu set baik-memerintahkan fungsiyang merupakan "cofinal", yaitu, mengingat fungsi, ada fungsi yang lebih cepat tumbuh

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 \underset{m \leq n}{maks} f_{m} (n) .

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

g_{α}

$g_\alpha$

f

$f$

g_{α}

$g_\alpha$ . (Alih-alih satu set yang tertata dengan baik, kita dapat secara setara berbicara tentang sebuah rantai, yaitu, dua fungsi dalam set harus sebanding.) Keberadaan skala tidak tergantung pada ZFC: dengan asumsi CH, ada skala, sedangkan dalam model Cohen yang memalsukan CH (menambahkan real), tidak ada skala.

ω_{1}

$\omega_1$

Yuval Filmus
sumber

5

Jawaban lain menjawab pertanyaan secara langsung. Untuk latar belakang yang lebih dan lebih dalam, makalah ini oleh Lafitte pada subjek mempertimbangkan konteks yang lebih besar dari fungsi seperti berang-berang yang sibuk. Ini juga memiliki beberapa hasil dan teorema yang cocok dengan ide ke dalam kerangka kerja yang lebih umum. Ini menunjukkan bahwa (secara informal) "fungsi sibuk seperti berang-berang" memiliki hubungan dekat dengan fenomena ketidaklengkapan Chaitin (Teorema 2.1). Ini juga menunjukkan bahwa ada teori yang tidak "kuat" cukup untuk "memahami" fungsi seperti berang-berang yang sibuk, yaitu mereka tidak terbukti dalam teori-teori itu karena ketidaklengkapan yang berkaitan dengan Godel. Ini menunjukkan ide untuk mengasumsikan hasil seperti berang-berang yang sibuk sebagai aksioma dan perkembangan logis dari teori yang menghasilkan mirip dengan ide yang awalnya dibayangkan oleh Turing.

[1] Berang-berang yang sibuk menjadi liar oleh Grégory Lafitte. Abstrak:

Kami menunjukkan beberapa hasil ketidaklengkapan à la Chaitin menggunakan fungsi berang-berang yang sibuk. Kemudian, dengan bantuan logika ordinal, kami menunjukkan bagaimana memperoleh teori di mana nilai-nilai fungsi berang-berang yang sibuk dapat dibuktikan dan digunakan untuk mengungkapkan struktur pada kemampuan nilai-nilai dari fungsi-fungsi ini.

ay
sumber

jawaban yang lain sama sekali berbeda. hmmm, berbicara tentang "penekanan pada bahasa", akankah contoh itu menjadi moderator yang mengatakan "tidak ada neraka" ? lagipula singkatan dapat dilihat sebagai hadiah besar untuk orang-orang yang suka mendapatkan +2 untuk pengeditan =)

vzn

1

Anda mengatakan pada diri sendiri bahwa ini tidak menjawab secara langsung, jadi mengapa Anda tidak memposting sebagai komentar?

Raphael

0

Teorema hierarki ruang dan waktu Hartmanis-Stearns membuktikan bahwa tidak ada fungsi "pertumbuhan tercepat" dalam hal waktu atau ruang karena skalanya tidak terikat. Tapi itu memang memberikan pemesanan sehingga semua fungsi komputasi / rekursif "berperilaku baik" dapat dibandingkan. Tetapi banyak fungsi matematika "tumbuh cepat" tampaknya tidak dievaluasi dalam hal kompleksitas ruang / waktu sejauh ini meskipun itu menjadi "celah" teoretis yang agak jelas atau bahkan mencolok untuk diisi. Melakukan hal itu dapat mengarah pada "jembatan teorema" yang penting.

ay
sumber

Apakah berang-berang yang sibuk merupakan fungsi dengan pertumbuhan tercepat yang diketahui manusia?

Jawaban: