Apakah fungsi yang tidak dapat dikomputasi tumbuh lebih besar secara asimptotik?

Saya membaca tentang nomor berang-berang yang sibuk dan bagaimana mereka tumbuh secara asimptotik lebih besar daripada fungsi yang dapat dihitung. Kenapa begitu? Apakah ini karena ketidaksesuaian fungsi berang-berang yang sibuk? Jika demikian, apakah semua fungsi yang tidak dapat dikomputasi tumbuh secara asimptotik lebih besar dari yang dapat dikomputasi?

Edit:

Jawaban yang bagus di bawah ini tetapi saya ingin menjelaskan dalam bahasa inggris yang lebih jelas apa yang saya mengerti tentang mereka.

Jika ada fungsi yang dapat dihitung f yang tumbuh lebih cepat daripada fungsi berang-berang yang sibuk, maka ini berarti bahwa fungsi berang-berang yang sibuk dibatasi oleh f. Dengan kata lain, mesin turing hanya perlu dijalankan untuk f (n) banyak langkah untuk memutuskan masalah penghentian. Karena kita tahu masalah penghentian tidak dapat diputuskan, anggapan awal kita salah. Oleh karena itu, fungsi berang-berang yang sibuk tumbuh lebih cepat daripada semua fungsi yang dapat dihitung.

Jika Anda mengambil himpunan bilangan alami yang tidak dapat dihitung, fungsi karakteristik himpunan hanya mengambil nilai dan tidak dapat dihitung. Jadi bukan kasus setiap fungsi nonkomputasi tumbuh sangat cepat, mereka bahkan dapat dibatasi.$\{0,1\}$

Fungsi Busy Beaver tumbuh lebih cepat daripada setiap fungsi yang dapat dihitung karena dibangun untuk melakukannya. Bukti bahwa itu hasil nonkomputasi dengan terlebih dahulu membuktikan bahwa ia tumbuh lebih cepat daripada fungsi yang dapat dihitung.

$A \subseteq \mathbb{N}$$A$

$B$$e$$f$$f(n) = k$$e$$n$$k$$f(n) = 0$$e$$n$$B$$B$

$f$$F$$f \in \omega(g)$$o(g)$$g \in F$$f \notin F$

$\{0,1\}$$O(1)$

Tentu saja ada set fungsi yang runtime merupakan kriteria keanggotaan yang diperlukan dan cukup, yaitu yang ditandai dengan runtime, seperti

$\qquad \displaystyle \mathrm{Poly} = \{f : \mathbb{N} \to \mathbb{N} \mid \exists k.\, f \in O(n^k)\}$

1. Itu hanya masuk akal dalam jumlah terbatas. Parameter fungsi HP adalah penyandian mesin Turing dan angka alami; ukurannya bukan ukuran seberapa rumitnya memutuskan untuk berhenti.