ความเข้าใจผิดแบบซอมบี้ในวิทยาการคอมพิวเตอร์เชิงทฤษฎี
(scottaaronson.blog)- ความสามารถในการคำนวณ และ NP-hard ในวิทยาการคอมพิวเตอร์เชิงทฤษฎีเป็นแนวคิดที่ใช้กับฟังก์ชัน ภาษา และลำดับอนันต์ ไม่ใช่กับจำนวนเต็มแต่ละตัวหรือคำถามจริง/เท็จเพียงข้อเดียว
- ในตัวอย่างของ Sipser “ฟังก์ชัน f ที่คืนค่า 1 เสมอถ้าพระเจ้ามีอยู่จริง และคืนค่า 0 เสมอถ้าพระเจ้าไม่มีอยู่จริง” เป็นฟังก์ชันคงที่ทั้งสองกรณี จึง คำนวณได้
- P vs NP ไม่ใช่ปัญหาที่รับอินพุต แต่เป็นคำถามแบบใช่/ไม่ใช่เพียงข้อเดียว จึงไม่สามารถเรียกตัวมันเองว่า NP-hard หรือคำนวณไม่ได้
- ฟังก์ชัน Busy Beaver ทั้งหมดคำนวณไม่ได้ แต่ค่าเฉพาะอย่าง BB(6) ไม่สามารถปฏิบัติต่อในแบบเดียวกันได้ เพราะไม่ว่าจะเป็นจำนวนเต็มใด k ก็มีโปรแกรม
print kอยู่เสมอ - แก่นของความสับสนที่เกิดซ้ำคือการนำแนวคิดสำหรับวัตถุอนันต์ไปใช้กับปัญหาเฉพาะราย และนิสัยในการปนความคำนวณไม่ได้ของปัญหาการหยุดทำงานเข้ากับความไม่สมบูรณ์ของ Gödel ก็อยู่ในตระกูลเดียวกัน
ขอบเขตของความสามารถในการคำนวณที่ตัวอย่างของ Sipser สอนเรา
- ใน Introduction to the Theory of Computation ของ Michael Sipser มีโจทย์การบ้านที่เผยให้เห็นนิยามของความสามารถในการคำนวณ
- ให้ f:{0,1}*→{0,1} เป็นฟังก์ชันที่คืนค่า 1 เสมอถ้าพระเจ้ามีอยู่จริง และคืนค่า 0 เสมอถ้าพระเจ้าไม่มีอยู่จริง
- คำถามคือ f คำนวณได้ หรือไม่ และคำตอบไม่เกี่ยวข้องกับความเชื่อทางศาสนา
- f คำนวณได้
- ฟังก์ชันคงที่ที่คืนค่า 1 เสมอคำนวณได้
- ฟังก์ชันคงที่ที่คืนค่า 0 เสมอก็คำนวณได้
- ถ้า f เป็นหนึ่งในสองแบบนี้ f ก็ย่อมคำนวณได้เช่นกัน
- คำถามคู่ขนานที่มีโครงสร้างแบบเดียวกันก็ให้สัญชาตญาณเดียวกัน
- ในคำถามว่า “ถ้าพระเจ้ามีอยู่จริง n=3 ไม่เช่นนั้น n=5 แล้ว n เป็นจำนวนเฉพาะหรือไม่” แม้ n จะยังไม่ถูกระบุอย่างสมบูรณ์ เราก็ยังบอกได้ว่าเป็น จำนวนเฉพาะ จากข้อมูลเพียงว่าเป็นสมาชิกของ {3,5}
- f ก็เช่นเดียวกัน มันเพียงแค่ยังไม่แน่ว่าเป็นฟังก์ชันคงที่ตัวไหนในสองตัวนี้ แต่ถูกระบุไว้มากพอแล้วที่จะตัดสินได้ว่าคำนวณได้
ความสามารถในการคำนวณไม่ใช่ความยากในการเขียนโปรแกรม แต่คือการมีอยู่ของโปรแกรม
- ความสามารถในการคำนวณเป็นแนวคิดที่ใช้กับฟังก์ชันหรือลำดับอนันต์
- เราไม่ใช้ความสามารถในการคำนวณกับคำถามแบบใช่/ไม่ใช่เฉพาะข้อ หรือจำนวนเต็มเฉพาะตัว ในแบบเดียวกัน
- คำถามสำคัญคือมีโปรแกรมคอมพิวเตอร์ที่แมปอินพุตไปยังเอาต์พุตนั้น อยู่หรือไม่
- ความยากแค่ไหนในการเลือก หา หรือเขียนโปรแกรมนั้น ไม่ได้เป็นส่วนหนึ่งของนิยามความสามารถในการคำนวณ
- ต่อให้การจะเขียนโปรแกรมต้องแก้เรื่องการมีอยู่ของพระเจ้าก่อน การตัดสินว่าคำนวณได้หรือไม่ก็ไม่เปลี่ยนไป
เหตุใดจึงเรียก P vs NP ว่า NP-hard ไม่ได้
- คำถามว่า “ตัวคำถาม P versus NP เองเป็น NP-hard จึงแก้ไม่ได้หรือไม่” ถูกถามซ้ำมาหลายครั้งในช่วง 25 ปีที่ผ่านมา
- NP-hard ใช้กับฟังก์ชันหรือภาษาที่รับอินพุต เช่น 3SAT, Independent Set, Clique
- อินพุตอาจเป็น Boolean formula, graph เป็นต้น
- เอาต์พุตคือคำตอบสำหรับอินพุตนั้น
- ถ้าปัญหาใดแก้ได้ในเวลาพหุนาม และด้วยการรีดักชันทำให้ทุกภาษาหรือฟังก์ชันใน NP ก็แก้ได้ในเวลาพหุนามด้วย ปัญหานั้นจึงเรียกว่า NP-hard
- P vs NP ไม่ใช่ฟังก์ชันหรือภาษา แต่เป็นคำถามแบบใช่/ไม่ใช่เพียงข้อเดียว
- เป็นไปได้ที่คำตอบของมันจะเป็นอิสระจากสัจพจน์ของทฤษฎีเซต Zermelo-Fraenkel
- แต่เราไม่สามารถบอกได้ว่าตัวคำถามนี้เองคำนวณไม่ได้หรือเป็น NP-hard
- ในเชิงรูปแบบแล้ว มีโปรแกรมที่ตอบคำถาม P vs NP ได้อย่างถูกต้องและรวดเร็วอยู่
- ถ้า P=NP ก็มีโปรแกรมที่พิมพ์ “P=NP”
- ถ้า P≠NP ก็มีโปรแกรมที่พิมพ์ “P≠NP”
ความสับสนแบบเดียวกันที่เกิดซ้ำใน Busy Beaver
- ในคอมเมนต์ของบทความที่ประกาศว่าค่า Busy Beaver 5 ถูกตัดสินแล้ว ก็มีคำถามลักษณะคล้ายกันซ้ำอยู่
- “ค่า n ที่น้อยที่สุดซึ่งทำให้ค่าของ BB(n) คำนวณไม่ได้คืออะไร”
- “BB(6) อาจคำนวณไม่ได้แล้วหรือไม่”
- ฟังก์ชัน Busy Beaver คำนวณไม่ได้
- แต่กับจำนวนเต็มเฉพาะอย่าง BB(6) เราไม่ใช้แนวคิดเรื่องความสามารถในการคำนวณแบบนั้น
- ไม่ว่า BB(6) จะถูกพบว่าเป็นจำนวนเต็มใด k ก็ย่อมมีโปรแกรม
print k - โปรแกรมนี้จะพิมพ์จำนวนนั้นออกมา
- ไม่ว่า BB(6) จะถูกพบว่าเป็นจำนวนเต็มใด k ก็ย่อมมีโปรแกรม
- คำถามที่ถามได้จริงคือ สำหรับ n ใดบ้างที่ค่าของ BB(n) พิสูจน์ไม่ได้ ภายในระบบสัจพจน์อย่างทฤษฎีเซต ZF
- Aaronson และ Adam Yedidia ศึกษาคำถามนี้ในปี 2016
- สถิติปัจจุบันคือ n=745 ซึ่งปรับปรุงจากค่า n=8000 ของ Aaronson และ Adam
- จำนวนเต็มเฉพาะทุกตัวถือได้ว่า “คำนวณได้” และสิ่งที่คำนวณไม่ได้คือฟังก์ชัน BB ทั้งหมด
เหตุใด “ความเข้าใจผิดแบบซอมบี้” จึงยังฟื้นกลับมาเสมอ
- แก่นของความสับสนที่เกิดซ้ำคือการนำแนวคิดที่ออกแบบมาสำหรับลำดับอนันต์และฟังก์ชัน ไปใช้ผิดกับจำนวนเต็มเฉพาะตัวและปัญหาที่ยังเปิดอยู่
- กรณีที่ปนความคำนวณไม่ได้ของปัญหาการหยุดทำงานเข้ากับความไม่สมบูรณ์ของ Gödel ก็เป็นความสับสนประเภทเดียวกัน
- ทั้งสองอย่างเกี่ยวข้องกันอย่างใกล้ชิด
- Gödel ทำให้เราพูดถึงประพจน์เฉพาะข้อได้
- ส่วนความสามารถในการคำนวณแบบทัวริงไม่ใช่แนวคิดที่สัมพัทธ์กับระบบสัจพจน์ใดระบบหนึ่ง แต่เป็นแนวคิดแบบสัมบูรณ์
- คำอธิบายนี้ทำหน้าที่เป็นจุดอ้างอิงที่เชื่อมโยงได้เมื่อความเข้าใจผิดเชิงการสอนแบบเดิมกลับมาอีก
- คำถามสุดท้ายมุ่งไปที่ว่าจะทำอย่างไรให้ความเข้าใจผิดแบบ “ซอมบี้” นี้สงบลงได้
1 ความคิดเห็น
ความคิดเห็นบน Hacker News
การที่แนวคิดเรื่อง ความสามารถในการคำนวณได้ จำเป็นต้องรวมอนันต์เข้าไปด้วย อาจค่อนข้างขัดกับสัญชาตญาณ
เช่น ถ้าถามว่ามีอัลกอริทึมที่คำนวณความซับซ้อนของคอลโมโกรอฟ K(s) สำหรับสตริง s ใด ๆ หรือไม่ คำตอบก็เป็นที่รู้กันดีว่า “ไม่มี” ไม่มีเครื่องทัวริงที่รับสตริงความยาวใด ๆ เป็นอินพุตแล้วคำนวณ K(s) ได้ และพิสูจน์ได้สั้น ๆ ด้วยปัญหาการหยุดทำงาน
แต่ถ้าถามว่ามีอัลกอริทึมที่คำนวณ K(s) สำหรับสตริง s ใด ๆ ที่มีความยาวน้อยกว่า n หรือไม่ คำตอบคือ “มี” สำหรับ n ใด ๆ ก็มีอัลกอริทึมเช่นนั้นอยู่
วิธีการนั้นน่าผิดหวังคือสร้างเครื่องทัวริงที่มี ตารางค้นหา ขนาดมหึมา ซึ่งเก็บค่า K(s) สำหรับสตริงที่เป็นไปได้ทั้งหมด 2^n ตัว ก็พอ ส่วนจะหาตารางนั้นจริง ๆ ได้อย่างไรเป็นอีกเรื่องหนึ่ง และเพราะ implementation เฉพาะใด ๆ มีคำอธิบายที่จำกัด และ K(s) ก็มีค่าจำกัดสำหรับทุก s ดังนั้นอัลกอริทึมจึงมีอยู่
ดังนั้นคำถามแบบจำกัดเกี่ยวกับวัตถุจำกัด อาจไม่ค่อยน่าสนใจนักในมุมของความสามารถในการคำนวณได้ เพราะเราสามารถเขียนโปรแกรมที่พิมพ์คำตอบทั้งหมดออกมาได้เสมอ และเมื่อคำถามขยายไปยังเซตของวัตถุที่เป็นอนันต์ เมื่อนั้นจึงเริ่มน่าสนใจว่าอะไรบางอย่างที่มีขนาดจำกัดจะตอบคำถามอนันต์เหล่านั้นได้หรือไม่
ในความเป็นจริง อนันต์ ทำหน้าที่แทน “พฤติกรรมโดยประมาณ/ท้ายที่สุด/สภาวะคงตัวเมื่อ N ใหญ่พอจนเหนือกว่ากลเม็ดเฉพาะครั้งใด ๆ”
ในโลกจริง กลเม็ดแบบนั้นก็สำคัญ และค่าคงที่กับพจน์ลำดับต่ำที่ถูกมองข้ามในการเปรียบเทียบ Big-O ก็สำคัญต่อประสิทธิภาพจริงเช่นกัน มีความตึงเครียดอยู่เสมอระหว่าง “ปัญหาที่ใหญ่พอจนปัจจัยคงที่ไม่มีความหมาย” กับ “ปัญหาที่เล็กพอให้อยู่ในขอบเขตที่คำว่าค่าคงที่สื่อเป็นนัย” เช่น กรณีที่จำนวนเต็ม 32 บิตทำทีเป็นจำนวนเต็ม
จากมุมมองของอนันต์ จำนวนจำกัดทั้งหมดนั้นจริง ๆ แล้วเล็กมาก หากนั่งอยู่บนเก้าอี้ที่ปลายจักรวาล ระยะ 1 ไมล์ก็ไม่ต่างจาก 1 มิลลิเมตร
สถานการณ์นี้แทบจะเหมือน “โรงแรมอนันต์ของ Hilbert บนคอมพิวเตอร์” เพียงเลื่อนโปรแกรมเดิม ๆ ไปคนละหนึ่งห้อง ก็เพิ่มโปรแกรมใหม่ได้ และขนาดตารางที่ต้องใช้ในการคำนวณก็ยังเท่าเดิม
หากกล่าวให้ทั่วไปขึ้น คนส่วนใหญ่มีสัญชาตญาณที่อ่อนแอว่าอนันต์ อาเลฟ และคณิตศาสตร์เชิงอนันต์ยิ่งยวดทำงานอย่างไร ความเกี่ยวข้องในชีวิตประจำวันก็ต่ำ และมันพัวพันอย่างลึกซึ้งกับคุณสมบัติอุบัติใหม่ของคณิตศาสตร์ รวมถึงทฤษฎีหมวดหมู่และทฤษฎีเซต ไม่ใช่แค่อนันต์ใหญ่กว่าจำนวนจำกัดใด ๆ เท่านั้น แต่อนันต์บางแบบอาจใหญ่กว่าอนันต์อีกแบบได้ด้วย ซึ่งไม่เห็นได้ทันทีจากสัญชาตญาณที่หยุดอยู่แค่แนวคิด “อนันต์” แบบประถม
คำถามที่น่าสนใจกว่าคือมี n < ∞ ใด ๆ ที่ทำให้อัลกอริทึมนั้นคำนวณได้หรือไม่ ซึ่งแน่นอนว่าคำตอบคือไม่ และรางวัลทัวริงก็ลอยหายไป
แนวคิดคือแจกแจงเครื่องทัวริงที่เป็นไปได้ทั้งหมดจากความยาวสั้นไปยาว แล้วหาเครื่องที่พิมพ์ s ออกมา ถ้าลองเครื่องที่สั้นกว่าทั้งหมดแล้วและไม่มีเครื่องใดพิมพ์ s แสดงว่าเจอเครื่องที่สั้นที่สุดที่พิมพ์ s แล้ว ดังนั้นความยาวของมันคือ K(s) เครื่องอื่นที่ยาวเท่ากันหรือยาวกว่าอาจพิมพ์ s ได้เช่นกัน แต่ K(s) เป็นค่าของความยาวขั้นต่ำจึงไม่เปลี่ยน
จากประสบการณ์ของผม ในเรื่องนี้ คณิตศาสตร์คอนสตรักติวิสต์ เข้ากับสัญชาตญาณของผู้คนมากกว่าวิทยาการคอมพิวเตอร์แบบคลาสสิก
ตัวอย่างเช่น เรายังไม่มีการพิสูจน์เชิงคอนสตรักทีฟว่ามีโปรแกรมที่พิมพ์คำตอบของปัญหา P=NP ออกมา
ในวิทยานิพนธ์ของผมก็เคยพูดถึงปัญหานี้เกี่ยวกับเซต Julia ที่คำนวณได้ Mark Braverman พิสูจน์ว่าเซต Julia ดีกรีสองทั้งหมดคำนวณได้ แต่เขาเองก็อธิบายว่าการพิสูจน์นั้นคำนวณได้แบบไม่สม่ำเสมอ แทนที่จะมีเครื่องเดียว เขาสร้างเครื่อง 5 เครื่องที่รับพารามิเตอร์ของเซต Julia ที่ต้องการ แล้วพยายามวาดหลายเซตด้วยความละเอียดที่ต้องการ และสำหรับเซต Julia แต่ละชุด จะมีหนึ่งในนั้นที่วาดได้ถูกต้อง
ในคณิตศาสตร์คอนสตรักติวิสต์ แนวคิดเชิงคอนสตรักทีฟของเซตกะทัดรัดสอดคล้องโดยประมาณกับเซตที่คำนวณได้ในความหมายที่จำเป็นสำหรับเซต Julia ที่คำนวณได้ แต่ไม่สามารถพิสูจน์แบบคอนสตรักทีฟได้ว่าเซต Julia ดีกรีสองทั้งหมดเป็นเซตกะทัดรัด ต้องแบ่งระนาบเชิงซ้อนของพารามิเตอร์ที่เป็นไปได้ออกเป็นหลายบริเวณ แล้วพิสูจน์ว่าเซต Julia เหล่านั้นกะทัดรัดภายในแต่ละบริเวณ
ในคณิตศาสตร์คลาสสิก ยูเนียนของบริเวณเหล่านี้คือระนาบเชิงซ้อนทั้งหมด แต่ในคอนสตรักติวิสต์ผลลัพธ์นี้ไม่เป็นจริง เช่นเดียวกัน ในคณิตศาสตร์คลาสสิก ยูเนียนของจำนวนจริงบวกกับจำนวนจริงที่ไม่เป็นบวกคือเส้นจำนวนจริงทั้งหมด แต่ในคอนสตรักติวิสต์ก็ไม่เป็นจริงเช่นกัน
แนวทางคอนสตรักติวิสต์บอกเราอย่างแม่นยำว่าต้องมีข้อมูลเพิ่มเติมอะไรจึงจะทำให้การคำนวณเกิดขึ้นได้จริง กล่าวคือ ต้องบอกให้ได้ว่าพารามิเตอร์ที่ให้มาอยู่ในบริเวณใดของระนาบเชิงซ้อน แล้วจึงจะรู้ว่าควรรันเครื่องใดใน 5 เครื่องเพื่อให้ได้ภาพที่ต้องการ วิธีนี้ให้ความรู้สึกว่าเป็นคำตอบที่น่าพอใจกว่ามาก
ผู้คนรู้โดยสัญชาตญาณว่าต้องรู้ว่าอยู่ฝั่งไหนของเงื่อนไขใน branching statement และเพียงแต่ไม่ได้ถูกฝึกด้วยตรรกะคลาสสิกจนลืมข้อเท็จจริงนั้นไป
และก็สงสัยด้วยว่า สำหรับคำถามว่า “ใน 5 เครื่องนั้น เครื่องไหนถูก” ควรมองว่ามีการพิสูจน์บางอย่างที่ยังหาไม่เจออยู่หรือไม่ หรือควรมองว่าตัดสินไม่ได้เหมือนใน ZFC
ผมมองว่านี่เป็นหนึ่งในปัจจัยที่ทำให้เข้าใจ ความตัดสินไม่ได้ของปัญหาการหยุด ได้ยาก
เราอยากพูดว่า “มีเครื่องบางเครื่องที่ซับซ้อนเกินกว่าจะบอกได้ว่าเครื่องใดจะหยุดหรือไม่หยุด” แต่ในบรรดาโปรแกรมง่าย ๆ อย่าง
return trueกับreturn falseโปรแกรมหนึ่งในสองนี้จะให้คำตอบที่ถูกเสมอ ไม่ว่าจะโยนเครื่องและอินพุตใดเข้าไปก็ตามคุณอาจอยากโต้ว่า “โปรแกรมพวกนั้นไม่รู้อะไรเกี่ยวกับ Turing machine เลย จึงควรถูกตัดออก” แต่ความตัดสินได้ไม่ได้พูดถึงเรื่องนั้น คุณอาจคิดว่า “สิ่งที่ตัดสินไม่ได้คือการหาว่าโปรแกรมใดในสองโปรแกรมนั้นถูกต้อง” แต่เรื่องนั้นก็มีคำตอบที่กำหนดแน่นอนว่าเป็นจริงหรือเท็จ ปัญหาจะตัดสินไม่ได้ก็ต่อเมื่อขยายไปยังเซตอนันต์ของคู่เครื่อง/อินพุตเท่านั้น
ตัวอย่างเช่น ปริภูมิเวกเตอร์มิติจำกัดใด ๆ ย่อมไอโซมอร์ฟิกกับปริภูมิคู่และปริภูมิคู่ซ้ำของมันได้หลายวิธี แต่สำหรับกรณีหลัง เราสามารถเลือกไอโซมอร์ฟิซึมที่ “เป็นธรรมชาติ” และสอดคล้องกันครอบคลุมปริภูมิทั้งหมดเหล่านั้นได้ ขณะที่สำหรับกรณีแรกทำเช่นนั้นไม่ได้
จึงเกิดความสับสนทำนองว่า “ทำไมถึงไม่ไอโซมอร์ฟิกกันอย่างเป็นธรรมชาติ? ความยาวของฐานก็เท่ากันนี่! จะขึ้นกับฐานหรือไม่แล้วทำไมต้องสนใจ? แล้วทำไมบทพิสูจน์อื่น ๆ ถึงเลือกฐานได้โดยไม่เป็นไร?”
ผมมองว่าปัญหาของถ้อยคำคือมันต้องใช้ ตรรกศาสตร์เชิงโมดัล
“ถ้าพระเจ้ามีอยู่ ให้ f:{0,1}*→{0,1} เป็นฟังก์ชันค่าคงที่ 1; ถ้าพระเจ้าไม่มีอยู่ ให้เป็นฟังก์ชันค่าคงที่ 0. f คำนวณได้หรือไม่? คำใบ้: คำตอบไม่ได้ขึ้นกับความเชื่อทางศาสนา”
คำถามที่แม่นยำคือ f จะคำนวณได้หรือไม่ กล่าวคือ มี Turing machine M ที่ทำให้ f(x)=M(x) สำหรับทุก x หรือไม่
คำตอบคือมี เพราะไม่ว่าอยู่ในโลกใดก็มี Turing machine ง่าย ๆ อย่าง M=1_M หรือ M=0_M อยู่ ตรงกันข้าม สำนวนเดิมอย่าง “f คำนวณได้หรือไม่” เป็นคำถามที่ผิดในเชิงโมดัล และใกล้กับคำถามที่ไม่ถูกต้องทางไวยากรณ์แบบปริศนา Sleeping Beauty หรือ Red Envelope
อีกมุมหนึ่งคือ การพึ่งพาพระเจ้าหรือข้อเท็จจริงบางอย่างที่อาจเป็นจริงได้นั้นคล้ายกับคำสั่งคอมไพเลอร์หรือ pragma ที่จะถูกเติมในภายหลัง แต่ถูกกำหนดก่อนใช้งาน ถ้าถามให้ถูก ก็เป็นเพียงโจทย์ที่คลี่นิยามอย่างเคร่งครัดของฟังก์ชันและความคำนวณได้ ซึ่งทั้งสองอย่างถูกนิยามไว้อย่างชัดเจนใน Sipser
แต่มันหมายความว่า สิ่งที่ ป้ายชื่อ f อ้างถึงจะเป็นฟังก์ชันค่าคงที่ 1 ถ้าพระเจ้ามีอยู่ และเป็นฟังก์ชันค่าคงที่ 0 ถ้าพระเจ้าไม่มีอยู่ เพียงแต่เรายังไม่รู้ว่าเป็นฝั่งไหนจนกว่าจะรู้ว่าพระเจ้ามีอยู่หรือไม่ ความคำนวณได้ของฟังก์ชันค่าคงที่ทั้งสองนั้นชัดเจนอยู่แล้ว ดังนั้นจริง ๆ แล้วมันใกล้กับปัญหาเรื่องป้ายชื่อมากกว่าปัญหาเรื่องความคำนวณได้
เมื่อคิดว่าข้อเท็จจริงที่ทฤษฎีความน่าจะเป็นใช้กับความเป็นจริงได้เองนั้นลึกลับมาก และเป็นหัวข้อของการสืบค้นทางวิทยาศาสตร์และปรัชญาหลายแขนง ก็ไม่น่าแปลกใจ
วิธีแก้ที่เสนอในรูป “would f be” ก็ดูไม่ได้ช่วยแก้อะไรมากนัก จุดประสงค์ของคำถามเรื่อง “พระเจ้า” คือทำให้ผู้อ่านหลุดจากปัญหา P-NP เฉพาะหนึ่ง ๆ และเข้าใจว่า สำหรับฟังก์ชันค่าคงที่ แนวคิดเรื่องความคำนวณได้นั้นไม่มีประโยชน์ หากข้อเสนอนี้จะช่วยได้ มันก็ควรนำไปใช้กับคำถาม P-NP เดิมได้ด้วย แต่ผมยังไม่เห็นว่าแนวทางเชิงโมดัลจะเข้ามาเกี่ยวกับคำถามคณิตศาสตร์ที่นิยามไว้ดีแล้วได้อย่างไร
“ถ้าพระเจ้ามีอยู่ ให้ f:{0,1}→{0,1} เป็นฟังก์ชันค่าคงที่ 1 และถ้าพระเจ้าไม่มีอยู่ ให้ f:{0,1}→{0,1} เป็นฟังก์ชันค่าคงที่ 0”
ส่วนภาคแสดงเช่นนั้นสอดคล้องกับแนวคิดเรื่องพระเจ้าของเจ้าตัวหรือไม่ เป็นประเด็นนอกคณิตศาสตร์อีกเรื่องหนึ่ง
คล้ายกับเวลาผู้คนประหลาดใจเมื่อเรียนรู้ว่าในตรรกะคลาสสิก ประพจน์เท็จย่อมนำไปสู่ทุกสิ่งได้ คณิตศาสตร์มีกฎเชิงรูปแบบที่เข้มงวด และสิ่งสำคัญคือต้องวางอคติเกี่ยวกับความหมายในชีวิตประจำวันของคำอย่าง “สื่อความว่า” หรือ “ถ้า” ลงเสีย
เช่น กำหนด G:t∈ℝ⁺->{0,1} ให้เป็น 1 ถ้าพระเจ้ามีอยู่ ณ เวลา t และเป็น 0 ถ้าไม่เช่นนั้น
แน่นอนว่า ถ้าวิเคราะห์ G ในกรอบอ้างอิงที่ไม่เฉื่อย ก็จะยิ่งน่าสนใจขึ้น
Sipser กำลังใช้ประโยชน์จากข้อเท็จจริงที่ว่าคนส่วนใหญ่ไม่ค่อยแยกความแตกต่างระหว่าง การคำนวณ กับการสืบค้นเชิงประจักษ์
“พระเจ้ามีอยู่หรือไม่” อาจเป็นคำถามที่ตอบไม่ได้ก็ได้ แต่นั่นไม่ใช่ประเด็น การหาคำตอบนั้นตั้งแต่แรกก็ไม่ใช่ขอบเขตของการคำนวณ การคำนวณเป็นเพียงกระบวนการที่แมปอินพุตเป็นเอาต์พุต และในกรณีนี้ การมีอยู่ของพระเจ้าคืออินพุตหนึ่ง
สิ่งที่ทำให้สับสนคือเราไม่อาจรู้ค่าอินพุตจริง ๆ ได้ แต่โปรแกรมก็ยังมีอยู่ และเป็นโปรแกรมที่ง่ายมากด้วย จะเปลี่ยนเป็นคำถามเชิงประจักษ์แบบไบนารีอื่นก็ได้
เช่น ให้ f:{0,1}* -> {0,1} เป็น “ถ้าใน Paris มีห้องน้ำเคลื่อนที่อย่างน้อยหนึ่งห้อง ให้เป็น 1 ไม่เช่นนั้นเป็น 0” สิ่งนี้คำนวณได้ และยังรันจริงด้วยอินพุตที่เป็นจริงได้ด้วย ฟังก์ชันเกี่ยวกับพระเจ้าก็คำนวณได้เช่นกัน เพียงแต่รันได้ด้วยอินพุตที่คาดเดาเท่านั้น แม้จะรับประกันไม่ได้ว่าเอาต์พุตจะสอดคล้องอย่างมีความหมายกับเอกภพที่เราอาศัยอยู่ แต่มันก็ยังเป็นฟังก์ชันที่คำนวณได้
จะมองให้ง่ายกว่านั้น แค่คิดถึง f:{0,1}* -> {0,1} ก็พอ “พระเจ้ามีอยู่” และ “พระเจ้าไม่มีอยู่” ต่างก็เป็นสตริงบิตที่เป็นไปได้ ถ้าถามว่ามีโปรแกรมที่รับหนึ่งในสองอย่างนี้เป็นอินพุตแล้วส่งออก 0 และรับอีกอย่างแล้วส่งออก 1 ได้หรือไม่ คำตอบก็แน่นอนว่าได้ ไม่เกี่ยวว่าอินพุตนั้นจริงหรือเท็จในเชิงประจักษ์
f ในคำถามไม่ใช่ฟังก์ชัน แต่เป็น ป้ายชื่อ ถ้าพระเจ้ามีอยู่ สิ่งที่ f อ้างถึงคือ f1 ที่ส่งออก 1 เสมอ และถ้าพระเจ้าไม่มีอยู่ ก็จะเป็น f0 ที่ส่งออก 0 เสมอ ดังนั้นจริง ๆ แล้วนี่ไม่ใช่ปัญหาเรื่องความคำนวณได้ แต่เป็นปัญหาเรื่องป้ายชื่อ
เรื่องแบบนี้เกิดขึ้นอยู่เสมอ เพราะนักคณิตศาสตร์และนักวิทยาการคอมพิวเตอร์ใช้ สำนวนย่อ ที่ละรายละเอียดไว้เพื่อความสะดวกในการสนทนา
ก็ไม่ต่างจากการพูดว่า “คูณทั้งสองข้างด้วย dx” คำถามว่า “ปัญหาเซลส์แมนเดินทางเป็น NP-hard หรือไม่?” หมายถึงตระกูลของปัญหา ไม่ใช่อินสแตนซ์เฉพาะอันเดียว ถ้าตรึงกราฟเฉพาะไว้ ก็ไม่มี N อยู่แล้ว จึงย่อมไม่ใช่ NP-hard
ถ้ารู้เรื่องนี้ มันก็ชัดเจนเกินกว่าจะคุ้มค่าพูดถึง แต่สำหรับคนที่ไม่รู้ความหมายของคำศัพท์ มันแทบเข้าถึงไม่ได้เลย
ในอดีตฉันเองก็เคยมีความเข้าใจผิดในรูปแบบคล้ายกันในสาขาอื่น เคยมอง DNA เหมือนโค้ด และเชื่อว่าสิ่งต่าง ๆ ที่ส่งข้อความกันผ่าน substrate โดยตรงหรือโดยการแก้ไข DNA กำลังรันโค้ดนั้นอยู่ โดยรวมแล้วโมเดลนี้ไม่ได้ไร้ประโยชน์โดยสิ้นเชิง แต่ต้องรู้ว่าเมื่อไรไม่ควรยึดติดกับโมเดลนั้นมากเกินไป
สำหรับนักชีววิทยาที่มีพื้นฐานคณิตศาสตร์ การมอง DNA ตรง ๆ ว่าเป็นโมเดลการรันของเครื่องทัวริงนั้นผิดอย่างชัดเจน แต่สำหรับฉันตอนนั้นไม่ใช่แบบนั้น สุดท้ายแล้วมันเป็นปัญหาที่มาจากความไม่คุ้นเคยกับความรู้พื้นฐาน
คำอย่าง decidability, computability, existence หรือแม้แต่คำว่าผลไม้ มีความหมายต่างกันในบริบทวิชาการกับบริบทชีวิตประจำวัน ถ้านำสัญชาตญาณจากความหมายในชีวิตประจำวันเข้าไปใช้ในบริบทวิชาการ ก็จะเกิด “คำถามโง่ ๆ” แบบนี้ขึ้น
จำนวนขนาดใหญ่มากบางจำนวนที่อยู่ใน Wikipedia นั้น “มีอยู่” และ “คำนวณได้” ในความหมายเชิงวิชาการ แต่จำนวนหลักของมันไม่สามารถบรรจุอยู่ในเอกภพของเราได้
ถ้าไม่อ่านอย่างระมัดระวัง ถ้อยคำอาจทำให้สับสนได้
ในประโยค “ถ้าพระเจ้ามีอยู่ ให้ f:{0,1}*→{0,1} เป็นฟังก์ชันค่าคงที่ 1 และถ้าพระเจ้าไม่มีอยู่ ให้เป็นฟังก์ชันค่าคงที่ 0 แล้ว f คำนวณได้หรือไม่?” ทางเลือกเหล่านั้นไม่ใช่ส่วนหนึ่งของฟังก์ชัน
ฟังก์ชัน f ไม่ได้ branch ตามค่าของ “พระเจ้ามีอยู่” แต่การ branch อยู่ใน ภาษาเมตา เราไม่รู้ว่า f=0 หรือ f=1 แต่ไม่ว่าจะเป็นฝั่งไหน ฟังก์ชันที่เป็นไปได้ทั้งสองแบบก็คำนวณได้ ดังนั้น f ก็คำนวณได้
ยิ่งไปกว่านั้น แม้ f จะมีการ branch นั้นอยู่จริง และโดเมนของฟังก์ชันเป็น 0 (พระเจ้าไม่มีอยู่) กับ 1 (พระเจ้ามีอยู่) ก็ยังเป็นฟังก์ชันที่คำนวณได้ในความหมายที่ว่าสามารถคำนวณผลลัพธ์สำหรับแต่ละค่าของโดเมนได้
แก่นของความสับสนอยู่ที่การยัดตัวแปรอิสระซึ่งถือว่ายังไม่รู้ค่า เข้าไปเป็นเงื่อนไขการ branch ภายใน f
ฉันยินดีจะคัดค้านตัวอย่างที่ว่า “ถ้าพระเจ้ามีอยู่ ให้ n=3 และถ้าพระเจ้าไม่มีอยู่ ให้ n=5 แล้ว n เป็นจำนวนเฉพาะหรือไม่?”
ตรงนี้กำลังใช้ กฎตัดกลาง เพื่ออ้างว่า n เป็น 3 หรือ 5 แต่ไม่มีการให้เหตุผลว่ากฎตัดกลางใช้ได้กับประพจน์ “พระเจ้ามีอยู่”
ในกรณีนี้ ถ้าจะตั้งคำถามว่ากฎตัดกลางมีเหตุผลรองรับหรือไม่ ก็ต้องให้เหตุผลด้วยว่าทำไมถึงหยิบเฉพาะกฎตัดกลางมาเป็นปัญหา ทำไมไม่ทิ้งหลักการระเบิดไปด้วยแล้วทำงานใน paraconsistent logic? Kolmogorov ก็เห็นว่าสัจพจน์นี้มีปัญหาร้ายแรง และในตอนแรกมองว่ามันเข้ากันไม่ได้กับตรรกะแบบสร้างสรรค์นิยม
นอกจากนี้ ขึ้นอยู่กับการจัดรูปแบบอย่างแม่นยำของประพจน์นี้ อาจไม่จำเป็นต้องใช้กฎตัดกลางเสมอไปก็ได้
พระเจ้าอาจไม่จำเป็นต้องถูกผูกมัดด้วยกฎฟิสิกส์หรือความจำเป็นเชิงตรรกะพื้นฐาน แนวคิดเรื่องพระเจ้าแบบนั้นมาจากสายการให้เหตุผลทางเทววิทยาบางสาย ไม่ใช่กรณีทั่วไป
หากต้องการ พระเจ้าก็อาจทำให้ 6 เป็นจำนวนคี่ได้ หรืออาจเปลี่ยนคณิตศาสตร์ทั้งหมด ความสอดคล้องทางตรรกะ และทั้งเอกภพ หรือสร้างโลกที่มีเพียง 77 เป็นจำนวนคู่และจำนวนอื่นทั้งหมดเป็นจำนวนคี่ แล้วทำให้นักคณิตศาสตร์ทุกคนมองว่าการจัดเรียงนั้นสอดคล้องกันอย่างสมบูรณ์และถูกต้องมาโดยตลอดก็ได้
ดังนั้นคำตอบจึงอาจถือได้ว่าขึ้นอยู่กับ ความเชื่อทางศาสนา ในระดับหนึ่ง
วิทยาการคอมพิวเตอร์เชิงทฤษฎีและ ทฤษฎีความซับซ้อน ดูเหมือนมีตำแหน่งต่อสายตานักศึกษาปริญญาตรี CS หรือคนในอุตสาหกรรมข้างเคียง คล้ายกับที่ฟิสิกส์อนุภาคมีต่อคนทั่วไป
เหมือนที่คนทั่วไปเคยได้ยินคำว่า entanglement เราก็เคยได้ยินคำว่า NP-hard แล้วแทนที่จะเดินตามพัฒนาการทางคณิตศาสตร์ด้วยตัวเอง เรากลับแทนที่ด้วยอุปมาแบบป๊อปที่แย่และจินตนาการเพ้อฝัน
ผู้เขียนอาจเลือกนิยามของ computability ที่เข้มงวดมากของตนเองจากการฝึกฝนมายาวนาน เขียนบทความทั้งบทเกี่ยวกับนิยามเฉพาะของคำนั้น แล้วกล่าวหาคนทั้งโลกที่ใช้คำเดียวกันในนิยามอื่นว่าถามคำถามโง่ ๆ ก็ได้
เวลาเราคุยกับนักวิชาการหรือคุยกับคนทั่วไปในที่ทำงาน เรื่องแบบนี้เกิดขึ้นบ่อยจริง ๆ การกำหนดคำศัพท์ร่วมกันเป็นเรื่องยาก และวิธีที่ขีดเส้นตามมาตรฐานคำศัพท์ของตัวเองแล้วบอกให้คนอื่นตามมาเป็นอะไรที่เหนื่อยหน่าย