ความสามารถในการคำนวณของฟังก์ชันที่ขึ้นอยู่กับฟังก์ชัน Busy Beaver
ปล่อย $\log _b^ac$หมายถึงฐานที่ทำซ้ำ -$b$ฟังก์ชันลอการิทึม ตัวอย่างเช่น,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$
เลือกแบบจำลอง M ของเครื่องทัวริงโดยพลการสมมติว่าเครื่องทำงานด้วยตัวอักษรสองสัญลักษณ์:$0$ เป็นสัญลักษณ์ว่างและ $1$เป็นสัญลักษณ์ไม่เว้นว่าง เราจะเรียกเครื่องจักรดังกล่าวว่า "M-Machines"
ปล่อย $f(n)$ หมายถึงจำนวนสูงสุดของสัญลักษณ์ที่ไม่ว่างเปล่าซึ่งอาจเกิดขึ้นที่เทปเมื่อเครื่อง M เครื่องใดเครื่องหนึ่งหยุดโดยสมมติว่าเครื่องทั้งหมดเริ่มต้นด้วยอินพุตว่างและตารางคำแนะนำมีมากที่สุด $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)$ ไม่สามารถคำนวณได้สำหรับรุ่น M ใด ๆ (นั่นคือไม่มีเครื่อง M ที่สามารถคำนวณไฟล์ $F(n)$ฟังก์ชั่นไม่ว่าเราจะเลือก M ตัวไหน)? ถ้าใช่ (หรือไม่ใช่) เป็นไปได้ไหมที่จะพิสูจน์สิ่งนี้?
แก้ไข
สมมติว่าเราเลือกรูปแบบที่อธิบายไว้ใน "เกม" ในหัวข้อ"ไม่ว่าง Beaver" บทความวิกิพีเดีย คือ$F$เครื่องดังกล่าวไม่สามารถคำนวณได้? ฉันสนใจวิธีพิสูจน์สิ่งนี้ด้วย
คำตอบ
ลอการิทึมที่ซ้อนกันไม่ได้ทำอะไรมากที่นี่ เป็นฟังก์ชันที่คำนวณได้โดยมีผกผันที่คำนวณได้ดังนั้นฟังก์ชัน$n \mapsto x_n$ และ $f$ ไม่เพียง แต่เทียบเท่ากับทัวริงเท่านั้น แต่เกี่ยวข้องกับการปรับขนาดที่คำนวณได้
ด้วยเหตุนี้คำตอบสำหรับคำถามนี้ก็นำไปใช้ที่นี่เช่นกัน
เราค่อนข้างแน่นอนสามารถตั้งค่าเครื่องทัวริงของเราในแบบที่พวกเขาไม่เคยเขียนสัญลักษณ์ที่ไม่ว่างเปล่าทั้งหมดลงในช่วงที่จะ $x_n$แปลก เราจำเป็นต้องทำการคำนวณด้านข้างเพื่อหาช่วงที่ยอมรับได้ แต่ด้วยขนาดของช่วงที่ฉันคาดหวังว่าสัญลักษณ์ที่เราต้องใช้ในการกำหนดช่วงเวลาถัดไปที่เราสามารถใช้ได้จะไม่นำเราออกจากช่วงเวลาในที่สุด
ในทางกลับกันสำหรับการตั้งค่าที่เป็นธรรมชาติฉันไม่เห็นเหตุผลว่าทำไม $F$จะสามารถคำนวณได้ แต่จริงๆแล้วการพิสูจน์สิ่งนี้สำหรับการตั้งค่าเฉพาะจะต้องใช้ความคิดมากเกี่ยวกับรายละเอียดของเครื่องทัวริงรุ่นใดรุ่นหนึ่งมากกว่าที่ฉันต้องการจะทำ