ทำไม BB(3, 3) จึงยาก: Bigfoot
(sligocki.com)- เครื่องทัวริง 3 สถานะ 3 สัญลักษณ์ Bigfoot เป็นกรณีที่การพิสูจน์ว่าจะหยุดหรือไม่บนเทปว่างจำเป็นต้องแก้ปัญหาคล้าย Collatz แสดงให้เห็นว่า (BB(3, 3)) อาจยากในระดับเดียวกัน
- เครื่องนี้เป็นหนึ่งในผู้สมัครที่ยังไม่คลี่คลาย 160 รายการของ (BB(3, 3)) บน bbchallenge.org และนิยามด้วยตารางทรานซิชัน
1RB2RA1LC_2LC1RB2RB_---2LA1LA - พฤติกรรมถูกลดรูปเป็นกฎการวนซ้ำของคอนฟิกูเรชัน (A(a,b,c)) โดยขึ้นกับ (b \bmod 6) แล้ว a จะเพิ่มหรือลด และจะหยุดเฉพาะเมื่อ (a) กำลังจะลดต่ำกว่า 0
- จากเทปว่าง หลังผ่านไป 69 ขั้นจะถึง (A(2,1,2)) และหลังวนซ้ำ 24 ล้านครั้ง (a) โตถึง (3,999,888) ทำให้ในเชิงทดลองดูเหมือนมีโอกาสหยุดต่ำมาก
- ลำดับ (b \bmod 6) เป็นแบบกำหนดแน่นอน แต่ในภาพรวมดูเหมือน random walk แบบมีอคติที่ไปทางขวา 2/3 และซ้าย 1/3; หากต้องการพิสูจน์ว่ามันรันตลอดไป ต้องแสดงว่าฟังก์ชันคล้าย Collatz นี้ไม่เคยไปถึงทรานซิชันที่หยุด
เหตุผลที่ Bigfoot ทำให้ (BB(3, 3)) ยาก
- การพิสูจน์ การหยุดหรือไม่หยุด ของเครื่องทัวริง 3 สถานะ 3 สัญลักษณ์เพียงเครื่องเดียว จำเป็นต้องแก้ปัญหาคล้าย Collatz
- ดังนั้นการแก้ปัญหา (BB(3, 3)) อาจยากพอ ๆ กับการแก้ปัญหาคล้าย Collatz นี้
- Paul Erdős เคยกล่าวถึงปัญหาตระกูล Collatz ว่า “Mathematics may not be ready for such problems”
- บทความก่อนหน้า Mother of Giants กล่าวถึงตระกูลเครื่องทัวริงที่พบจากการค้นหา “Beeping” Busy Beaver
- ตระกูลดังกล่าวต้องจำลองปัญหาคล้าย Collatz อย่างมีประสิทธิภาพหรือแก้ให้สมบูรณ์ เพื่อพิสูจน์ว่าจะเข้าสู่สถานะคล้ายหยุด (quasihalt) หรือไม่
- Bigfoot เป็นกรณีที่พบในเกม Busy Beaver ปกติ ไม่ใช่เกมแบบดัดแปลง
กรณีความยากเดิมของ Busy Beaver
- เครื่องทัวริงหลายเครื่องที่มนุษย์สร้างขึ้นเองให้ตัวอย่างว่า หากต้องพิสูจน์ค่า Busy Beaver บางค่า ก็ต้องพิสูจน์ประพจน์คณิตศาสตร์ยากอื่น ๆ
- (BB(745)): ต้องพิสูจน์ความสอดคล้องของ ZFC
- (BB(27)): ต้องพิสูจน์ Goldbach Conjecture
- (BB(15)) และ (BB(5,4)): ต้องพิสูจน์ข้อคาดการณ์ของ Erdős ที่ว่าเมื่อ (n > 8) การแทน (2^n) ในฐานสามมีเลข 2 อย่างน้อยหนึ่งตัว
- อย่างไรก็ดี ค่า Busy Beaver เหล่านี้อยู่นอกขอบเขตที่เข้าถึงได้ในปัจจุบัน
- ในช่วง 60 ปีที่ผ่านมา ค่าที่พิสูจน์ได้มีเพียง (BB(2), BB(3), BB(4), BB(2,3)) และเป็นที่รู้ว่า (BB(6) > 10 \uparrow\uparrow 15)
- ก่อนวิเคราะห์ Bigfoot เคยเชื่อกันว่ายังมีความเป็นไปได้ที่จะพิสูจน์ (BB(3, 3))
นิยามและที่มาของ Bigfoot
- เครื่องทัวริงนี้มีชื่อว่า Bigfoot และนิยามตารางทรานซิชันด้วยสตริงต่อไปนี้
1RB2RA1LC_2LC1RB2RB_---2LA1LA
- เป็นเครื่องที่ลงทะเบียนบน bbchallenge
- ตารางทรานซิชันมีดังนี้
| สถานะ | 0 | 1 | 2 |
|---|---|---|---|
| A | 1RB | 2RA | 1LC |
| B | 2LC | 1RB | 2RB |
| C | — | 2LA | 1LA |
- Bigfoot เป็นหนึ่งใน holdout ไม่เป็นทางการที่เหลืออยู่ 160 รายการของ (BB(3,3)) ซึ่งแชร์ในช่อง Discord ของ bbchallenge.org
- เครื่องทัวริงเครื่องนี้ถูก @savask แชร์ครั้งแรกในช่อง Discord เดียวกันเมื่อวันที่ 14 ตุลาคม 2023 พร้อมคำอธิบายพฤติกรรมระดับต่ำ
- การวิเคราะห์ภายหลังเผยให้เห็น โครงสร้างคล้าย Collatz และลักษณะของ random walk แบบมีอคติ
พฤติกรรมที่ลดรูปเป็นคอนฟิกูเรชัน (A(a,b,c))
- ให้คอนฟิกูเรชันทั่วไปเป็นดังนี้
[ A(a, b, c) = 0^\infty ; 12^a ; 11^b ; \text{ <A } ; 11^c ; 0^\infty ]
- เมื่อ Bigfoot เข้าสู่คอนฟิกูเรชัน (A(a,b,c)) ที่ (c \ge 1) กฎต่อไปนี้จะอธิบายพฤติกรรมหลังจากนั้นได้อย่างแม่นยำจนกว่าจะหยุดหรือดำเนินต่อไปตลอดกาล
[ \begin{array}{l} A(a, 6k, c) \to A(a, 8k+c-1, 2) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+1, c) \to A(a+1, 8k+c-1, 3) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+2, c) \to A(a-1, 8k+c+3, 2) \quad \text{if } a \ge 1 \ A(a, 6k+3, c) \to A(a, 8k+c+1, 5) \ A(a, 6k+4, c) \to A(a+1, 8k+c+3, 2) \ A(a, 6k+5, c) \to A(a, 8k+c+5, 3) \end{array} ]
[ A(0, 6k+2, c) \to \text{Halt}(16k+2c+7) ]
- กฎเหล่านี้วนซ้ำ ฟังก์ชันคล้าย Collatz สำหรับพารามิเตอร์ (b) และ (c)
- (a) เคลื่อนที่เหมือนค่สะสม
- ถ้า (b \equiv 1 \pmod{6}) หรือ (b \equiv 4 \pmod{6}) แล้ว (a) จะเพิ่มขึ้น
- ถ้า (b \equiv 2 \pmod{6}) แล้ว (a) จะลดลง
- Bigfoot จะหยุดเฉพาะเมื่อ (a) กำลังจะลดต่ำกว่า 0
เส้นทางที่สังเกตจากเทปว่าง
- เมื่อเริ่มจากเทปว่าง Bigfoot จะถึงคอนฟิกูเรชัน (A(2,1,2)) หลังผ่านไป 69 ขั้น
- จากการจำลองหลังจากนั้น (a) ดูเหมือนเพิ่มขึ้นอย่างต่อเนื่อง และหลังวนซ้ำ 24 ล้านครั้ง (a = 3,999,888)
- หากสมมติว่าลำดับเศษเหลือของ (b \bmod 6) เป็นสุ่มแบบสม่ำเสมอ กระบวนการนี้จะเทียบได้กับ random walk แบบมีอคติ บนเส้นจำนวน
- ในแต่ละขั้น ความน่าจะเป็นที่จะไปทางขวาคือ (\frac{2}{3})
- ความน่าจะเป็นที่จะไปทางซ้ายคือ (\frac{1}{3})
- ในทฤษฎี Markov chain สามารถพิสูจน์ได้ว่า เมื่ออยู่ที่ตำแหน่งปัจจุบัน (a=n) ความน่าจะเป็นที่ในอนาคตจะไปถึง (a=-1) คือ ((\frac{1}{2})^{n+1})
- ลำดับ (b \bmod 6) จริงไม่ได้เป็นสุ่ม แต่กำหนดแน่นอนทั้งหมด และทำตามรูปแบบคี่·คี่·คู่·คู่อย่างสม่ำเสมอ
- ถึงอย่างนั้น ในระดับใหญ่ก็แสดงเส้นทางคล้ายกับ random Markov chain
- หลัง 24 ล้านขั้น Markov chain คาดว่าจะเคลื่อนที่ไปทางขวา 8 ล้านครั้ง และไปทางซ้าย 4 ล้านครั้ง
- ซึ่งใกล้กับค่า (a) จริงราว 4 ล้านมาก
ฮิวริสติกที่ว่า “probviously” ไม่หยุด
- เมื่อ (a \approx 4,000,000) ความน่าจะเป็นที่ random Markov chain จะไปถึง (a=-1) อยู่ที่ประมาณ ((\frac{1}{2})^{4,000,000})
- ตัวเลขนี้เล็กจนในเชิงวิทยาศาสตร์ถือได้แทบเหมือนรับประกันความล้มเหลว
- หาก Bigfoot ทำงานคล้าย Markov chain ก็ดูเหมือนว่า จะไม่หยุด
- แต่นี่เป็นฮิวริสติกเชิงทดลอง ไม่ใช่ประพจน์คณิตศาสตร์ที่เข้มงวด
- ยังไม่อาจตัดความเป็นไปได้ที่ Bigfoot จะหยุดหลังวนซ้ำ googolplex ครั้งได้
- John Conway สร้างคำนี้ขึ้นเพื่ออธิบายฮิวริสติกที่ว่า conjecture ของ Collatz น่าจะจริงแบบ “probviously” แต่ก็ยังไม่เห็นบทพิสูจน์ของ Collatz
จุดจบสองแบบที่ Bigfoot อาจมี
- Bigfoot เป็นอย่างใดอย่างหนึ่งต่อไปนี้
- หยุด
- รันตลอดไป
- ถ้ามันหยุด สามารถพิสูจน์ได้ด้วยการเร่งการวนซ้ำของฟังก์ชันคล้าย Collatz ให้มากพอ แล้วจำลองจนถึงจุดจบ
- ถ้ามันรันตลอดไป ต้องพิสูจน์ว่าฟังก์ชันคล้าย Collatz นี้ไม่เคยไปถึงทรานซิชันหยุดที่ (a=0)
- ตามฮิวริสติกของ Markov chain กรณีที่สองดูเป็นไปได้มากกว่า และดูพิสูจน์ยากกว่ามาก
ชื่อ Cryptids
- เครื่องประเภทนี้สามารถลดรูปพฤติกรรมเป็นกฎคณิตศาสตร์ที่ค่อนข้างเรียบง่ายได้ แต่กฎนั้นอยู่ในกลุ่มปัญหาคณิตศาสตร์เปิด
- คล้ายสิ่งมีชีวิตในตำนานที่มีเพียงข่าวลือว่าหยุดหรือไม่หยุด แต่ไม่มีฝ่ายใดแสดงหลักฐานเป็นรูปธรรมได้
- จึงมีข้อเสนอให้เรียกเครื่องเหล่านี้ว่า Cryptids
- เป็นการเปรียบเทียบกับสิ่งมีชีวิตในตำนานอย่าง Loch Ness Monster หรือ Chupacabra
- เครื่องทัวริงนี้ได้ชื่อว่า Bigfoot เพราะดูเหมือนเดินแบบสุ่ม
พฤติกรรมคล้าย Collatz นี้ยากจริงหรือไม่
- พลวัตของฟังก์ชันคล้าย Collatz เฉพาะนี้ดูเหมือนเป็นปัญหาที่แทบไม่เคยถูกวิเคราะห์มาก่อน
- ยังมีความเป็นไปได้ที่จะใช้ทฤษฎีจำนวนและการคำนวณเล็กน้อย เพื่อค้นหาคุณสมบัติทางคณิตศาสตร์ที่ชาญฉลาดและใช้ได้กับปัญหานี้โดยเฉพาะ
- หากพบคุณสมบัติดังกล่าว ก็จะรู้ว่า การพิสูจน์ (BB(3,3)) ยังอยู่ในขอบเขตที่เข้าถึงได้
- คำถามที่ถามได้ในปัญหาคล้าย Collatz แบ่งตามประสบการณ์ออกเป็นสองประเภท
- คำถามที่พิสูจน์ได้ค่อนข้างง่าย
- คำถามที่นักคณิตศาสตร์คนใดก็ยังไม่รู้วิธีพิสูจน์
- ข้อเท็จจริงที่ว่าใน Bigfoot (b) ทำซ้ำรูปแบบคี่·คี่·คู่·คู่ หรือข้อเท็จจริงที่ว่าหลังใช้กฎ Collatz แบบดั้งเดิม (3n+1) แล้วจะเป็นจำนวนคู่เสมอและถูกหารด้วย 2 ในขั้นถัดไป อยู่ในประเภทแรก
- คำถามอื่นแทบทั้งหมดเกี่ยวกับพฤติกรรมของระบบ Collatz ถือเป็นตัวอย่างในประเภทที่สองได้
การแสดงแบบทางเลือกที่มี 81 กรณี
- การแสดงแบบทางเลือกที่เพิ่มเมื่อวันที่ 18 ตุลาคม 2023 ช่วยลดความไม่สะดวกของคำอธิบาย (A(a,b,c)) เดิม
- คำอธิบายเดิมมีความไม่สะดวกสามอย่าง
- พารามิเตอร์ (b) และ (c) พัวพันกัน
- โมดูโลอินพุต 6 และโมดูโลเอาต์พุต 8 มีตัวประกอบร่วมคือ 2
- (b) ทำตามรูปแบบซ้ำคี่·คี่·คู่·คู่
- Matthew House ชี้ว่า หากนิยามคอนฟิกูเรชันใหม่ดังนี้จะหลีกเลี่ยงปัญหาเหล่านี้ได้
[ B(a,b)=A(a,2b+1,2) ]
- เมื่อตั้ง (b=81k+r) และรวมทรานซิชันเดิม 4 ครั้งเป็นทรานซิชันเดียว จะสามารถแสดงพฤติกรรมคล้าย Collatz ของ Bigfoot เป็นกฎที่มี 81 กรณี
- การแสดงนี้แก้คุณลักษณะสามอย่างของการแสดง (A) เดิม และดูคล้ายปัญหา Collatz แบบคลาสสิกมากขึ้น
- อย่างไรก็ตาม ต้องจัดการกรณีทั้งหมด 81 กรณี จึงค่อนข้างเทอะทะ
- กฎบางข้อขึ้นกับเงื่อนไข (a \ge 2)
1 ความคิดเห็น
ความคิดเห็นบน Hacker News
แทนที่จะบอกว่า BB(3, 3) เองยาก น่าจะพูดให้ถูกกว่าว่ามันกำลัง encode ปัญหาประเภท Collatz และปัญหาแบบนั้นโดยทั่วไปถือว่ายากมาก
แต่กรณีเฉพาะนี้จะยากจริงหรือไม่ก็เป็นอีกเรื่องหนึ่ง เพราะพฤติกรรมดูเอนเอียงไปด้านหนึ่งพอสมควร และไม่ใช่ว่าต้องดูวิถีของจำนวนเต็มทั้งหมดเหมือนปัญหา Collatz แบบคลาสสิก แต่ต้องดูเพียง วิถีเดียว เท่านั้น
ประเด็นเรื่องวิถีเดียวเทียบกับหลายวิถีก็เห็นด้วยในระดับหนึ่ง อย่างไรก็ตาม หากสมมติว่า Turing machine นี้อยู่ในโลกที่ไม่หยุด การพิสูจน์วิถีเดียวของระบบนี้อาจถือว่า “ยากกว่า” วิถีเดียวของข้อคาดการณ์ Collatz แบบคลาสสิกได้ ถ้าข้อคาดการณ์ Collatz เป็นจริง การพิสูจน์วิถีเดี่ยวใด ๆ สุดท้ายก็เป็นเพียงการคำนวณจำกัดจำนวนขั้น แต่ในวิถีเดียวของบทความนี้ ต้องแสดงว่ามัน จะไม่หยุดตลอดไป จึงต้องใช้คณิตศาสตร์ที่ประณีตกว่า
ไม่ได้อยากพูดเกินจริง นี่ไม่ได้หมายความว่าการจะแก้ BB(3, 3) จะต้องพิสูจน์ข้อคาดการณ์ Collatz หรือปัญหาเปิดทางคณิตศาสตร์ที่มีการศึกษากันดีอยู่แล้วเสมอไป แต่ก็ยังคิดว่ามีความหมายในฐานะผลลัพธ์ “รองลงมา” ว่าเป็นปัญหายากที่คล้ายกับปัญหาที่มีการศึกษากันดี ส่วนปัญหาคล้าย Collatz นี้ยากแค่ไหน ก็คงต้องดูว่าใครจะสามารถแก้มันได้
อยากช่วยทำความเข้าใจตรงนี้ มี Turing machine ขนาด 748 สถานะอยู่ [0] และเข้าใจว่าเครื่องนี้จะหยุด ก็ต่อเมื่อ ZFC ขัดแย้งในตัวเองเท่านั้น
เครื่องนี้เป็นวัตถุ “ทางกายภาพ” ที่สามารถ implement และรันบนคอมพิวเตอร์ได้ แม้พลังคำนวณปัจจุบันจะไม่พอ แต่โดยหลักการแล้วไม่มีอะไรขวางไม่ให้เรารันเครื่องนี้เป็นเวลา BB(748) ขั้น ถ้ามันหยุด ก็เป็นการพิสูจน์ตามทฤษฎีบท 1 ว่า ZFC ขัดแย้งในตัวเอง และถ้ามันไม่หยุด ก็ดูเหมือนเป็นการพิสูจน์ว่า ZFC สอดคล้องกัน
นี่คือแก่นของความสับสน มันดูไม่ใช่ผลลัพธ์เชิงนามธรรม แต่เหมือนการคำนวณที่ทำจริงและได้ค่าออกมาได้
แน่นอน ตามทฤษฎีบทความไม่สมบูรณ์ข้อที่สองของ Gödel ภายใน ZFC ไม่สามารถพิสูจน์ความสอดคล้องของ ZFC เองได้ แต่ถ้า Turing machine ข้างต้นหยุด ก็จะกลายเป็นการพิสูจน์ว่า ZFC สอดคล้องกัน ซึ่งดูเหมือนขัดแย้งกัน
ตรงไหนที่ผิด? ตอนนี้เดาว่าในการพิสูจน์ทฤษฎีบท 1 ใช้ เมตาทฤษฎี ที่แข็งแรงกว่า ZFC เพื่อแสดงว่า Turing machine 748 สถานะนี้จะหยุดก็ต่อเมื่อ ZFC ขัดแย้งในตัวเองเท่านั้น ถ้าเป็นแบบนั้นก็ไม่ขัดแย้งกัน ต่อให้รันได้เป็นเวลา BB(748) ขั้น นั่นก็เพียงแสดงว่า ZFC+ พิสูจน์ความสอดคล้องของ ZFC ได้ ซึ่งเป็นเรื่องที่รู้กันอยู่แล้ว ตัวอย่างเช่น ZFC + “มี inaccessible cardinal อยู่” ก็ทำหน้าที่แบบนั้น
ยังไม่ได้อ่าน论文ละเอียด เลยไม่รู้ว่าจริง ๆ เป็นแบบนั้นไหม มีใครที่เคยคิดเรื่องนี้ลึก ๆ พอจะให้ insight ได้บ้างไหม?
[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
ถ้าเทพแห่ง busy beaver บอกค่านั้นให้เรา ในเชิงทฤษฎีก็สามารถรัน Turing machine ได้นานเท่านั้น และพิสูจน์ได้ตามที่บอกว่า ZFC สอดคล้องหรือไม่ แต่ถ้ามนุษย์จะคำนวณ BB(748) จริง ๆ ก็แทบจะต้องรู้ว่า Turing machine 748 สถานะตัวเฉพาะนี้จะหยุดในสักวันหรือไม่ และ Turing machine 748 สถานะตัวอื่นทั้งหมดที่หยุดได้จะหยุดหรือไม่ด้วย
แม้จะใช้สสารและพลังงานทั้งหมดของเอกภพสร้างคอมพิวเตอร์ และให้คอมพิวเตอร์นั้นทำงานนี้เพียงงานเดียวด้วยประสิทธิภาพสูงสุดที่เป็นไปได้ทางฟิสิกส์ ก็ยังคำนวณไม่เสร็จ
นั่นจึงเป็นจุดที่คณิตศาสตร์แยกออกจากฟิสิกส์และความเป็นจริง เราสามารถพูดถึงและให้เหตุผลเกี่ยวกับวัตถุแบบนั้นได้ แต่มันไม่มี ความหมายทางกายภาพ อีกต่อไป
แต่การพิสูจน์ว่ามันไม่หยุดนั้นยากกว่ามาก ต่อให้รันไปถึง TREE(3) ขั้น ก็ไม่ได้เป็นการพิสูจน์ว่ามันจะไม่หยุดที่ขั้น TREE(3)+1
เพราะฉะนั้นน่าเศร้าที่พูดว่า “ก็แค่รันไปสิ” ไม่ได้
ชอบสไตล์การเขียนของผู้เขียน ดูไม่เยิ่นเย้อ แต่ช่วยให้เข้าใจหัวข้อได้ และการหาจุด สมดุล แบบนั้นไม่ใช่เรื่องง่าย
แหล่งข้อมูลที่เกี่ยวข้อง: https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.... และ https://googology.fandom.com/wiki/Googology_Wiki
ที่บอกว่า BB คำนวณไม่ได้ หมายถึงแบบนี้หรือเปล่า? พอ BB ใหญ่ขึ้น มันก็โอบรับ คณิตศาสตร์ทั้งหมด เข้าไป และสุดท้ายหมายความว่าต้องพิสูจน์ทุกอย่างให้ได้หรือเปล่า
คณิตศาสตร์ส่วนที่เหลือทั้งหมดถูกลักลอบยัดเข้ามาใน BB ผ่านปัญหาการหยุดทำงาน เราสามารถเขียนโปรแกรมที่หยุดก็ต่อเมื่อข้อคาดเดาทางคณิตศาสตร์ใด ๆ เป็นจริงหรือเป็นเท็จได้ ดังนั้นการพยายามแก้ปัญหาการหยุดทำงานหรือ BB ก็คือต้องรู้คณิตศาสตร์ทั้งหมด[0] สิ่งนี้เป็นไปได้เพราะความเป็นทัวริงสมบูรณ์คือเส้นแบ่งของความสามารถในการคำนวณ สิ่งใดที่บรรจุคอมพิวเตอร์ไว้ได้ สิ่งนั้นเองก็คือคอมพิวเตอร์
[0] จริง ๆ แล้วตัวเรื่องนี้เองไม่ใช่เหตุผลที่ทำให้การหยุดทำงานตัดสินไม่ได้ ความตัดสินไม่ได้มาจากการที่โปรแกรม “ดึงตัวเองเข้าไปในปัญหาการหยุดทำงาน” เช่น ตัวตัดสินการหยุดทำงานสมมติที่หยุดเฉพาะเมื่อมันบอกว่าตัวเองจะไม่หยุด
มีปัญหาคณิตศาสตร์บางอย่างที่เรา “รู้” ว่าเราไม่สามารถพิสูจน์หรือหักล้างได้ ถ้าไม่ใช่กรณีที่ทุกประพจน์สามารถพิสูจน์ได้ทั้งว่าเป็นจริงและเป็นเท็จ นั่นคือ ทฤษฎีบทความไม่สมบูรณ์ข้อที่หนึ่งของ Gödel ถ้าทุกประพจน์พิสูจน์ได้ทั้งจริงและเท็จ ระบบพิสูจน์นั้นก็ไร้ประโยชน์ และการพิสูจน์ก็ไม่มีความหมายอะไร จึงต้องเลือกระบบพิสูจน์อื่นที่ไม่เกิดเรื่องแบบนั้น ดังนั้นโดยทั่วไปจึงสมมติกรณีแรก คือมีปัญหาที่พิสูจน์ก็ไม่ได้ หักล้างก็ไม่ได้ อนึ่ง ทฤษฎีบทความไม่สมบูรณ์ข้อที่สองของ Gödel กล่าวไว้ว่า เราไม่มีทางพิสูจน์ได้เลยว่าเราอยู่ในกรณีแรกนั้นเอง
และการที่ BB คำนวณไม่ได้หมายความว่า เมื่อ BB ใหญ่ขึ้น สักวันหนึ่งมันจะสามารถเข้ารหัสโปรแกรมที่หยุดก็ต่อเมื่อปัญหาที่พิสูจน์ก็ไม่ได้ หักล้างก็ไม่ได้นั้นเป็นจริง ดังนั้นจึงพิสูจน์ไม่ได้ว่าโปรแกรมนั้นหยุดหรือไม่หยุด
พูดอย่างเคร่งครัด การพิสูจน์หรือหักล้างสิ่งที่พิสูจน์ก็ไม่ได้ หักล้างก็ไม่ได้ เท่ากับเป็นการพิสูจน์สิ่งเท็จ และสุดท้ายสามารถนำไปใช้ “พิสูจน์” ทุกประพจน์ได้ ดังนั้นคำว่า “ครอบคลุมคณิตศาสตร์ทั้งหมด” จึงถูกในความหมายหนึ่ง อย่างไรก็ตาม นี่เป็นเงื่อนไขวิกฤต และมันทำงานนานก่อนที่จะมีเครื่องทัวริงที่ใหญ่พอจะเข้ารหัสปัญหาคณิตศาสตร์ “ทุก” ข้อได้จริง ๆ อันที่จริงไม่มีจำนวนสถานะจำกัดใดที่เพียงพอสำหรับการเข้ารหัสปัญหาคณิตศาสตร์ทั้งหมด เพราะเราสามารถทำให้สตริงเชิงเลขคณิตยาวขึ้นไปเรื่อย ๆ ได้
จากนั้นก็ไม่น่าแปลกใจแล้วที่มี BB บางตัวที่เราแก้ไม่ได้ และสิ่งที่น่าสนใจก็คือการสำรวจว่า BB ตัวไหนแก้ได้ และตัวไหนแก้ไม่ได้
ไม่เข้าใจว่าทำไมส่วนที่ว่า “ดังนั้นการแก้ปัญหา BB(3, 3) อย่างน้อยก็ยากเท่ากับการแก้ปัญหาคล้าย Collatz นี้” ถึงน่าประหลาดใจ จริง ๆ แล้วดูเหมือนพิสูจน์ได้แทบจะชัดเจนอยู่แล้ว ไม่ใช่ว่าปัญหา BB(x, y) ทุกอันลดรูปเป็น ปัญหาประเภท Collatz ได้หรือ?
BB(x, y) แปลงเป็นปัญหาการหยุดทำงานได้ง่ายมาก หาเครื่องทั้งหมดที่หยุดในบรรดาเครื่องที่มี x สถานะและ y สัญลักษณ์ แล้วแยกเครื่องที่ไม่หยุดไว้ต่างหาก จากนั้นรันเครื่องที่หยุดทั้งหมดไปพร้อมกันทีละขั้นจนทุกเครื่องหยุด จำนวนขั้นตอนที่รันก็คือค่า BB(x, y)
เท่าที่รู้ Conway เสนอวิธีลดรูปปัญหาการหยุดทำงานเป็นปัญหาประเภท Collatz ไว้แล้ว ถ้าอย่างนั้น ด้วยการลดรูปสองขั้นจาก BB ไปเป็นปัญหาการหยุดทำงาน แล้วจากนั้นไปเป็นปัญหา Collatz ก็ดูเหมือนจะลด BB(x, y) สำหรับ x, y ใด ๆ ให้เป็นปัญหาประเภท Collatz ได้
สิ่งที่ต้องการคือการลดรูปจาก Collatz ไปเป็นปัญหาการหยุดทำงาน แล้วต่อไปเป็น B(x,y) การไปจาก Collatz เป็นปัญหาการหยุดทำงานนั้นชัดเจน แต่จากปัญหาการหยุดทำงานไปเป็น B(x,y) นั้นไม่ชัดเท่าไร ต้องนิยามให้ชัดว่าสับเซตของปัญหาการหยุดทำงานที่สามารถลดรูปมาจาก Collatz และไม่ยากกว่า B(3,3) คืออะไร
ปัญหาการหยุดทำงานดูเหมือนจะ “ขัดขวาง” แนวทางจำนวนมากของ ทฤษฎีสารสนเทศเชิงอัลกอริทึม และการอนุมานที่ตั้งอยู่บนโปรแกรมที่คำนวณได้อยู่บ่อย ๆ แต่สงสัยว่ามีงานวิจัยไหมว่าปัญหาการหยุดทำงานส่งผลเชิงวัตถุต่อความสามารถในการอนุมานในโลกจริงหรือไม่
ตัวอย่างเช่น สมมติว่ามีโอราเคิลที่บอกให้รู้ว่าเครื่องทัวริงสากลแบบโมโนโทนใด ๆ มาถึงจุดที่ระหว่างการทำงานจะไม่เขียนอะไรลงบนเทปเอาต์พุตอีกต่อไปแล้วหรือยัง ผลลัพธ์ของการอนุมานที่ใช้โอราเคิลนี้จะแตกต่างมากไหมจากวิธีที่ไล่ค้นพื้นที่โปรแกรมแบบสมบูรณ์ แล้วถ้าโปรแกรมใดไม่สร้างเอาต์พุตเป็นเวลานานพอ เช่น n ขั้นตอน ก็แค่ “ข้าม” ไปโปรแกรมถัดไป
หมายถึงการอนุมานกับข้อมูลที่บีบอัดได้แบบ “ธรรมดา” ไม่ใช่กรณีขอบที่ตั้งใจสร้างขึ้นอย่าง BB(3,3) หรือตัวอย่างเชิงปฏิปักษ์
ในฐานะนักวิจัยด้านความปลอดภัย ผมเขียน fuzzer เองโดยตรง fuzzer คือเครื่องมือที่ค้นหาอินพุตที่มีนัยสำคัญด้านความปลอดภัยให้กับโปรแกรมที่ถูกทดสอบโดยอัตโนมัติ มันสร้างและดัดแปลงอินพุตเชิงอัลกอริทึม ป้อนเข้าโปรแกรม แล้วสังเกตว่าเกิดอะไรขึ้นนับสิบ นับร้อย หรือนับพันครั้งต่อวินาที
ถ้าอินพุตบางอย่างทำให้โปรแกรมแครช ก็อาจมองได้ว่ามันทำให้โปรแกรม “หยุด” การจะสร้าง fuzzer ที่ค้นหาบั๊กทั้งหมดของโปรแกรมใด ๆ ได้ภายในเวลาที่สมจริง ดูเหมือนว่าจะต้องแก้ปัญหาการหยุดทำงานให้ได้ ในทางปฏิบัติ แม้ทดสอบไปหลายพันล้านครั้งแล้ว ก็ยังมีคนพบบั๊กใน image decoder อยู่ ดังนั้น fuzzer ที่เรามีจึงไม่สมบูรณ์จริง ๆ
ขณะเดียวกัน ในโลกจริงผมก็เห็นว่าเมื่อให้เวลาพอ fuzzer สามารถเจาะลึกเข้าไปภายในโปรแกรมซับซ้อนได้มากกว่าที่คาด การตรวจสอบอินพุตที่โปรแกรมเป้าหมายทำ รวมถึงหน่วยความจำและพื้นที่เก็บข้อมูลที่จำกัดของพีซีสมัยใหม่ ช่วยวาง fuzzer ให้อยู่บนรางได้ในระดับหนึ่ง แต่ยกเว้นเมื่อมีคริปโตกราฟีเข้ามาเกี่ยวข้อง ซึ่งสำหรับ fuzzer แล้วเหมือนบ่อโคลนเชิงคำนวณ โปรแกรมที่ป้องกันดีและระบุสเปกชัดเจนทำหน้าที่เป็นราวกั้นในตัว ทำให้ fuzzer ไม่จำเป็นต้องแก้ปัญหาการหยุดทำงาน
ดังนั้นในเรื่องการตรวจหาบั๊กความปลอดภัยของโปรแกรม ผมมองแบบนี้: ถ้าไม่นับคริปโตกราฟี fuzzer เก่งกับการเล็งไปที่โปรแกรมที่ตรวจสอบอินพุตอย่างเข้มงวด ในทางกลับกัน สำหรับโปรแกรมที่ไม่ตรวจสอบอินพุตอย่างเข้มงวด ก็ไม่จำเป็นต้องใช้ fuzzer เสียด้วยซ้ำ และในที่แบบนั้น fuzzer ก็ไม่ได้จำเป็นต้องทำงานได้ดีเสมอไป
พอจะมีสัญชาตญาณไหมว่าทำไม BBB หรือ Busy Beaver ที่ส่งเสียงบี๊บ จึงอาจรันได้นานกว่ามากก่อนจะกึ่งหยุด?
สิ่งหนึ่งที่เห็นได้คือ แทบไม่จำเป็นต้องใช้สถานะหยุดจริง ๆ ในแง่นั้น BBB แบบ 3 สถานะอาจคล้ายกับ BB แบบ 4 สถานะก็ได้ อยากรู้ว่ายังมีอย่างอื่นอีกไหม
ดังนั้นจึงทำให้โปรแกรมหรือเครื่องทัวริงขนาด X จำลองการรันโปรแกรมทุกตัวที่มีขนาด Y โดยที่ Y >> X ได้ เมื่อใดก็ตามที่โปรแกรมเหล่านั้นตัวใดตัวหนึ่งหยุด ก็ให้ส่งเสียงบี๊บ และเสียงบี๊บสุดท้ายจะเกิดขึ้นตอนจำลองโปรแกรมที่หยุดหลังผ่านไปมากกว่า BB(Y) ขั้นตอน ดังนั้นจะได้ BBB(X) > BB(Y) >> BB(X)
ถ้าจำไม่ผิด ด้วยโครงสร้างแบบเดียวกันโดยพื้นฐาน ถ้าเรารู้ BB(N) ก็จะคำนวณปัญหาการหยุดของโปรแกรมขนาดไม่เกิน N ได้แบบช้ามาก ในขณะที่ถ้าเรารู้ BBB(N) ก็จะคำนวณปัญหาการหยุดสำหรับ เครื่องทัวริงที่ได้รับ halting oracle ขนาดไม่เกินนั้นได้แบบช้ากว่านั้นมาก
เรื่องนี้เนิร์ดเกินไปสำหรับผม
สงสัยว่าต้องมีพื้นความรู้อะไรบ้างถึงจะเข้าใจเรื่องแบบนี้ แค่แคลคูลัสพื้นฐานพอไหม? หัวข้อหรือวิชาเฉพาะอะไรบ้างที่เป็นพื้นฐานที่ดี?
[1] https://www.scottaaronson.com/writings/bignumbers.html
ถ้าตามตำราเบื้องต้นของวิทยาการคอมพิวเตอร์เชิงทฤษฎีไป ส่วนใหญ่จะช่วยให้เข้าใจได้ นักศึกษาวิทยาการคอมพิวเตอร์มักเรียนกันในปี 1–2 และไม่ใช่เรื่องง่าย ที่มหาวิทยาลัยของเราเป็นหนึ่งในวิชาสอบที่น่ากลัวที่สุด
หนังสือเบื้องต้นของ Hopcroft & Ullmann ดี แต่เนื้อหาที่เกี่ยวข้องมีเยอะมาก จึงควรมองว่าเป็นเพียงจุดเริ่มต้น
หลักสูตรปริญญาตรีวิทยาการคอมพิวเตอร์หลายแห่งน่าจะมีวิชาที่เปิดสื่อการสอนไว้สาธารณะ
ควรอ่าน
1RB2RA1LC_2LC1RB2RB_---2LA1LAอย่างไร?https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
ตัวอย่างเช่น ถ้าอยู่ในสถานะ B และค่าบนเทปที่ตำแหน่งหัวอ่านปัจจุบันเป็น 0 ก็ให้เขียน 2 เลื่อนหัวอ่านไปทางซ้ายหนึ่งช่อง แล้วไปยังสถานะ C
3 ตัวอักษรนั้นหมายถึงสัญลักษณ์ที่จะเขียน สถานะใหม่ และทิศทางการเคลื่อนที่ สถานะ
---คือหยุด(สถานะ, ค่าเทป)ปัจจุบันแต่ละคู่ จะถูกแมปไปเป็นสามสิ่ง(ค่าเทปใหม่, ทิศทางการเคลื่อนที่ของหัวเทป, สถานะใหม่)[0] https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA