व्यस्त बीवर फ़ंक्शन के आधार पर एक फ़ंक्शन की निर्विवादता

Question

लश्कर $\log _b^ac$एक पुनरावृत्त आधार को निरूपित करें-$b$लघुगणक समारोह। उदाहरण के लिए,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

ट्यूरिंग मशीनों का एक मनमाना मॉडल एम चुनें , यह मानते हुए कि एक मशीन दो-प्रतीक वर्णमाला के साथ संचालित होती है:$0$ रिक्त प्रतीक के रूप में और $1$गैर-रिक्त प्रतीक के रूप में। हम ऐसी मशीनों को "एम-मशीन" कहेंगे।

लश्कर $f(n)$ गैर-रिक्त प्रतीकों की अधिकतम संख्या को निरूपित करें जो टेप पर हो सकते हैं जब एक विशेष एम-मशीन रुक जाती है, यह मानते हुए कि सभी मशीनें रिक्त इनपुट से शुरू होती हैं और निर्देशों की तालिका में सबसे अधिक होते हैं $n$ परिचालन राज्य।

फिर समारोह $F(n)$ इस प्रकार परिभाषित किया गया है: $${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.$$ कहां है $x_n$ इस तरह की सबसे छोटी प्राकृतिक संख्या है $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$

प्रश्न: फ़ंक्शन है $F(n)$ किसी भी मॉडल एम के लिए असुविधाजनक (यानी, वहाँ एक एम-मशीन मौजूद नहीं है जो गणना कर सकता है $F(n)$समारोह, कोई फर्क नहीं पड़ता जो एम हम चुनते हैं)? यदि हाँ (या नहीं), क्या यह साबित करना संभव है?

EDIT
मान लीजिए कि हम "व्यस्त बीवर" विकिपीडिया लेख में "खेल" खंड में वर्णित एक मॉडल चुनते हैं । है$F$ऐसी मशीनों द्वारा अपरिहार्य? मुझे यह साबित करने में भी दिलचस्पी है कि यह कैसे साबित होगा।

Answer 1

नेस्टेड लघुगणक वास्तव में यहाँ बहुत कुछ नहीं करता है। यह एक कम्प्यूटेशनल व्युत्क्रम के साथ एक कम्प्यूटेशनल फ़ंक्शन है, और इस प्रकार कार्य करता है$n \mapsto x_n$ तथा $f$ केवल ट्यूरिंग समतुल्य नहीं हैं, लेकिन संगणनीय पुनरुत्थान के माध्यम से संबंधित हैं।

जैसे, इस प्रश्न का उत्तर यहां भी लागू होता है।

हम निश्चित रूप से अपनी ट्यूरिंग मशीनों को इस तरह से स्थापित कर सकते हैं कि वे कभी भी एक सीमा में गिरने वाले गैर-रिक्त प्रतीकों की कुल संख्या को कभी नहीं लिखते हैं $x_n$विषम। हमें स्वीकार्य सीमाओं का पता लगाने के लिए कुछ पक्ष संगणनाएँ करने की आवश्यकता होगी, लेकिन मुझे दी गई सीमाओं के आकार को देखते हुए उम्मीद है कि जिन प्रतीकों को हमें अगले अंतराल का उपयोग करने की आवश्यकता है, वे अंततः हमें अंतराल से बाहर नहीं लाएंगे।

दूसरी ओर, एक प्राकृतिक सेटअप के लिए मुझे कोई कारण नहीं दिखता है $F$कभी संगणना होगी। लेकिन वास्तव में एक विशेष सेटअप के लिए यह साबित करने के लिए एक विशेष ट्यूरिंग मशीन मॉडल के विवरण के बारे में अधिक सोचने की आवश्यकता होगी जो मैं करना चाहता हूं।