สะพานใหม่ที่เชื่อมคณิตศาสตร์ประหลาดของอนันต์เข้ากับวิทยาการคอมพิวเตอร์

• มีการค้นพบว่า ทฤษฎีเซตเชิงพรรณนา ซึ่งเป็นสาขาเทคนิคที่ศึกษาถึง โครงสร้างของเซตอนันต์ สามารถ ตีความใหม่ในภาษาของอัลกอริทึม ได้
• นักคณิตศาสตร์ Anton Bernshteyn พิสูจน์ว่า ปัญหาของกราฟอนันต์ สามารถเขียนใหม่เป็น ปัญหาการสื่อสารในเครือข่ายคอมพิวเตอร์ ได้
• ความเชื่อมโยงนี้แสดงให้เห็นความสัมพันธ์สอดคล้องกันระหว่าง ความสามารถในการวัด (measurability) กับ ประสิทธิภาพของอัลกอริทึมแบบกระจาย
• นักวิจัยกำลังใช้สะพานนี้เพื่อ แปลงทฤษฎีบทและปัญหาระหว่างสองสาขาไปมา และสร้างผลลัพธ์ใหม่
• นี่เป็นการค้นพบที่ นิยามเส้นแบ่งระหว่างอนันต์กับการคำนวณใหม่ และขยายความเป็นไปได้ของความร่วมมือระหว่างคณิตศาสตร์กับวิทยาการคอมพิวเตอร์

---

บทนำ: ทฤษฎีเซตและโลกของอนันต์

• รากฐานของคณิตศาสตร์สมัยใหม่ตั้งอยู่บน ทฤษฎีเซต และนักคณิตศาสตร์ส่วนใหญ่ก็ทำงานบนสมมติฐานนี้
• อย่างไรก็ตาม นักทฤษฎีเซตเชิงพรรณนา (descriptive set theorists) เป็นกลุ่มนักวิจัยส่วนน้อยที่ยังคงสำรวจธรรมชาติของเซตอนันต์อย่างต่อเนื่อง
• ในปี 2023 Anton Bernshteyn ค้นพบ ความเชื่อมโยงเชิงลึกระหว่างทฤษฎีเซตเชิงพรรณนากับวิทยาการคอมพิวเตอร์
  • โดยแสดงให้เห็นว่าปัญหาของเซตอนันต์บางประเภทสามารถแปลงเป็น ปัญหาการสื่อสารในเครือข่ายคอมพิวเตอร์ ได้
• ผลลัพธ์นี้ถูกมองว่าเป็นสะพานที่เชื่อมภาษาซึ่งดูตรงข้ามกันอย่าง ตรรกะกับอัลกอริทึม และ อนันต์กับจำนวนจำกัด

ภูมิหลังของทฤษฎีเซตเชิงพรรณนา

• จุดกำเนิดของทฤษฎีเซตเริ่มจากงานวิจัยของ Georg Cantor ซึ่งพิสูจน์ว่ามี ขนาดของอนันต์ ที่แตกต่างกัน
• แนวคิดที่ใช้บอกขนาดของเซตมีทั้ง คาร์ดินาลิตี (cardinality) และ การวัด (measure)
  • ตัวอย่าง: เซตของจำนวนจริงในช่วง 0~1 และเซตของจำนวนจริงในช่วง 0~10 มีคาร์ดินาลิตีเท่ากัน แต่มีการวัดเป็น 1 และ 10 ตามลำดับ
• ทฤษฎีเซตเชิงพรรณนาแยกความแตกต่างระหว่าง เซตที่วัดได้กับเซตที่วัดไม่ได้ และจัดจำแนกสิ่งเหล่านี้เป็น ลำดับชั้นความซับซ้อน (hierarchy)
• ลำดับชั้นนี้กลายเป็น เกณฑ์ในการเลือกเครื่องมือที่เหมาะสม ในสาขาคณิตศาสตร์อื่น ๆ เช่น ทฤษฎีความน่าจะเป็น ระบบพลวัต และทฤษฎีกลุ่ม

กราฟอนันต์และปัญหาการระบายสี

