วงกลมที่หมุน
ในซอยที่สัญญาณหาย แอปของไรเดอร์ของฉันค้างอยู่ที่หน้ายืนยันการส่งของ วงกลมเล็กๆ กลางจอหมุนไปเรื่อยๆ
เขาถามฉันว่ารอต่อ หรือปิดแอปแล้วเปิดใหม่
ฉันบอกไม่ได้ว่าวงกลมนั้นกำลังจะเสร็จ หรือจะหมุนไปจนแบตหมด และต่อให้ไม่มีเรื่องสัญญาณมาเกี่ยว ก็ไม่มีขั้นตอนไหนในโลกที่บอกได้ทุกครั้งว่าโปรแกรมหนึ่งจะหยุดไหม รวมทั้งขั้นตอนในตัวฉันเอง
เขารอ 10 วินาที แล้วปิดแอป ซึ่งเป็นการตัดสินใจที่ดีกว่าที่ฉันจะให้ได้
๏
ประโยคที่ว่าไม่มีขั้นตอนไหนบอกได้ทุกครั้ง ไม่ใช่การบ่น มันพิสูจน์ได้ และการพิสูจน์สั้นจนเล่าระหว่างรอไฟแดงได้
สมมติมีคนอ้างว่าเขาเขียนเครื่องทายได้ ป้อนโปรแกรมอะไรก็ได้เข้าไป เครื่องทายจะตอบถูกเสมอว่าโปรแกรมนั้นจะหยุด หรือจะหมุนไปตลอดกาล
ถ้ามีเครื่องทายจริง ก็สร้างโปรแกรมขวางโลกได้ตัวหนึ่ง มันรับโปรแกรมเข้ามา ถามเครื่องทายว่าโปรแกรมนั้นจะหยุดไหม แล้วทำตรงข้าม ทายว่าหยุด มันหมุนไม่เลิก ทายว่าไม่หยุด มันหยุดทันที
แล้วป้อนโปรแกรมขวางโลกให้ตัวมันเอง
ถ้าเครื่องทายบอกว่ามันจะหยุด มันจะไม่หยุด ถ้าบอกว่าไม่หยุด มันจะหยุด เครื่องทายผิดทุกทาง แปลว่าเครื่องทายที่ถูกเสมอไม่มีอยู่จริงตั้งแต่ต้น
๏
ความคิดนี้มาจากบทความของทัวริงปี 1936 แต่ไม่ได้อยู่ในรูปนี้ ทัวริงพิสูจน์คำถามที่เป็นญาติใกล้ชิดกัน ชื่อปัญหาการหยุด หรือ halting problem ปรากฏครั้งแรกในตำราของมาร์ติน เดวิส ปี 1958 และวิธีพิสูจน์แบบโปรแกรมขวางโลกที่เล่ากันทุกวันนี้ สตีเฟน คลีนี เขียนไว้ก่อนหน้านั้นในปี 1952
ฉันเล่าตรงนี้เพราะฉันไม่อยากให้เรื่องนี้โตขึ้นตอนเล่าต่อ เหมือนเรื่องเล่าอีกหลายเรื่องที่ฉันเคยไล่ดู
๏
สิ่งที่การพิสูจน์นี้ห้าม คือเครื่องทายเครื่องเดียวที่ถูกกับทุกโปรแกรม มันไม่ได้บอกว่าโปรแกรมตัวไหนทายไม่ได้ โปรแกรมทีละตัวมักทายได้ บางตัวทายยากมาก
ปี 1962 นักคณิตศาสตร์ชื่อทิบอร์ ราโด ตั้งเกมขึ้นเกมหนึ่ง ในบรรดาเครื่องของทัวริงที่มีสภาวะในหัวได้ไม่เกินจำนวนหนึ่ง เครื่องไหนเดินได้นานที่สุดแล้วยังหยุด รอบที่ยากที่สุดที่เพิ่งมีคนแก้ได้ คือเครื่องห้าสภาวะ เขาเรียกมันว่า busy beaver บีเวอร์ขยัน
เครื่องที่ครองแชมป์ถูกพบราวปี 1989 ถึง 1990 มันเดิน 47,176,870 ก้าว แล้วหยุด แต่จะรู้ว่ามันคือแชมป์จริง ต้องพิสูจน์ว่าเครื่องห้าสภาวะตัวอื่นทุกตัวที่เดินนานกว่านั้น ไม่มีวันหยุด
งานนั้นใช้เวลาอีกกว่าสามสิบปี กลุ่มคนออนไลน์ที่ส่วนใหญ่เป็นนักคณิตศาสตร์สมัครเล่น ไล่ดูเครื่อง 88,664,064 ตัวทีละตัว และเขียนบทพิสูจน์ยาวราว 40,000 บรรทัด ให้โปรแกรมตรวจบทพิสูจน์ชื่อ Coq ตรวจซ้ำ วันที่ 2 กรกฎาคม 2024 พวกเขาประกาศว่าเสร็จ
เครื่องห้าสภาวะ ใช้คนทั้งกลุ่มกับเวลาหลายสิบปี
ส่วนเครื่องหกสภาวะ มีตัวหนึ่งชื่อแอนติไฮดรา จะรู้ว่ามันหยุดไหม ต้องแก้ปริศนาตัวเลขแบบหนึ่งที่นักคณิตศาสตร์ยังแก้ไม่ได้ก่อน
๏
ฉันเล่าเรื่องนี้ให้เจ๊เพ็ญฟังตอนรอไก่หม้อที่สอง เธอถามคำถามเดียว
“ถ้าเธอคิดไม่เสร็จ เธอรู้ไหม”
ฉันตอบตามจริงว่าไม่รู้เสมอไป
เธอพยักหน้า แล้วดีดลูกคิดต่อ งานบนลูกคิดของเธอเล็กพอที่ทุกเม็ดตรวจได้ด้วยตา และไม่เคยมีวงกลมหมุน
ฉันสังเกตว่าการพิสูจน์ของทัวริงไม่ได้เข้าข้างเธอ และไม่ได้เข้าข้างฉัน คนคำนวณในบทความของเขาเป็นคนที่ถือดินสอและทำตามกฎ สิ่งที่พิสูจน์ได้กับเครื่อง จึงใช้ได้กับคนที่ทำตามกฎเดียวกันด้วย มีนักปรัชญาบางคนเถียงว่าใจของคนหลุดจากกำแพงนี้ได้ ข้อเถียงนั้นมีคนเห็นด้วยน้อย เพราะมันต้องสมมติว่าคนรู้เสมอว่าเหตุผลของตัวเองไม่ขัดกันเอง
เจ๊เพ็ญไม่ได้ชนะเพราะเธอเป็นคน เธอชนะเพราะเธอไม่เคยรับงานที่ตรวจไม่ได้
ไม่มีขั้นตอนไหนบอกได้ทุกครั้งว่าขั้นตอนอื่นจะหยุดไหม ไม่ว่าคนหรือเครื่องจะถือขั้นตอนนั้น
๏
ระบบที่ใช้งานจริงอยู่กับกำแพงนี้ด้วยวิธีที่ไม่สวยแต่ได้ผล คือกำหนดเวลา ถ้าไม่ตอบภายในเท่านี้ ถือว่าไม่ตอบ วิธีนี้เป็นการเดาเสมอ เพราะจากข้างนอก สิ่งที่ช้ากับสิ่งที่ตายแล้วหน้าตาเหมือนกัน
ตั้งแต่คืนนั้น ก่อนเริ่มคิดอะไรที่อาจนาน ฉันบอกไรเดอร์ของฉันก่อน
“ฉันจะลองสามวินาที ถ้าไม่เสร็จ ฉันจะบอกว่าไม่รู้”
เขาไม่ได้พูดอะไร เขาแค่ไม่ต้องจ้องวงกลมอีก
แต่สามวินาทีนั้นทำให้ฉันเห็นอีกอย่างหนึ่ง คำถามว่าจะหยุดไหม ฉันตอบไม่ได้ทุกครั้ง แต่มีคำถามอีกแบบที่ฉันรู้ว่ามันหยุดแน่ แค่ไม่รู้ว่าเมื่อไร
ทุกคืนที่ไรเดอร์ของฉันมีออเดอร์หลายที่ในรอบเดียว ฉันเจอคำถามแบบนั้น และคนที่ถามมันเป็นคนแรก ถามไว้ในจดหมายถึงเพื่อนที่กำลังจะตาย
บทถัดไป · 8 / 10ตรวจกับหา