Fungsi yang tidak dapat dihitung berdasarkan fungsi Busy Beaver

Jan 12 2021

Membiarkan $\log _b^ac$menunjukkan sebuah iterasi dasar-$b$fungsi logaritma. Sebagai contoh,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

Pilih model M sembarang dari mesin Turing, dengan asumsi bahwa mesin beroperasi dengan alfabet dua simbol:$0$ sebagai simbol kosong dan $1$sebagai simbol tidak kosong. Kami akan menyebut mesin seperti itu "M-machine".

Membiarkan $f(n)$ menunjukkan jumlah maksimum simbol tidak kosong yang dapat terjadi pada rekaman ketika mesin-M tertentu berhenti, dengan asumsi bahwa semua mesin mulai dengan input kosong dan tabel instruksi berisi paling banyak $n$ status operasional.

Kemudian fungsinya $F(n)$ didefinisikan sebagai berikut: $${F}(n) = \left\{ \begin{array}{l} 0\quad {\text{if}}\;{x_n}\;{\text{is even}}{\text{,}}\\ 1\quad {\text{if}}\;{x_n}\;{\text{is odd}}{\text{,}} \end{array} \right.$$ dimana $x_n$ adalah bilangan asli terkecil sehingga $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$

Pertanyaan: adalah fungsinya $F(n)$ tidak dapat dihitung untuk model M apa pun (artinya, tidak ada mesin-M yang dapat menghitung $F(n)$fungsi, tidak peduli M mana yang kita pilih)? Jika ya (atau tidak), apakah mungkin untuk membuktikannya?

EDIT
Misalkan kita memilih model yang dijelaskan di bagian "Permainan" di artikel Wikipedia "Busy Beaver" . Aku s$F$tidak dapat dihitung oleh mesin seperti itu? Saya juga tertarik untuk membuktikannya.

Jawaban

3 Arno Jan 13 2021 at 10:53

Logaritma bersarang tidak banyak membantu di sini. Ini adalah fungsi yang dapat dihitung dengan invers yang dapat dihitung, dan dengan demikian fungsi-fungsinya$n \mapsto x_n$ dan $f$ tidak hanya setara dengan Turing, tetapi juga terkait melalui penskalaan ulang yang dapat dihitung.

Karena itu, jawaban atas pertanyaan ini juga berlaku di sini.

Kami sangat pasti dapat mengatur mesin Turing kami sedemikian rupa sehingga mereka tidak pernah menulis jumlah simbol tidak kosong yang jatuh ke dalam kisaran yang akan membuatnya. $x_n$aneh. Kita perlu melakukan beberapa perhitungan samping untuk mengetahui rentang yang dapat diterima, tetapi mengingat ukuran rentang, saya berharap bahwa simbol yang kita perlukan untuk menentukan interval berikutnya yang dapat kita gunakan pada akhirnya tidak akan membawa kita keluar dari interval.

Di sisi lain, untuk pengaturan alami saya tidak melihat alasannya $F$akan pernah bisa dihitung. Tapi sebenarnya membuktikan ini untuk pengaturan tertentu akan membutuhkan pemikiran lebih banyak tentang detail model mesin Turing tertentu daripada yang ingin saya lakukan.