ผลลัพธ์ของ BB(3, 4) > Ack(14)

 (sligocki.com)
1 คะแนน โดย GN⁺ 2024-05-25 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • มีการค้นพบ TM แชมป์ 3-state 4-symbol Busy Beaver ตัวใหม่ และคำนวณได้ว่าเมื่อหยุดทำงานจะทิ้งสัญลักษณ์ที่ไม่ใช่ 0 ไว้จำนวน ((2 \uparrow^{15} 5) + 14)
  • จำนวนนี้ใหญ่มากแม้จะเขียนด้วยสัญกรณ์ up-arrow ของ Knuth จึงสรุปเป็นขอบล่าง (BB(3,4) > Ack(14)) ซึ่งมากกว่า Ackermann number ลำดับที่ 14 ที่นิยามโดย (Ack(n)=n \uparrow^n n)
  • พฤติกรรมหลักของ TM สามารถย่อได้ใกล้เคียงกับ (B(k,n,m) \to B(k,0,g_{k-1}^n(m))) แต่การแสดงให้เห็นสิ่งนี้ต้องใช้ การอุปนัยสองชั้น
  • ด้วย นิพจน์ประเมินแบบปิด ของ Matthew House (g_k^n(0)=\frac{2 \uparrow^k (n+2)}{2}-2) จึงสามารถเขียนคะแนนสุดท้าย (\sigma=(2 \uparrow^{15}5)+14) ได้อย่างแม่นยำ
  • TM นี้จำลองฟังก์ชันระดับ Ackermann ได้โดยไม่ต้องมีการแตกแขนงตามเศษแบบ Collatz และยังถูกใช้เป็นกรณีทดสอบสำหรับ Inductive Proof Validator ที่กำลังพัฒนาอยู่

ขนาดของ Busy Beaver แชมป์ตัวใหม่

  • Pavel Kropitz ค้นพบแชมป์ 3-state 4-symbol Busy Beaver ตัวใหม่
  • TM นี้สามารถคำนวณฟังก์ชัน “ระดับ Ackermann” ได้ และเมื่อหยุดทำงานจะเหลือสัญลักษณ์ที่ไม่ใช่ 0 บนเทปจำนวนดังนี้
    • ((2 \uparrow^{15} 5) + 14)
  • ค่านี้ใหญ่มากแม้จะเขียนด้วยสัญกรณ์ up-arrow ของ Knuth ดังนั้นขอบล่างจึงสรุปได้ดังนี้
    • (BB(3,4) > Ack(14))
  • โดยที่ (Ack(14)) คือ Ackermann number ลำดับที่ 14 ซึ่งนิยามโดย (Ack(n)=n \uparrow^n n)
  • เท่าที่ทราบ นี่เป็นกรณีแรกในบรรดา TM ที่ค้นพบจากการสำรวจจริงซึ่งสามารถจำลอง ฟังก์ชันระดับ Ackermann ได้

นิยามของ TM และคอนฟิกูเรชันสุดท้าย

  • สตริงทรานซิชันของ TM มีดังนี้
    • 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
  • ตารางทรานซิชันถูกกำหนดสำหรับสถานะ A, B, C และสัญลักษณ์ 0, 1, 2, 3
    • A: 1RB, 3LB, 1RZ, 2RA
    • B: 2LC, 3RB, 1LC, 2RA
    • C: 3RB, 1LB, 3LC, 2RC
  • คอนฟิกูเรชันสุดท้ายเป็นดังนี้
    • (0^\infty ;; 3^{2 g_{15}^{3}(0) + 1} ;; 2^{16} ;; 1 ;; \text{ Z> } ;; 0^\infty)
  • จากคอนฟิกูเรชันนี้สามารถคำนวณคะแนน (\sigma) ได้อย่างแม่นยำ
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

