Knuth ได้เผยแพร่บทความต้นฉบับชื่อ “Claude’s Cycles” บนเว็บไซต์ของมหาวิทยาลัยสแตนฟอร์ด โดยเปิดบทความด้วยคำว่า “Shock! Shock!” เพื่อแสดงความตะลึงของเขา
ที่อยู่บทความ: https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf
Knuth เป็นบุคคลสัญลักษณ์ในวงการวิทยาศาสตร์คอมพิวเตอร์ เขาเป็นผู้ได้รับรางวัลทัวริง ผู้เขียนหนังสือ “The Art of Computer Programming” (TAOCP) ที่ได้รับการยกย่องว่าเป็น “คัมภีร์แห่งอัลกอริทึม” และยังเป็นผู้คิดค้นระบบจัดเรียงพิมพ์ TeX
“The Art of Computer Programming” เป็นงานตลอดชีวิตของ Knuth โดยมีเป้าหมายเพื่อจัดระบบและเสริมสร้างรากฐานทางคณิตศาสตร์และประวัติศาสตร์ของอัลกอริทึมคอมพิวเตอร์ การที่นักวิชาการผู้เชี่ยวชาญด้านอัลกอริทึมมานานกว่า 50 ปีเริ่มพิจารณาความสามารถทางคณิตศาสตร์ของ AI อย่างจริงจังนั้น เป็นสัญญาณที่ชัดเจนว่า AI กำลังเข้าถึงขอบเขตความสามารถทางปัญญาที่เป็นแก่นกลางของมนุษย์
ปัญหาที่ทำให้บิดาแห่งอัลกอริทึมติดขัด ถูก Claude Opus 4.6 พิชิตได้
ในบทความ Knuth เล่าว่า “เมื่อวานฉันเพิ่งทราบว่า ปัญหาที่ยังไม่มีคำตอบซึ่งฉันใช้เวลาศึกษาหลายสัปดาห์ เพิ่งถูกแก้ไขโดย Claude Opus 4.6 — โมเดลการให้เหตุผลแบบผสมที่ Anthropic เปิดตัวเมื่อสามสัปดาห์ก่อน!”
เขากล่าวเพิ่มเติมว่า “ดูเหมือนว่าฉันจะต้องทบทวนมุมมองของตัวเองที่มีต่อ ‘Generative AI’ ในไม่ช้า เป็นเรื่องน่ายินดีอย่างยิ่งที่ได้รู้ว่าข้อคาดการณ์ของฉันไม่เพียงแต่มีวิธีแก้ที่สวยงาม แต่ยังได้เห็นความก้าวหน้าอย่างมากในด้านการให้เหตุผลอัตโนมัติและการแก้ปัญหาอย่างสร้างสรรค์นี้”
จุดเริ่มต้นของเหตุการณ์มาจากโจทย์ปัญหาที่ Knuth เตรียมไว้สำหรับบทใหม่ของหนังสือชุด “The Art of Computer Programming” ที่เขากำลังเขียนต่อเนื่อง ปัญหานี้เกี่ยวข้องกับวัฏจักรแฮมิลตันในกราฟมีทิศทาง เขาและเพื่อนๆ ได้พิสูจน์กรณีพิเศษของมันแล้ว แต่พบกับอุปสรรคเมื่อพยายามขยายผลไปสู่กรณีทั่วไป
ในที่สุด Claude Opus 4.6 ก็พบวิธีแก้เชิงสร้างสรรค์ (constructive solution) ที่สง่างามสำหรับปัญหานี้ หลังจากนั้น Knuth เองได้ให้การพิสูจน์ทางคณิตศาสตร์ที่เข้มงวดสำหรับโครงสร้างนี้ บทความวิจัยนี้จึงกลายเป็นเครื่องหมาย: การมีส่วนร่วมของ Generative AI ถูกบันทึกอย่างเป็นทางการและเข้มงวดเป็นครั้งแรกในการวิจัยทางคณิตศาสตร์
ปัญหายาก: การแยกวัฏจักรสามวงในกราฟทอรัสสามมิติ
โจทย์ปัญหานี้เป็นปัญหาทฤษฎีกราฟที่ดูง่ายแต่ซับซ้อน
ลองนึกภาพพื้นที่ตารางสามมิติรูปทอรัส นั่นคือลูกบาศก์ขนาด m × m × m โดยแต่ละจุดยอดแทนด้วยพิกัด (i, j, k) (แต่ละพิกัดมีค่าตั้งแต่ 0 ถึง m-1) ดังนั้น กราฟจึงมีจุดยอดทั้งหมด m³ จุด
จากแต่ละจุดยอด อนุญาตให้เคลื่อนที่ไปในทิศทางบวกของแกนพิกัดทั้งสาม (i+1, j+1, k+1) เมื่อค่าพิกัดถึง m จะวนกลับไปที่ 0 ด้วยวิธีนี้ แต่ละจุดยอดจะมีเส้นออก 3 เส้น และกราฟทั้งหมดมีเส้นมีทิศทาง 3m³ เส้น
เป้าหมายของปัญหาคือ: หาสามวัฏจักรแฮมิลตัน (คือเส้นทางที่ผ่านแต่ละจุดยอดเพียงครั้งเดียวและกลับสู่จุดเริ่มต้น) เพื่อให้เส้นทางทั้งสามนี้ครอบคลุมเส้นทุกเส้นในกราฟพอดี และแต่ละเส้นเป็นของวัฏจักรเดียวเท่านั้น Knuth วางแผนเดิมที่จะเขียนปัญหานี้และวิธีแก้ (ที่ในตอนนั้นยังไม่รู้) ลงในหนังสือของเขา
ความยากของปัญหานี้อยู่ที่พื้นที่การค้นหาที่กว้างใหญ่ แต่ละจุดยอดต้องเลือกเส้นออกหนึ่งในสามเส้นเพื่อประกอบเป็นวัฏจักร ดังนั้นจำนวนชุดค่าผสมที่เป็นไปได้จึงสูงถึง 3^(m³) การค้นหาแบบ brute force แทบจะเป็นไปไม่ได้ ต้องหาวิธีการสร้างที่มีรูปแบบแน่นอน
ก่อนหน้านี้ Knuth ได้แก้กรณี m=3 แล้ว และผู้ร่วมงานของเขา Filip Stappers พบคำตอบสำหรับ 4 ≤ m ≤ 16 จากการทดลองด้วยคอมพิวเตอร์ ซึ่งชี้ให้เห็นอย่างแรงกล้าว่ามีคำตอบทั่วไปอยู่
แล้วเราสามารถหาสูตรทั่วไปที่ใช้ได้กับ m ทุกค่า (หรือกลุ่มหนึ่ง) ได้หรือไม่?
กระบวนการวิจัย: การสำรวจ 31 ครั้งของ Claude
Filip มอบปัญหาให้กับ Claude Opus 4.6 และขอให้บันทึกความคืบหน้าของการสำรวจในแต่ละครั้งที่รันโปรแกรมอย่างเคร่งครัด น่าสนใจที่กระบวนการแก้ปัญหาของ Claude ไม่ใช่การสำเร็จในครั้งเดียว แต่ผ่านการลองอย่างเป็นระบบ 31 ครั้ง ซึ่งรูปแบบคล้ายกับขั้นตอนการทำงานของนักวิจัยมนุษย์
- การลองครั้งแรก: เริ่มด้วยการลองใช้ฟังก์ชันเชิงเส้นง่ายๆ เพื่อตัดสินใจทิศทางการเคลื่อนที่ของแต่ละจุดยอด แต่พบว่าวิธีนี้ใช้ไม่ได้
- การค้นหาแบบ brute force: หันไปใช้การค้นหาแบบลึกก่อน (DFS) แต่มีประสิทธิภาพต่ำเนื่องจากพื้นที่สถานะระเบิด
- การวิเคราะห์ลดมิติ: หันไปวิเคราะห์ปัญหาที่คล้ายกันในสองมิติ พบโครงสร้าง “เส้นทางรูปงู” และพยายามขยายผลไปยังสามมิติ
- การลองผิดลองต่อเนื่อง: ในการสำรวจอีกสิบกว่าครั้งต่อมา Claude พยายามสร้างเส้นทางและวิธีการแยกต่างๆ อย่างต่อเนื่อง แต่ยังไม่พบคำตอบทั่วไป
จุดเปลี่ยนสำคัญ: การแยกเส้นใย (Fiber Decomposition)
ในการสำรวจครั้งที่ 15 Claude เสนอแนวคิดหลัก: การแยกเส้นใย
มันสังเกตเห็นว่า หากกำหนด s = (i + j + k) mod m แล้ว เส้นมีทิศทางทั้งหมดจะเคลื่อนจุดยอดจากชั้น s ไปยังชั้น (s+1) mod m ซึ่งหมายความว่ากราฟสามมิติทั้งหมดสามารถ “หั่น” ตามค่า s ได้ แต่ละชั้น (s คงที่) ของจุดยอดจะประกอบเป็นโครงสร้างตารางสองมิติ ข้อมูลเชิงลึกนี้ทำให้ปัญหาง่ายขึ้นอย่างมาก
หลังจากนั้น Claude ลองใช้การค้นหาแบบสุ่ม การหลอมจำลอง (simulated annealing) และการค้นหาย้อนกลับ (backtracking search) แม้ว่าจะสามารถหาคำตอบสำหรับ m เฉพาะบางค่าได้ แต่ยังไม่สามารถสรุปกฎทั่วไปได้ มันจึงสรุปว่า: ต้องหากฎการสร้างทางคณิตศาสตร์ล้วนๆ
ความสำเร็จในที่สุด: การสำรวจครั้งที่ 31 พบกฎการสร้าง
ในการสำรวจครั้งที่ 31 Claude ในที่สุดก็เสนอชุดกฎที่กระชับ แกนกลางของกฎยังคงอยู่บนพื้นฐานของ s = (i + j + k) mod m
กฎเฉพาะขึ้นอยู่กับค่า s, ความคู่คี่ (parity) หรือค่าของ i และ j เพื่อตัดสินใจว่าจะ “กระโดด” (bump) ในทิศทางพิกัดใด ตัวอย่างเช่น:
* เมื่อ s = 0 ทิศทางการเคลื่อนที่จะถูกกำหนดโดยค่า j
* เมื่อ 0 < s < m-1 ทิศทางการเคลื่อนที่จะถูกกำหนดโดยค่า i
* เมื่อ s = m-1 จะใช้กฎอีกชุดหนึ่ง
Claude ยืนยันผ่านการเขียนโปรแกรมว่า สำหรับ m=3, 5, 7, 9, 11 เป็นต้น (เลขคี่) เส้นทางที่สร้างขึ้นจากกฎนี้สามารถแยกออกเป็นสามวัฏจักรแฮมิลตันได้สำเร็จ
แน่นอน Claude ให้มาเป็นวิธีการสร้าง Knuth ได้ทำการพิสูจน์ทางคณิตศาสตร์ที่เข้มงวดในภายหลัง ยืนยันว่าโครงสร้างนี้สร้างวัฏจักรที่ครอบคลุมจุดยอดทั้งหมดได้จริง และวัฏจักรทั้งสามครอบคลุมเส้นทุกเส้นโดยไม่ทับซ้อนกัน
นอกจากนี้ การศึกษาต่อของ Knuth ยังแสดงให้เห็นว่า สิ่งที่ Claude ค้นพบเป็นเพียงหนึ่งในคำตอบที่เป็นไปได้หลายวิธี อันที่จริงมีวิธีการแยกที่ตรงกับโครงสร้างคล้ายกันนี้760 วิธี ในขณะเดียวกัน โครงสร้างนี้ในปัจจุบันใช้ได้เฉพาะกรณีที่ m เป็นเลขคี่ เท่านั้น สำหรับ m คู่ ปัญหานี้ยังไม่ได้รับการแก้ไขอย่างสมบูรณ์ (เช่น m=2 ได้รับการพิสูจน์แล้วว่าไม่มีคำตอบ)
ความหมาย: การสำรวจกระบวนทัศน์การวิจัยที่เกินกว่าการแก้ปัญหา
ความหมายที่ลึกซึ้งที่สุดของเหตุการณ์นี้อาจไม่ได้อยู่ที่การแก้ข้อคาดการณ์เฉพาะเรื่อง แต่อยู่ที่กระบวนทัศน์การวิจัยที่ AI แสดงให้เห็นในการแก้ปัญหา
ตลอดกระบวนการ Claude ไม่ได้ทำการเดาสุ่ม แต่ดำเนินการทบทวนปัญหา การทดลองด้วยการเขียนโปรแกรม การจดจำรูปแบบ และการสรุปกฎเกณฑ์อย่างเป็นระบบ กระบวนการนี้มีความคล้ายคลึงกับวิธีการทำงานของนักวิจัยคณิตศาสตร์มนุษย์อย่างมาก
ตลอดหลายทศวรรษที่ผ่านมา การพิสูจน์ทางคณิตศาสตร์一直被มองว่าเป็นวิหารที่ AI เข้าไปเกี่ยวข้องได้ยาก แต่บทความนี้แสดงให้เห็นว่า AI เริ่มสามารถมีส่วนร่วมในการสำรวจทางคณิตศาสตร์ที่มีสาระสำคัญได้แล้ว ในอนาคต โหมดการทำงานร่วมกันแบบใหม่อาจกลายเป็นเรื่องปกติ: มนุษย์เสนอปัญหาสำคัญและทิศทาง AI ทำการสำรวจและค้นหาโครงสร้างที่อาจเป็นไปได้ มนุษย์ทำการพิสูจน์ที่เข้มงวดและยกระดับทฤษฎีในที่สุด
บทความ “Claude’s Cycles” นี้ อาจถูกมองว่าเป็นจุดเริ่มต้นของยุคใหม่นี้
Knuth เขียน “The Art of Computer Programming” มานานกว่าครึ่งศตวรรษแล้ว ชุดหนังสือยักษ์นี้บันทึกวิวัฒนาการของความคิดด้านอัลกอริทึมของมนุษย์ ตอนนี้ การมีส่วนร่วมของ AI ถูกบันทึกอย่างเป็นทางการในบทความของบิดาแห่งอัลกอริทึมท่านนี้ นี่อาจเป็นเพียงจุดเริ่มต้นเท่านั้น
Knuth: ไม่เพียงแต่เป็นบิดาแห่งวิทยาศาสตร์คอมพิวเตอร์
Donald Ervin Knuth เกิดเมื่อวันที่ 10 มกราคม ค.ศ. 1938 ที่เมืองมิลวอกี สหรัฐอเมริกา เป็นนักวิทยาศาสตร์คอมพิวเตอร์ที่มีชื่อเสียงระดับโลก และศาสตราจารย์กิตติคุณแห่งมหาวิทยาลัยสแตนฟอร์ด
เขาได้รับการยอมรับว่าเป็นผู้วางรากฐานของสาขาการวิเคราะห์อัลกอริทึม เป็นหนึ่งในผู้บุกเบิกวิทยาศาสตร์คอมพิวเตอร์สมัยใหม่ และมีส่วนร่วมที่เป็นรากฐานในหลายสาขาย่อยของวิทยาการคอมพิวเตอร์เชิงทฤษฎี เนื่องจากงานบุกเบิกของเขาในการวิเคราะห์อัลกอริทึมและการออกแบบภาษาการเขียนโปรแกรม เขาได้รับรางวัลทัวริง (เกียรติยศสูงสุดในสาขาวิทยาศาสตร์คอมพิวเตอร์) ในปี ค.ศ. 1974 เมื่ออายุ 36 ปี และยังคงเป็นหนึ่งในผู้ได้รับรางวัลที่อายุน้อยที่สุดของรางวัลนี้
ถ้อยคำมอบรางวัลกล่าวถึงการมีส่วนร่วมอันยอดเยี่ยมของหนังสือชุดยักษ์ของเขา “The Art of Computer Programming” (TAOCP) ต่อศิลปะการเขียนโปรแกรมคอมพิวเตอร์เป็นพิเศษ ในปี ค.ศ. 1999 หนังสือเล่มนี้ถูกนิตยสาร American Scientist จัดให้เป็นหนึ่งใน 12 หนังสือวิชาการที่ดีที่สุดของศตวรรษที่ 20 ร่วมกับงานสำคัญเช่น “ทฤษฎีสัมพัทธภาพ” ของไอน์สไตน์
เล่มแรกของหนังสือชุดนี้ตีพิมพ์ในปี ค.ศ. 1968 และภายในปี ค.ศ. 1976 ยอดขายเกินหนึ่งล้านเล่ม บิล เกตส์ เคยให้ความเห็นว่า “ถ้าคุณคิดว่าตัวเองเป็นโปรแกรมเมอร์ที่ดี ลองอ่าน ‘The Art of Computer Programming’ สิ ถ้าคุณอ่านจบแล้ว โปรดส่งเรซู
⚠️ หมายเหตุ: เนื้อหาได้รับการแปลโดย AI และตรวจสอบโดยมนุษย์ หากมีข้อผิดพลาดโปรดแจ้ง
本文来自网络搜集，不代表คลื่นสร้างอนาคต立场，如有侵权，联系删除。转载请注明出处：https://www.itsolotime.com/th/archives/24173