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

BB(3, 4) > Ack(14)

• 22 พฤษภาคม 2024
  • Pavel ค้นพบเครื่องทัวริง 3 สถานะ 4 สัญลักษณ์ (Turing Machine, TM)
  • เครื่องนี้คำนวณฟังก์ชันระดับ "Ackermann" และหยุดทำงานโดยมีสัญลักษณ์ที่ไม่เป็นศูนย์เหลืออยู่พอดีจำนวน (2↑155)+14 ตัว
  • ส kýลักษณ์ลูกศรชี้ขึ้นของ Knuth เริ่มใช้งานไม่สะดวกนัก จึงสามารถประมาณได้ดังนี้: BB(3,4)>Ack(14)
  • โดย Ack(14) นิยามเป็นจำนวน Ackermann ลำดับที่ 14: Ack(n)=n↑nn
  • นี่คือ TM ตัวแรกที่ค้นพบ "ในธรรมชาติ" ซึ่งสามารถจำลองฟังก์ชันระดับ Ackermann ได้

เครื่อง

• ตารางการเปลี่ยนสถานะ

  | 0   | 1   | 2   | 3   |
  | --- | --- | --- | --- |
  | A   | 1RB | 3LB | 1RZ | 2RA |
  | B   | 2LC | 3RB | 1LC | 2RA |
  | C   | 3RB | 1LB | 3LC | 2RC |
  

• คอนฟิกูเรชันสุดท้าย

  • 0∞32g153(0)+12161 Z> 0∞
  • มีสัญลักษณ์ที่ไม่เป็นศูนย์เหลืออยู่บนเทปพอดีจำนวน σ=2g153(0)+18=(2↑155)+14 ตัว

Attribution

• ผู้ค้นพบ
  • TM นี้ถูกค้นพบโดย Pavel Kropitz(@uni) และแชร์บน Discord เมื่อวันที่ 25 เมษายน 2024
  • โค้ดของเขาไม่สามารถระบุขอบเขตที่มนุษย์อ่านเข้าใจได้สำหรับคะแนน TM และถูกระบุไว้เพียงว่า Halt(SuperPowers(13))
  • เขาเริ่มตรวจสอบผลลัพธ์นี้โดยใช้ "ตัวตรวจสอบการพิสูจน์แบบอุปนัย" ตัวใหม่
  • เมื่อวันที่ 20 พฤษภาคม 2024 ได้ดึงนิยามที่แน่นอนของ gkn(m) ออกมา และได้ขอบเขต σ>2↑153
  • Matthew House(@LegionMammal978) ค้นพบรูปปิดอย่างง่ายของ gkn(0)=2↑k(n+2)2−2 เมื่อวันที่ 22 พฤษภาคม 2024

การวิเคราะห์

• นิยามของ B(k,n,m)

  B(k,n,m)=0∞32m+12k A> 1n
  

• การพิสูจน์

  0∞A>0∞→241B(16,3,0)20∞
  B(k,n,m)→B(k,0,gk−1n(m)) if k≥1
  B(k,0,m)2→10∞32m+12k1Z>
  

• นิยามของ gk(m)

  g0(m)=m+1
  gk+1(m)=gk2m+2(0)
  

การพิสูจน์ด้วยอุปนัยสองชั้น

• กฎหลัก

  B(k,n,m)→B(k,0,gk−1n(m))
  

• เลมมา 1

  For all k≥1: 32k<B→2k+12k<B1
  

• ผลตามมา 2

  For all k≥1,m≥0: 3m2k<B→(2k+1)m2k<B1m
  

• ทฤษฎีบท 3

  For all k≥1,n≥0,m≥0: B(k,n,m)→B(k,0,gk−1n(m))
  

ค่าที่แน่นอน

• ทฤษฎีบท

  For all k≥0,m≥0: 2gk+1(m)+4=2↑k(2m+4)
  

• ผลตามมา

  For all k≥0,n≥0: 2gkn(0)+4=2↑k(n+2)
  

• ข้อสรุป

  σ=2g153(0)+18=(2↑155)+14
  

Permutations

• เริ่มจากสถานะ B

  σB=2g63(0)+9=(2↑65)+5
  

• เริ่มจากสถานะ C

  σC=2g03(0)+3=(2↑05)−1=9 (หยุดใน 72 ขั้นตอน)
  

• TNF ที่แปลงแล้ว

  | 0   | 1   | 2   | 3   |
  | --- | --- | --- | --- |
  | A   | 1RB | 3RB | 1LC | 2LA |
  | B   | 2LA | 2RB | 1LB | 3RA |
  | C   | 3LA | 1RZ | 1LC | 2RA |
  

Not Collatz

• จุดที่น่าสนใจ
  • TM นี้เรียบง่ายอย่างน่าประหลาดใจ
  • ไม่มีกฎแบบ Collatz
  • แต่นี่ไม่ได้ตัดความเป็นไปได้ว่าจะมี TM ระดับ Ackermann แบบเดียวกับ Collatz อยู่

Inductive Proof Validator