• Bernshteyn ศึกษา กราฟอนันต์ โดยจำลองโหนดและเส้นเชื่อมของแต่ละกราฟให้เป็น โครงสร้างที่เชื่อมต่อกันอย่างไม่สิ้นสุด
• ตัวอย่าง: หากเชื่อมจุดบนวงกลมด้วยระยะห่างคงที่ เมื่อเป็น ระยะห่างเชิงตรรกยะ จะได้วงปิด แต่เมื่อเป็น ระยะห่างอตรรกยะ จะเกิดโครงสร้างการเชื่อมต่อแบบอนันต์
• หากระบายสีโหนดของกราฟด้วยสองสี การทำเช่นนั้นเป็นไปได้เมื่อใช้ สัจพจน์การเลือก (axiom of choice) แต่จะได้ เซตที่วัดไม่ได้
• ในทางกลับกัน หากใช้ วิธีระบายสีแบบต่อเนื่อง จะต้องใช้สามสี แต่จะได้ เซตที่วัดได้
• ความแตกต่างนี้เป็นปัจจัยสำคัญที่กำหนด ตำแหน่งในลำดับชั้นความซับซ้อนเชิงทฤษฎีเซต

การพบกันกับอัลกอริทึมแบบกระจาย

• ในปี 2019 Bernshteyn ได้ฟังบรรยายด้านวิทยาการคอมพิวเตอร์เกี่ยวกับ อัลกอริทึมแบบกระจาย (distributed algorithms) และสังเกตเห็นความคล้ายคลึงกัน
  • ตัวอย่าง: ปัญหาที่เราเตอร์ Wi‑Fi ต้องเลือก ความถี่ (สี) ที่ต่างกันเพื่อไม่ให้รบกวนกัน
• แต่ละโหนดใช้ อัลกอริทึมเฉพาะที่ (local algorithm) ในการกำหนดสี โดย สื่อสารได้เฉพาะกับโหนดข้างเคียง
• การใช้เพียงสองสีไม่มีประสิทธิภาพ แต่หากอนุญาตให้ใช้สามสี ก็สามารถแก้ปัญหาได้อย่างมีประสิทธิภาพ
• Bernshteyn ตระหนักว่า ค่าเกณฑ์ (threshold) ของจำนวนสี นี้ตรงกับ ค่าเกณฑ์ของปัญหาการระบายสีแบบวัดได้ ในทฤษฎีเซตเชิงพรรณนา

การพิสูจน์ความสมมูลกันของสองโลก

• Bernshteyn พิสูจน์ทางคณิตศาสตร์ถึงความสมมูลระหว่าง อัลกอริทึมเฉพาะที่ที่มีประสิทธิภาพ ↔ วิธีระบายสีแบบวัดได้
• ในกราฟจำกัด สามารถกำหนดหมายเลขเฉพาะให้แต่ละโหนดได้ แต่ใน กราฟอนันต์ที่นับไม่ได้ จะทำเช่นนั้นไม่ได้
• เขาออกแบบ วิธีติดป้ายกำกับที่ไม่ซ้ำกันระหว่างโหนดที่อยู่ติดกัน ทำให้อัลกอริทึมสามารถขยายไปใช้กับกราฟอนันต์ได้
• ผลลัพธ์คือมีการพิสูจน์ว่า “อัลกอริทึมเฉพาะที่ทุกตัวสอดคล้องกับวิธีระบายสีแบบวัดได้ในทฤษฎีเซตเชิงพรรณนา”
• สิ่งนี้เผยให้เห็นความเชื่อมโยงทางคณิตศาสตร์อย่างลึกซึ้งระหว่าง ความสามารถในการคำนวณ กับ ความสามารถในการนิยาม (definability)

การขยายงานวิจัยและการประยุกต์ใช้

• Václav Rozhoň และคณะใช้ความเชื่อมโยงนี้ในการแก้ ปัญหาการระบายสีกราฟต้นไม้ (tree) และได้เครื่องมือสำหรับ การวิจัยระบบพลวัต
• ในทางกลับกัน ก็มีงานวิจัยที่ใช้วิธีจากทฤษฎีเซตเพื่อปรับปรุง การประเมินความยากของปัญหา เช่นกัน
• สะพานนี้ไม่ได้เป็นเพียงเครื่องมือสำหรับแก้ปัญหาเท่านั้น แต่ยังมีส่วนช่วย จัดระเบียบระบบการจำแนกของทฤษฎีเซตใหม่
• ตอนนี้นักทฤษฎีเซตเชิงพรรณนาสามารถอ้างอิง วิธีการจัดหมวดหมู่อย่างเป็นระบบของวิทยาการคอมพิวเตอร์ เพื่อจัดระเบียบปัญหาที่ยังไม่ถูกจัดหมวดหมู่ได้
• Bernshteyn หวังว่างานวิจัยนี้จะเป็น จุดเปลี่ยนที่ทำให้แนวคิดเรื่องอนันต์ถูกมองว่าเป็นส่วนหนึ่งของคณิตศาสตร์เชิงปฏิบัติอย่างแท้จริง