กระบวนการค้นพบและการตรวจสอบ

  • Pavel Kropitz แชร์ TM นี้บน Discord เมื่อวันที่ 25 เมษายน 2024
  • ตอนนั้นโค้ดยังไม่สามารถระบุขอบล่างของคะแนนในรูปแบบที่มนุษย์อ่านได้ และแสดงผลลัพธ์เป็น Halt(SuperPowers(13))
    • ซึ่งหมายความว่าการพิสูจน์ต้องใช้ กฎอุปนัย 13 ชั้น
  • หลังจากนั้นจึงเริ่มการตรวจสอบด้วย Inductive Proof Validator ตัวใหม่
  • เมื่อการตรวจสอบเสร็จสิ้นในวันที่ 20 พฤษภาคม 2024 ก็สามารถดึงนิยามที่แม่นยำของ (g_k^n(m)) ออกมาได้ และจากนั้นได้ขอบล่าง (\sigma > 2 \uparrow^{15} 3)
  • Matthew House ค้นพบนิพจน์ประเมินแบบปิดอย่างง่ายต่อไปนี้เมื่อวันที่ 22 พฤษภาคม 2024
    • (g_k^n(0) = \frac{ 2 \uparrow^k (n+2) }{2} - 2)
  • นิพจน์นี้ทำให้สามารถแสดง ค่าที่แน่นอน ของ (\sigma) ได้

การวิเคราะห์พฤติกรรมและการพิสูจน์แบบอุปนัยสองชั้น

  • กำหนดคอนฟิกูเรชันต่อไปนี้
    • (B(k, n, m) = 0^\infty ;; 3^{2m+1} ;; 2^k ;; \text{ A> } ;; 1^n)
  • คอนฟิกูเรชันเริ่มต้นจะไปถึงสถานะต่อไปนี้หลัง 241 สเต็ป
    • (0^\infty ;; \text{A>} ;; 0^\infty \xrightarrow{241} B(16,3,0);;2;;0^\infty)
  • กฎหลักมีดังนี้
    • (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), โดยที่ (k \ge 1)
  • (g_k) นิยามด้วยความสัมพันธ์เวียนเกิดดังนี้
    • (g_0(m)=m+1)
    • (g_{k+1}(m)=g_k^{2m+2}(0))
  • พฤติกรรมทั้งหมดเรียบง่ายถึงขั้นแทบย่อได้เป็นกฎเดียว แต่ตัวกฎนี้เองต้องพิสูจน์ด้วย การอุปนัยสองชั้น
  • บทตั้งและผลตามกล่าวถึงกระบวนการที่สถานะ B ประมวลผลบล็อก 3 และ 2^k เพื่อสร้าง 1
    • (3;;2^k;;\text{<B} \xrightarrow{2k+1} 2^k;;\text{<B};;1)
    • (3^m;;2^k;;\text{<B} \xrightarrow{(2k+1)m} 2^k;;\text{<B};;1^m)
  • ทฤษฎีบท 3 แสดงให้เห็นว่ากฎหลักเป็นจริงสำหรับทุก (k \ge 1, n \ge 0, m \ge 0)
    • กรณีฐาน (k=1) จัดการด้วยการอุปนัยตาม (n)
    • ขั้นอุปนัยใช้ทั้งสมมติฐานตาม (k) และสมมติฐานอุปนัยตาม (n) ร่วมกัน

การคำนวณค่าที่แน่นอน

  • (g_k) มี การประเมินแบบปิด ที่ค่อนข้างเรียบง่าย โดยใช้เพียง Knuth up-arrow และเลขคณิต
  • สำหรับทุก (k \ge 0, m \ge 0) จะได้ว่า
    • (2 g_{k+1}(m) + 4 = 2 \uparrow^k (2m+4))
    • โดยนิยามให้ (a \uparrow^0 b = ab)
  • ผลลัพธ์นี้พิสูจน์ได้ด้วยการอุปนัยตาม (k)
    • ในกรณีฐาน (k=0) จะได้ (g_1(m)=2m+2)
    • ขั้นอุปนัยใช้การประยุกต์ซ้ำของ ((2 \uparrow^k)^n)
  • รูปแบบปิดนี้อาศัยความบังเอิญที่ว่า (2 \uparrow^k 2 = 4) เป็นจริงสำหรับทุก (k)
    • หากพารามิเตอร์ต่างออกไปเล็กน้อยจนกลายเป็นรูป ((2 \uparrow^k)^{2m+2}5) ก็อาจยากที่จะได้รูปแบบปิดนี้
  • จากผลตาม จะได้ว่าสำหรับทุก (k \ge 0, n \ge 0)
    • (2 g_k^n(0) + 4 = 2 \uparrow^k (n+2))
  • คะแนนสุดท้ายจึงได้โดยตรงดังนี้
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

