BB(3, 3) นั้นยาก

 (sligocki.com)
1 คะแนน โดย GN⁺ 2023-10-19 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • บทความนี้กล่าวถึงเครื่องทัวริง 3 สถานะ 3 สัญลักษณ์ที่ไม่สามารถพิสูจน์ได้ว่าหยุดทำงานหรือไม่ หากยังไม่สามารถแก้ปัญหาที่คล้ายกับ Collatz ได้ และด้วยเหตุนี้จึงกล่าวว่าปัญหา BB(3,3) ยากพอ ๆ กับการแก้ปัญหาแบบ Collatz นี้
  • ผู้เขียนกล่าวถึงตระกูลของเครื่องทัวริง (TM) ที่การพิสูจน์ว่าเกิด "quasihalt" หรือไม่นั้น ต้องอาศัยการจำลองอย่างมีประสิทธิภาพหรือการแก้ปัญหาที่คล้ายกับ Collatz อย่างสมบูรณ์
  • ผู้เขียนนำตัวอย่างมาจากเกม Busy Beaver แบบทั่วไป และค้นพบ TM จำนวนมากที่ให้ผลลัพธ์ต่อเกม Busy Beaver
  • ผู้เขียนแนะนำ TM ชื่อ "Bigfoot" ซึ่งเป็นหนึ่งใน 160 ตัวต้านทาน BB(3,3) แบบไม่เป็นทางการที่ยังเหลืออยู่
  • พฤติกรรมของ Bigfoot ถูกอธิบายว่าเป็นการวนใช้ฟังก์ชันคล้าย Collatz กับ b และ c ขณะที่ a ทำหน้าที่เก็บผลรวมสะสม
  • ผู้เขียนใชัทฤษฎีมาร์คอฟเชนเพื่ออธิบายพฤติกรรมของ Bigfoot และสรุปว่า Bigfoot "probviously" จะไม่มีวันหยุดทำงาน
  • ผู้เขียนเสนอว่าเราอาศัยอยู่ในหนึ่งในสองโลก: โลกที่ Bigfoot หยุดทำงาน หรือโลกที่มันรันไปตลอดกาล และเขาเชื่อว่าเราอยู่ในโลกแบบที่สอง
  • ผู้เขียนเสนอให้เรียกเครื่องประเภทนี้ว่า "Cryptids" โดยอุปมาจากสิ่งมีชีวิตในตำนานอย่าง Loch Ness Monster หรือ Chupacabra
  • ผู้เขียนเชิญชวนให้เสนอไอเดียเกี่ยวกับวิธีโจมตีปัญหานี้ และแสดงความหวังว่ายังอาจพิสูจน์ BB(3,3) ได้
  • ผู้เขียนสรุปว่าจากประสบการณ์ของเขา คำถามเกี่ยวกับปัญหาคล้าย Collatz มีอยู่ค่อนข้างเพียงสองประเภท: แบบที่พิสูจน์ได้ค่อนข้างง่าย และแบบที่แม้แต่นักคณิตศาสตร์ก็ยังไม่รู้วิธีพิสูจน์

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-10-19
ความเห็นจาก Hacker News
  • การอภิปรายเกี่ยวกับความซับซ้อนของ BB(3, 3) ซึ่งเป็นที่รู้จักว่าเป็นปัญหาประเภท Collatz แต่มีข้อโต้แย้งว่าอาจไม่จำเป็นต้องยากเสมอไป เพราะต้องพิจารณาเพียงพฤติกรรมที่มีอคติและวิถีเดียวเท่านั้น
  • การอภิปรายเกี่ยวกับเครื่องทัวริงที่มี 748 สถานะ ซึ่งจะหยุดทำงานหาก ZFC (ทฤษฎีเซต Zermelo-Fraenkel พร้อมสัจพจน์การเลือก) ไม่สอดคล้องกัน พร้อมแสดงความสับสนเกี่ยวกับนัยของการรันเครื่องนี้เป็นเวลา BB(748) ขั้น และความเป็นไปได้ที่จะขัดแย้งกับทฤษฎีบทความไม่สมบูรณ์ข้อที่สองของ Gödel
  • ชื่นชมว่าสไตล์การเขียนของผู้เขียนชัดเจนและกระชับ ช่วยให้ผู้อ่านเข้าใจหัวข้อได้โดยไม่เยิ่นเย้อ
  • ตั้งคำถามว่าการที่ BB (Busy Beaver) คำนวณไม่ได้หมายความว่าอย่างไร และเมื่อ BB เติบโตขึ้นจะต้องพิสูจน์ทุกสิ่งหรือไม่
  • เสนอว่าปัญหา BB(x, y) ทุกปัญหาสามารถลดรูปเป็นปัญหาแบบ Collatz ได้ ดังนั้นการหา BB(x, y) สำหรับค่า x และ y ใด ๆ ก็อาจลดรูปเป็นปัญหาแบบ Collatz ได้เช่นกัน
  • ตั้งคำถามว่าทำไม Beeping Busy Beavers (BBB) จึงสามารถกึ่ง-หยุดได้ก่อนที่จะรันนานกว่านี้มาก โดยมีข้อเสนอว่าอาจเป็นเพราะไม่จำเป็นต้องใช้สถานะหยุด
  • สงสัยถึงผลกระทบของปัญหาการหยุดทำงานต่อการอุปนัยในโลกจริง โดยยกสถานการณ์สมมุติที่มีออราเคิลซึ่งสามารถตัดสินได้ว่าเครื่องทัวริงที่กำหนดจะพิมพ์สิ่งอื่นลงบนเทปเอาต์พุตหรือไม่
  • ถามถึงความรู้พื้นฐานที่จำเป็นในการทำความเข้าใจหัวข้อเหล่านี้ และขอคำแนะนำเกี่ยวกับหัวข้อหรือวิชาที่จะช่วยปูพื้นฐานได้ดี
  • ถามว่าควรอ่านสตริง 1RB2RA1LC_2LC1RB2RB_---2LA1LA อย่างไร