[GN⁺]

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

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

  • นี่ไม่ใช่คำถามโง่เลยแม้แต่น้อย อินไซต์เชิงเทคนิค อาจนำไปสู่ ทฤษฎีบทความเป็นไปไม่ได้ แบบใหม่ในอัลกอริทึมแบบกระจายหรือทฤษฎีความซับซ้อนเชิงการคำนวณก็ได้ ความเป็นไปได้ในการประยุกต์ใช้กับสิ่งอย่าง mesh networking ก็น่าสนใจ

• คำพูดที่ว่า “คณิตศาสตร์สมัยใหม่ทั้งหมดสร้างอยู่บนทฤษฎีเซต” ฟันธงเกินไป เครื่องมือคณิตศาสตร์สมัยใหม่ อย่าง Lean หรือ Rocq กำลังพัฒนาบนฐานของ คณิตศาสตร์แบบทำให้เป็นรูปแบบทางการ (formalized mathematics) ซึ่งสร้างอยู่บน ทฤษฎีชนิด (type theory)

  • ผมไม่ใช่นักคณิตศาสตร์ แต่คิดว่า ZFC ก็ยังเป็นระบบรากฐานที่ใช้ได้อยู่ dependent types มีประโยชน์ในการจัดการการพิสูจน์ทฤษฎีบท แต่ไม่ได้ทำให้พิสูจน์ทฤษฎีบทได้มากขึ้น Isabelle/HOL ของ Lawrence Paulson ไม่ได้อิงชนิด แต่ก็พิสูจน์คณิตศาสตร์ได้เกือบทั้งหมด
  • แต่ในทางปฏิบัติ นักคณิตศาสตร์จริง ๆ แทบไม่ใช้คณิตศาสตร์แบบทำให้เป็นรูปแบบทางการ ต่อให้รู้จักก็ไม่ใช้เป็นภาษาพื้นฐานเพราะ ไม่สะดวก
  • อย่าสับสนระหว่าง ภาษา ของคณิตศาสตร์ กับ ภาษาทางการ ที่ใช้พิสูจน์เกี่ยวกับภาษานั้น อย่างแรกแทบทั้งหมดใช้เซต ส่วนอย่างหลังเลี่ยงไม่ได้ที่จะใช้ชนิด
  • ถ้าจะพูดให้แม่นกว่า ควรบอกว่าวิกฤตรากฐานของคณิตศาสตร์จบลงชั่วคราวด้วย การทำให้ทฤษฎีเซตเป็นรูปแบบทางการ

• เป็นการเล่นมุกคำว่า “cons’es all the way down” เพื่อเสียดสี โครงสร้างแบบเรียกซ้ำ

• รู้สึกซาบซึ้งกับประโยคที่ว่า “ในที่สุดเราก็คำนวณอนันต์ได้แล้ว”

  • เดือนหน้าใน Bay Area จะมีทัวร์ Calculating Infinity ของ The Dillinger Escape Plan ลิงก์งานแสดง เลยเอามาแชร์เพราะคิดว่าแฟนคณิตศาสตร์ แฮ็กกิง และ mathcore น่าจะทับซ้อนกัน
  • มีคนต่อมุกกับคำว่า “คำนวณอนันต์” ว่า “และเลยไปไกลกว่านั้น!”
  • ใน Haskell บอกว่าเขียนแค่ let x = x in x บรรทัดเดียวก็แทน อนันต์นับได้ (countable infinity) ได้แล้ว
  • เติมมุกด้วยมีม “Chuck Norris นับจาก 1 ถึงอนันต์มาแล้วสองรอบ”
  • เสริมด้วยคำประชดว่า “นี่ใช้เวลานานจริง ๆ /s”

• ไม่เห็นด้วยกับคำกล่าวที่ว่า “วิทยาการคอมพิวเตอร์จัดการเฉพาะสิ่งที่มีขอบเขตจำกัด” จริง ๆ แล้ว วิทยาการคอมพิวเตอร์เกี่ยวข้องกับอนันต์ อย่างลึกซึ้ง

  • Quanta มักนำเสนออะไรในลักษณะนี้บ่อย ๆ คือเน้นการเล่าแบบ วิทยาศาสตร์สำหรับคนทั่วไป โดยโฟกัสที่เรื่องราวของผู้คนและละรายละเอียดออกไป
  • แต่ก็จริงที่วิทยาการคอมพิวเตอร์สนใจ อนันต์นับไม่ได้ (uncountable infinity) น้อยกว่า ทฤษฎีการวัด (measure theory) จะเกี่ยวกับด้านนั้นมากกว่า
  • ตอนแรกผมก็คิดว่า “CS แค่อนุมานอนันต์” แต่จริง ๆ คำว่า การประมาณค่า (approximation) นี่แหละคือแก่นหลัก เราทำงานอยู่ภายใน ขอบเขตจำกัด เสมอ ต่อให้จักรวาลเป็นอนันต์ ช่วงที่เราสังเกตได้ก็ยังถูกจำกัดด้วย ความเร็วแสง
  • ประโยคแนว ๆ ว่า “วิทยาการคอมพิวเตอร์ไม่ใช้ตรรกะ” เป็นคำพูดที่ขี้เกียจเกินไป ตรรกะแบบบูลีน ก็คือหลักฐานตรงนั้นเลย