ผลลัพธ์จากการเรียงสับเปลี่ยนเมื่อเปลี่ยนสถานะเริ่มต้น

  • หากเปลี่ยนสถานะเริ่มต้นเป็น B หรือ C จะได้ผลลัพธ์ที่เกี่ยวข้องแต่มีขนาดเล็กกว่า
    • (0^\infty ;; \text{B>} ;; 0^\infty \xrightarrow{86} B(7,3,0);;2;;0^\infty)
    • (0^\infty ;; \text{C>} ;; 0^\infty \xrightarrow{20} B(1,3,0);;2;;0^\infty)
  • คะแนนเมื่อเริ่มจากสถานะ B เป็นดังนี้
    • (\sigma_B = 2 g_6^3(0) + 9 = (2 \uparrow^6 5) + 5)
  • เมื่อเริ่มจากสถานะ C จะหยุดใน 72 สเต็ป และมีคะแนนดังนี้
    • (\sigma_C = 2 g_0^3(0) + 3 = (2 \uparrow^0 5) - 1 = 9)
  • การเรียงสับเปลี่ยนตัวแรกที่เริ่มจาก B ก็เป็น BB(3,4) TM อันดับสูงอีกตัวหนึ่งเช่นกัน
  • เมื่อนำไปแปลงเป็น TNF จะได้สตริงทรานซิชันดังนี้
    • 1RB3RB1LC2LA_2LA2RB1LB3RA_3LA1RZ1LC2RA

ความเรียบง่ายที่ไม่มี Collatz-like rule

  • จุดที่น่าสนใจอย่างหนึ่งของ TM นี้คือมัน เรียบง่าย กว่าที่คาดไว้
  • ไม่มี กฎแบบ Collatz ที่ทำงานต่างกันไปตามเศษของค่า
  • ยังเร็วเกินไปที่จะบอกว่าการครองความเด่นของ TM แบบ Collatz-like ได้สิ้นสุดลงแล้วหรือไม่
  • อาจยังมี TM แบบ Collatz-like ระดับ Ackermann เหลืออยู่ แต่คาดว่าอาจมองไม่เห็นในทันทีเพราะ selection bias
  • สาเหตุที่ TM นี้ถูกค้นพบเป็น TM ระดับ Ackermann ตัวแรก อาจเป็นเพราะมันเรียบง่ายพอที่จะพิสูจน์การหยุดทำงานได้โดยไม่ต้องอิมพลีเมนต์ modular arithmetic บนฟังก์ชันระดับ Ackermann

