Meşgul Kunduz işlevine dayalı bir işlevin hesaplanamazlığı

Question

İzin Vermek $\log _b^ac$Bir ifade tekrarlanan base$b$logaritma işlevi. Örneğin,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

Bir makinenin iki sembollü alfabeyle çalıştığını varsayarak, Turing makinelerinin rastgele bir M modelini seçin :$0$ boş sembol olarak ve $1$boş olmayan sembol olarak. Bu tür makinelere "M-makineler" adını vereceğiz.

İzin Vermek $f(n)$ Tüm makinelerin boş girişle başladığını ve talimat tablosunun en fazla içerdiğini varsayarak, belirli bir M-makinesi durduğunda bantta oluşabilecek maksimum boş olmayan sembol sayısını belirtir. $n$ operasyonel durumlar.

Sonra işlev $F(n)$ aşağıdaki gibi tanımlanır: $${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.$$ nerede $x_n$ en küçük doğal sayıdır, öyle ki $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$

Soru: işlev $F(n)$ herhangi bir M modeli için hesaplanamaz (yani, hesaplayabilen bir M-makinesi yoktur. $F(n)$hangi M'yi seçersek seçelim)? Evetse (veya hayırsa), bunu kanıtlamak mümkün mü?

DÜZENLE "Meşgul Kunduz" Wikipedia makalesindeki "
Oyun" bölümünde açıklanan bir model seçtiğimizi varsayalım . Dır-dir$F$bu tür makineler tarafından hesaplanamaz mı? Bunu nasıl kanıtlayacağımla da ilgileniyorum.

Answer 1

İç içe geçmiş logaritma burada pek bir işe yaramıyor. Hesaplanabilir bir tersi olan hesaplanabilir bir fonksiyondur ve dolayısıyla fonksiyonlar$n \mapsto x_n$ ve $f$ sadece Turing eşdeğeri değil, aynı zamanda hesaplanabilir yeniden ölçeklendirme ile de ilgilidir.

Bunun gibi, cevabı bu soruya da burada geçerlidir.

Turing makinelerimizi kesinlikle bir aralığa düşen boş olmayan sembollerin toplam sayısını asla yazmayacakları şekilde kurabiliriz. $x_n$garip. Kabul edilebilir aralıkları bulmak için bazı yan hesaplamalar yapmamız gerekirdi, ancak aralıkların boyutu göz önüne alındığında, kullanabileceğimiz bir sonraki aralığı belirlememiz için ihtiyacımız olan sembollerin sonunda bizi aralığın dışına çıkarmayacağını umuyorum.

Öte yandan, doğal bir kurulum için hiçbir neden göremiyorum $F$hesaplanabilir olacaktı. Ama aslında bunu belirli bir kurulum için kanıtlamak, belirli bir Turing makine modelinin detayları hakkında yapmak istediğimden çok daha fazla düşünmeyi gerektirecektir.