• ผมเรียนคณิตศาสตร์มานาน และเริ่มเชื่อว่า อนันต์ (infinity) ไม่มีอยู่จริง คิดว่าคณิตศาสตร์อาจดีกว่าถ้าไม่มีมัน

  • ผมเองก็เรียนคณิตศาสตร์แค่ระดับวิศวกรรม แต่คิดว่าอนันต์ ไม่ใช่ตัวเลขแต่เป็นกระบวนการ (process) “...” ใน {1, 2, 3, ...} หมายถึงกระบวนการขยายต่อไปไม่สิ้นสุด ไม่มีอะไรอย่าง จำนวนเฉพาะลำดับที่เป็นอนันต์ มีแค่ กฎการสร้าง ว่าจะมีจำนวนเฉพาะที่ใหญ่กว่าเสมอ
  • แต่ถ้าตัดอนันต์ออก คณิตศาสตร์จะ ซับซ้อนอย่างน่ากลัว ถ้าไม่ยอมให้จำนวนธรรมชาติขยายต่อไปเรื่อย ๆ การคำนวณจะไม่สะดวกมาก
  • คณิตศาสตร์สนใจ ประโยชน์เชิงแนวคิด มากกว่าการมีอยู่จริง วงกลมก็ไม่มีอยู่จริงในโลก แต่มีประโยชน์ ถ้าไม่มีอนันต์ เราก็คงต้องประดิษฐ์มันกลับมาใหม่ในรูปอย่าง “ลิมิตเมื่อ x เข้าใกล้จำนวนที่ใหญ่มาก ๆ มาก ๆ”
  • มีมุกว่า “ก็หยุดที่ 8 ไปเลยสิ” เพื่อเสียดสีความไม่จำเป็นของอนันต์
  • อนันต์ก็เป็นแค่ชื่อที่ใช้เรียกกระบวนการที่ไม่มีวันจบ บางกระบวนการโตเร็วกว่า จึงมี อนันต์ที่ใหญ่กว่า ได้ ส่วนตัวชอบแนวคิดเรื่องอนันต์ใน แบบจำลองทรงกลมรีมันน์ (Riemann sphere model)

• มีมุกว่า node_modules ได้เชื่อม คณิตศาสตร์ของอนันต์ เข้ากับระบบไฟล์ของผมแล้ว เป็นการเสียดสี การระเบิดของ dependencies

• โต้แย้งประโยคที่ว่า “คณิตศาสตร์สมัยใหม่ทั้งหมดสร้างอยู่บนทฤษฎีเซต” โดยชี้ว่ายังมี ทฤษฎีชนิด (Type Theory) ด้วย

  • Type Theory เป็น ระบบสัจพจน์ที่ทรงพลังกว่า ZFC ดูคำอธิบายที่ คำตอบบน MathOverflow
  • แต่ก็ยังไม่มี ชุดสัจพจน์ของทฤษฎีชนิด ที่มีอิทธิพลเทียบเท่า ZF หรือ ZFC
  • ในเชิงเทคนิค descriptive set theory แยกจากทฤษฎีเซตรากฐานอยู่แล้ว มันสร้างใหม่ได้ง่ายด้วยแนวคิดเรื่องชนิดและปริภูมิ ซึ่งหลายครั้งได้เปรียบกว่า การตีความอนันต์ทางคณิตศาสตร์ใหม่จาก มุมมองเชิงการคำนวณ ไม่ใช่เรื่องใหม่
  • คำอธิบายว่าเป็น “ศาสตร์ที่จัดระเบียบเซตของวัตถุนามธรรม” ทำให้ทฤษฎีเซตดูง่ายเกินไป ถึงอย่างนั้นก็ยังจริงที่คณิตศาสตร์ส่วนใหญ่ยังนิยามขึ้นจาก สัจพจน์ของเซต