• เป้าหมายของโครงการ
  • กำลังพัฒนาเครื่องมือตรวจสอบ "การพิสูจน์แบบอุปนัย"
  • พัฒนารูปแบบใบรับรองมาตรฐานเพื่อให้ตรวจสอบการพิสูจน์แบบอุปนัยได้หลากหลายรูปแบบ
  • ยังอยู่ในระยะเริ่มต้น แต่ประสบความสำเร็จในการพิสูจน์การทำงานของ TM หลายตัวแล้ว

ความเห็นของ GN⁺

• จุดที่น่าสนใจ

  • บทความนี้ช่วยให้เข้าใจความซับซ้อนของเครื่องทัวริงและฟังก์ชัน Ackermann ได้มาก
  • แนวคิดที่ว่ากฎง่าย ๆ สามารถทำการคำนวณที่ซับซ้อนได้เป็นสิ่งที่น่าดึงดูด

• มุมมองเชิงวิจารณ์

  • การจะเข้าใจความซับซ้อนของเครื่องนี้จำเป็นต้องมีพื้นฐานคณิตศาสตร์
  • เน้นความน่าสนใจเชิงทฤษฎีมากกว่าการประยุกต์ใช้จริง

• เทคโนโลยีที่เกี่ยวข้อง

  • ตัวตรวจสอบการพิสูจน์แบบอุปนัยอาจมีส่วนช่วยอย่างมากต่อการพัฒนาระบบพิสูจน์คณิตศาสตร์อัตโนมัติ
  • มีศักยภาพที่จะนำไปใช้กับปัญหาการคำนวณซับซ้อนอื่น ๆ ได้

• ข้อควรพิจารณา

  • เมื่อนำเทคโนโลยีนี้มาใช้ ควรคำนึงถึงความถูกต้องและประสิทธิภาพของกระบวนการตรวจสอบ
  • ต้องใช้เวลาในการทำความเข้าใจและประยุกต์ใช้แนวคิดคณิตศาสตร์ที่ซับซ้อนเหล่านี้

[GN⁺]

ความคิดเห็นจาก Hacker News

สรุปรวมความคิดเห็นจาก Hacker News

• โปรแกรมเครื่องทัวริงที่เรียบง่าย
  ต่างจากความคิดที่ว่าโปรแกรมเครื่องทัวริงคงจะเป็นสปาเก็ตตี้โค้ดที่ซับซ้อน โปรแกรมใหม่นี้ค่อนข้างเรียบง่าย มีสามสถานะ (A, B, C) โดยสถานะ B ส่งต่อการควบคุมไปยัง A และ C แต่ A และ C ไม่รู้จักกันและส่งต่อการควบคุมกลับไปที่ B เท่านั้น นี่เป็นโครงสร้างแบบแยกส่วน ซึ่งต่างจากสปาเก็ตตี้โค้ดจริง ๆ ที่แต่ละสถานะสามารถส่งต่อการควบคุมไปยังสถานะอื่นทั้งหมดได้

• ลักษณะที่น่าสนใจ
  โปรแกรมนี้ไม่พิมพ์ช่องว่าง และทุกคำสั่งจะเปลี่ยนสถานะหรือสี เจ้าของสถิติ BB(3,4) คนใหม่มีข้อมูลประมาณ 64 บิต ส่วน BBλ(49) ที่มี 49 บิตนั้นมากกว่าจำนวน Graham อย่างมหาศาล

• ตัวอย่างการติดตั้งใช้งาน
  จากการลองนำโปรแกรมไปเขียนเอง พบว่าสถานะ B เปลี่ยน 0 เป็น 2 และ 1 เป็น 1 แล้วสลับไปยัง C ขณะที่สถานะ C เปลี่ยน 3 เป็น 2 แล้วสลับไปยัง A ซึ่งทำให้ลำดับของเลข 3 ยาวขึ้นแบบเอ็กซ์โปเนนเชียล

• ความคล้ายกับ code golf
  ทั้งหมดนี้ดูเหมือน code golf แบบสุดขั้ว BitGrid ซึ่งเป็นโปรเจกต์งานอดิเรกส่วนตัว มีสถานะเพียง 4 บิตต่อเซลล์ และกริด 4x4 สามารถนับได้สูงสุดถึง 2^64 ในกริดขนาดเล็ก การเชื่อมขอบมีผลอย่างมากต่อผลลัพธ์

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

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

• คำขอคำอธิบายว่าพิเศษอย่างไร
  มีการขอคำอธิบายว่าทำไมชุดคำสั่งนี้จึงน่าประทับใจ อยากรู้ว่าฟังก์ชันระดับ Ackerman คืออะไร และในทางปฏิบัติมันคำนวณอะไร

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

• การเปรียบเทียบ BB(5) กับ BB(3,4)
  มีคำถามว่า BB(5) ใหญ่กว่า BB(3,4) หรือไม่ โดยในเว็บไซต์ bbchallenge.org ระบุว่า BB(5) มีค่าประมาณ 47 ล้าน แต่ BB(3,4) ใหญ่กว่านั้นมาก

• การให้บริบทของผู้เขียน
  เป็นเรื่องดีที่ผู้เขียนได้ให้บริบทไว้บ้าง