Inductive Proof Validator

  • TM นี้เหมาะเป็นกรณีทดสอบสำหรับ Inductive Proof Validator ที่กำลังพัฒนาอยู่
  • เป้าหมายของโปรเจ็กต์คือการสร้างรูปแบบใบรับรองมาตรฐานสำหรับ “การพิสูจน์แบบอุปนัย”
  • คำว่า “การพิสูจน์แบบอุปนัย” ในที่นี้ใช้เป็นคำกว้าง ๆ ที่ครอบคลุมการอนุมานไปข้างหน้าและการวิเคราะห์แบบอิงกฎทั้งหมด
  • หากใครมี “inductive decider” ก็สามารถเขียนกฎนั้นให้อยู่ในรูปแบบนี้ และให้ validator ตรวจสอบการพิสูจน์ได้
  • ระบบยังค่อนข้างหยาบมากและยังไม่พร้อมสำหรับการใช้งานจริง แต่หลังผ่านงานทำมือเล็กน้อยก็ถูกใช้พิสูจน์พฤติกรรมของ TM หลายตัว รวมถึง TM นี้

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

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

 
GN⁺ 2024-05-25
ความคิดเห็นจาก Hacker News

  • เป็นเรื่องง่ายที่จะคิดว่า โปรแกรมทัวริงแมชชีนที่รันได้นานมาก ๆ น่าจะมีความซับซ้อนลึกซึ้งหรือเป็นโค้ดสปาเกตตี แต่แชมป์ใหม่ครั้งนี้แทบจะเป็นตัวอย่างโต้แย้ง
    มีเพียงสามสถานะคือ A, B, C และ B ส่งการควบคุมต่อไปยัง A กับ C แต่ A กับ C ไม่ได้ “รู้จัก” กันและกัน และย้อนกลับไปที่ B เท่านั้น
    ถ้าเป็นโค้ดสปาเกตตีจริง ๆ แต่ละสถานะก็น่าจะกระโดดไปยังสถานะอื่น ๆ ได้ทั้งหมด แต่นี่เป็น โครงสร้างแบบโมดูลาร์ รูปแบบหนึ่ง
    อีกอย่างคือมันไม่เคยพิมพ์ช่องว่าง และทุกคำสั่งจะเปลี่ยนสถานะหรือสีอย่างใดอย่างหนึ่งเสมอ จึงไม่มี “คำสั่งขี้เกียจ” ที่แค่ขยับตำแหน่งอย่าง B1 -> 1LB

    • แม้แต่ในโปรเจกต์ bbchallenge เองก็ยังมีการถกเถียงกันว่า คุณสมบัติของแชมป์ที่รันได้นานในปัจจุบันเป็นคุณสมบัติของแมชชีนที่รันได้นานที่สุดจริง ๆ ณ ขนาดนั้น หรือเป็น ผลกระทบแบบเสาไฟถนน ที่เราเห็นแค่คุณสมบัติที่ค้นหาและพิสูจน์อัตโนมัติได้ง่าย
      เราจะยังไม่รู้จนกว่าจะตัดพื้นที่ค้นหาทั้งหมดออกได้ ไม่ว่าจะด้วยวิธีแน่นอนหรือฮิวริสติก
      ทุกขนาดที่เกิน BB(5, 2) มีแมชชีนแบบโกลาหลและกึ่งสุ่มที่คาดว่าจะรันตลอดไป แต่ไม่อาจพิสูจน์ได้หากไม่มีความก้าวหน้าครั้งใหญ่ในทฤษฎีจำนวน
      อย่างไรก็ตาม มองว่าแมชชีนที่รันได้นานไม่อาจเป็นแบบโกลาหลทั้งหมดได้
      เพราะถ้ามันโปรยสัญลักษณ์ลงบนเทปราวกับเลขสุ่ม ไม่นานก็จะไปถึงคอนฟิกูเรชันที่หยุด คอนฟิกูเรชันแบบวนซ้ำ หรือแพตเทิร์นที่ลดรูปได้
      ถึงอย่างนั้น ก็เป็นไปได้ที่จะมีแมชชีนที่จำลองบางสิ่งซึ่งโกลาหลในระดับสูงกว่า ใช้เวลามหาศาลอย่างไร้เหตุผลระหว่างแต่ละขั้นระดับสูง แล้วจึงหยุด
    • ทัวริงแมชชีนที่มี n สถานะและ s สัญลักษณ์ สามารถทรานซิชันไปยังสถานะอื่นได้สูงสุดเพียง n สถานะ
      ดังนั้นถ้า s=4 หรือ s=2 มีเพียงทัวริงแมชชีนขนาดเล็กมากเท่านั้นที่สามารถเป็นเหมือนโค้ดสปาเกตตีได้

  • เจ้าของสถิติ BB(3,4) คนใหม่ มีดังนี้
    0 1 2 3
    A 1RB 3LB 1RZ 2RA
    B 2LC 3RB 1LC 2RA
    C 3RB 1LB 3LC 2RC
    (t', d, s') ในแถว s และคอลัมน์ t หมายถึงทรานซิชันเมื่อสัญลักษณ์ใต้หัวอ่านบนเทปเป็น t ในสถานะ s
    มันเขียนทับสัญลักษณ์ t ด้วย t' เลื่อนไปทางซ้าย/ขวาตามทิศทาง d จากนั้นเปลี่ยนสถานะเป็น s' และถ้า s' == Z ก็หยุด
    นี่คือ 3*4*log2(4*2*log2(4+1)) หรือประมาณ ข้อมูล 64 บิต
    ในทางกลับกัน BBλ(49) ที่มีเพียง 49 บิตนั้นเกินจำนวนของ Graham ไปไกลมาก https://oeis.org/A333479

    • การนับจำนวนทัวริงแมชชีนที่แตกต่างกันไม่ใช่เรื่องง่าย
      การคำนวณข้างต้นเป็นวิธีกว้างที่สุดที่ถือว่าแต่ละช่องสามารถมีชุดผสม (สัญลักษณ์, ทิศทาง, สถานะ) ใด ๆ ก็ได้ จึงประเมินจำนวนบิตที่จำเป็นต่อการอธิบายทัวริงแมชชีนแบบใด ๆ สูงเกินไปมาก
      สำหรับ BB(3, 4) หากใช้ Tree Normal Form หรืออัลกอริทึมของ Brady (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html) จะมีทัวริงแมชชีนที่แตกต่างกันเพียงประมาณ 600,000 ล้านตัว จึงออกมาต่ำกว่า 40 บิต
    • ในโปรแกรมนี้ 1R ของ 1RZ ดูเหมือนเป็นค่าที่เลือกมาแบบตามใจ
      เพราะมันหยุดตรงนั้นแล้ว ดังนั้นไม่ว่าอะไรจะเหลืออยู่บนเทป หรือหัวอ่านจะขยับไปไหน ก็ไม่สำคัญ
      จริง ๆ แล้วการเขียน 1 ก็ไม่สำคัญเช่นกัน แต่ถ้าเขียน 0 ก็คงไม่ใช่ค่าที่เหมาะที่สุด
      ตำแหน่งนั้นเคยมี 2 เขียนไว้อยู่แล้ว และแม้จะถูกเปลี่ยนเป็น 1 แต่ถ้านับตามจำนวนสัญลักษณ์บนเทป 2 ก็น่าจะถูกนับเหมือนกัน
    • ไม่ค่อยแน่ใจว่าพจน์ log2(4+1) มาจากไหน
      ถ้าคำนวณ 3*4*log2(4*2*log2(4+1)) จะได้ประมาณ 51 และในมุมของคนนอกสาย ก็น่าจะเป็น 3*4*log2(4*2*4) = 60
      เลยสงสัยว่าอาจเป็น 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64 หรือเปล่า

  • สงสัยว่ามันทำงานอย่างไร เลยลองอิมพลีเมนต์ไว้ที่นี่: turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc
    ถ้าลองรันสักพักจะเห็นว่าเกิดอะไรขึ้น
    สถานะ B เปลี่ยน 0 เป็น 2 เปลี่ยน 1 เป็น 1 แล้วทรานซิชันไป C ส่วนสถานะ C เปลี่ยน 3 เป็น 2 แล้วทรานซิชันไป A
    ดังนั้นหากต้องการแก้ 2 -> 1 จะต้องผ่าน 3 ทุกตัวหนึ่งรอบ จึงทำให้ ช่วงต่อเนื่องของเลข 3 ขยายตัวแบบเอ็กซ์โปเนนเชียลซ้ำ ๆ

    • การสร้างทัวริงแมชชีนที่เติบโตแบบเอ็กซ์โปเนนเชียลไปตลอดนั้นค่อนข้างง่าย
      ส่วนที่เข้าใจยากจริง ๆ คือ ทำไมสุดท้ายมันถึงหยุด หลังจากผ่านจำนวนขั้นที่มากจนจินตนาการไม่ออก

  • ฟังดูเหมือน code golf แบบสุดขั้วทั้งนั้น
    อีกทิศทางหนึ่งคือลองดูสิ่งที่เรียกว่า BitGrid
    BitGrid มีสถานะต่อเซลล์เพียง 4 บิต ดังนั้นกริดเซลล์ 4x4 ไม่ว่าอย่างไรก็ไม่สามารถนับได้เกิน 2^64
    การหาว่าจริง ๆ แล้วมันนับได้ถึงไหนน่าจะน่าสนใจ และในกริดเล็ก ๆ การเชื่อมต่อที่ขอบน่าจะครอบงำผลลัพธ์
    https://esolangs.org/wiki/Bitgrid
    https://github.com/mikewarot/Bitgrid

  • ตารางนี้น่าจะเป็นคำอธิบายของเครื่องทัวริง ถ้ามีแหล่งข้อมูลที่น่าอ่านเกี่ยวกับวิธีตีความก็คงดี

    • สถานะ A, B, C ตรงกับเป้าหมายของ goto และ สี 0, 1, 2, 3 คือข้อมูลระหว่างการทำงาน
      ในแต่ละสถานะจะอ่านสีปัจจุบัน แล้วตามสีนั้นจึงรันคำสั่งว่า “จะเขียนสีอะไร จะขยับไปซ้าย/ขวา และจะไปยังสถานะใด”
      ถ้าย้ายไปเป็น C ก็สามารถแสดงได้ตรง ๆ ด้วย switch (SCAN) กับ WRITE, RIGHT/LEFT, goto
      เลยสงสัยว่ายังมีช่องให้เขียนตรรกะนี้ใหม่ในสไตล์ที่ มีโครงสร้างมากขึ้น หรือทำ optimization แบบอื่นได้ไหม
    • แต่ละแถวคือสถานะ และแต่ละคอลัมน์คือสัญลักษณ์ที่เพิ่งอ่านจากเทป
      ตัวอย่างเช่น แถวแรกคอลัมน์แรกหมายถึง “อ่านสัญลักษณ์ 0 และสถานะปัจจุบันคือ A”
      ช่องในตารางแสดงการกระทำที่จะทำ โดย 1RB หมายถึง “เปลี่ยนสัญลักษณ์บนเทปเป็น 1, ขยับไปทางขวาหนึ่งช่อง แล้วเปลี่ยนเป็นสถานะ B”
      สถานะ Z คือ สถานะหยุด
    • ใน Python ก็ทำได้โดยมีฟังก์ชัน L(), R() สำหรับขยับดัชนีเทปไปซ้าย/ขวา สร้างตารางที่แมป (สถานะ, สัญลักษณ์ปัจจุบัน) ไปเป็น (สัญลักษณ์ที่จะเขียน, ฟังก์ชันเคลื่อนที่, สถานะถัดไป) แล้ววนซ้ำตราบใดที่ state != 'Z'
    • มีคำอธิบายสั้น ๆ ที่ https://bbchallenge.org/story#turing-machines
      1RZ ควรเข้าใจว่าเป็น transition ไปสู่การหยุด เพราะไม่มี rule สำหรับสถานะ Z
      ใน Wikipedia ก็มีตัวอย่าง ตารางสถานะของเครื่องทัวริง ที่ละเอียดกว่า https://en.wikipedia.org/wiki/Turing_machine#Formal_definition และสามารถดู trace การทำงานของเครื่องทัวริงตัวนี้ได้ที่ https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
    • ผมทำ repository เล็ก ๆ ที่รวบรวมเจ้าของสถิติปัจจุบันไว้ และแสดงตัวอย่างการรันด้วย Wolfram Language ด้วย: https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/
      ดูเหมือนว่าตอนนี้ต้องอัปเดตอันนี้ด้วย

  • การอ้างอิงผลลัพธ์สำคัญในวิทยาการคอมพิวเตอร์พื้นฐานเป็น ลิงก์ Discord เนี่ยนะ

    • ไม่เห็นรู้ว่าทำไมถึงไม่ได้
      ความคิดที่ว่าวิธีเดียวที่ถูกต้องในการเผยแพร่ผลลัพธ์ทางวิทยาศาสตร์คือวารสารที่เรียกกันว่า peer-reviewed นั้นเป็นซากตกค้างจากเมื่อ 200 ปีก่อน ตอนที่ชุมชนวิทยาศาสตร์ยังเล็กพอจะอยู่ภายใน Dunbar's number
      ที่ยังยึดกันอยู่ทุกวันนี้ก็เพราะนักวิชาการบางกลุ่มที่มีอำนาจและสำนักพิมพ์ได้ประโยชน์ ไม่ใช่เพราะมันมีข้อดีจริงในแง่ความก้าวหน้าทางวิทยาศาสตร์
      กลับกัน มันอาจมีส่วนรับผิดชอบค่อนข้างมากต่อวิกฤต reproducibility ในยุคปัจจุบันด้วย
      ผมสนับสนุน scientific method อย่างหนักแน่น แต่คิดว่า peer review แบบดั้งเดิมหมดอายุไปนานมากแล้ว
      https://en.wikipedia.org/wiki/Dunbar%27s_number
    • ถึงอย่างนั้นก็เป็นเซิร์ฟเวอร์ Discord สาธารณะ และหาลิงก์เชิญได้ที่มุมขวาบนของ https://bbchallenge.org
      ผมมองว่าสิ่งเหล่านี้ใกล้เคียงกับ การระบุที่มา มากกว่าการอ้างอิง
      อาร์กิวเมนต์หลักที่รองรับผลลัพธ์ถูกนำเสนอซ้ำในรูปแบบที่เคร่งครัดกว่าในบล็อกโพสต์อยู่แล้ว จึงยืนได้ด้วยตัวเอง ส่วนลิงก์ Discord แค่ให้บริบททางประวัติศาสตร์สำหรับคนที่สนใจเท่านั้น
    • ถ้าได้เข้าไปมีส่วนร่วมในแชตแบบนี้ จะคล้ายกับการคิดไอเดียบนกระดานดำในห้องพักแล้วพัฒนาร่วมกัน ต่างกันตรงที่สามารถอ้างอิงปฏิสัมพันธ์นั้นได้
      ถ้าเสริมด้วยเอกสารอ้างอิงในจังหวะที่เหมาะสมได้ ก็เป็นการเปลี่ยนแปลงในทางบวก
    • เข้าใจความไม่พอใจนะ แต่ความก้าวหน้าน่าประทับใจจำนวนมากในคณิตศาสตร์ช่วงหลังมาจากการร่วมมือและ iterate อย่างรวดเร็ว
      ตัวอย่างเช่นโปรเจกต์ที่ปรับปรุง ขอบเขตบนของช่องว่างระหว่างจำนวนเฉพาะ ของ Zhang และในแง่นี้ เครื่องมือสื่อสารอื่นอาจไม่สามารถแทน Discord ได้ง่าย ๆ
      ต้องไปยังที่ที่คนจริง ๆ รวมตัวกันอยู่
    • การหาจำนวน busy beaver ที่ใหญ่ขึ้นนั้นใกล้เคียงกับ คณิตศาสตร์นันทนาการ มากกว่าจะเป็นเรื่องพื้นฐานจริง ๆ
      ถ้ามันพื้นฐานจริง ก็คงไม่โพสต์ลงบล็อก แต่ส่งเป็นบทความวารสารให้ peer review แล้ว

  • เครื่องทัวริงที่อธิบายได้ด้วยปริมาณสัญลักษณ์ไม่ใหญ่มากอย่าง 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC มีจำนวนที่เป็นไปได้จำกัด
    แต่ความจริงที่ว่าบางเครื่องในนั้นสามารถรันได้เป็นจำนวนก้าวมหาศาลขนาดนี้ก่อนจะหยุด ช่างน่าทึ่งจริง ๆ

    • เครื่องทัวริงแบบ 3 สถานะ 4 สัญลักษณ์เช่นนี้มีอยู่ 2^60 เครื่อง
      lambda term ขนาด 49 บิต ที่ให้ผลลัพธ์ หรือ normal form ใหญ่กว่า Graham's number น่าจะยิ่งน่าทึ่งกว่า

  • พูดตามตรง ผมไม่ได้เข้าใจ 100% และผลลัพธ์เหล่านี้ก็คงแทบไม่มีประโยชน์ แต่กลับดึงดูดผมมากกว่าความก้าวหน้าของ LLM ที่มีประโยชน์เหลือเชื่อ
    อาจเป็นเพราะโดยธรรมชาติแล้วผมถูกดึงดูดด้วย ความจริงทางคณิตศาสตร์ที่เรียบง่าย มากกว่าผลลัพธ์ทางวิศวกรรมที่ “ซับซ้อน”

  • ไม่ใช่ BB(5) > BB(3,4) เหรอ?
    ใน https://bbchallenge.org บอกว่ากำลังพยายามพิสูจน์หรือหักล้างข้อสันนิษฐานว่า BB(5) อยู่ราว 47 ล้าน แต่ BB(3,4) ดูเหมือนจะใหญ่กว่านั้นมาก

    • ใช่ ดูเหมือนว่า BB(3, 4) >>> BB(5, 2)
      BB(5) = BB(5, 2) และ BB(3, 4) มี transition ในตาราง 12 ตัว (3*4) ขณะที่ BB(5, 2) มีแค่ 10 ตัว จึงไม่น่าแปลกใจนัก
      แต่ดูเหมือนว่า BB(3, 4) >> BB(6, 2) ด้วย
      ทั้งสองมีจำนวน transition เท่ากัน ดังนั้นสำหรับเครื่องทัวริงขนาดเล็กแบบนี้ การมีจำนวนสัญลักษณ์มากกว่า ดูจะมีคุณค่าพอสมควร