01 · ทฤษฎีการคำนวณ
บทนี้คือชั้นรากฐานของหอคอย — ชั้นที่ตัดสินว่าทุกชั้นเหนือขึ้นไปได้รับอนุญาตให้ลองทำอะไรได้บ้าง
อะไรบ้างที่คำนวณได้เลย — และอะไรที่คำนวณไม่ได้เด็ดขาด ไม่ว่าจะบนฮาร์ดแวร์ชนิดไหนก็ตาม
โปรแกรมเมอร์ทำงานจริงทุกคนอยากมีเครื่องมือชิ้นนี้ไว้ในมือ มันอ่านโปรแกรมกับข้อมูลนำเข้าของโปรแกรมนั้น แล้วตอบคำถามเดียว: โปรแกรมนี้จะจบ หรือจะวนซ้ำไปตลอดกาล? หมด build ที่ค้าง หมดเซิร์ฟเวอร์ที่วนลูปข้ามคืน มันไม่ต้อง แก้ โปรแกรมด้วยซ้ำ แค่รายงานผลก็พอ
มันไม่มีทางมีอยู่จริง ไม่ใช่ "ยังไม่มีใครทำสำเร็จ" ไม่ใช่ "มันคงช้าเกินไป" — ไม่มีใครเขียนโปรแกรมแบบนี้ขึ้นมาได้ ไม่ว่าจะบนเครื่องไหนที่เคยสร้างมาแล้วหรือจะสร้างขึ้นในอนาคต และบทพิสูจน์ตีพิมพ์ตั้งแต่ปี 1936 ก่อนจะมีเครื่องจักรสักเครื่องให้รันมันด้วยซ้ำ "ทำไม" คือเนื้อหาทั้งหมดของชั้นนี้ และคือเหตุผลที่ชั้นนี้อยู่ล่างสุดของหอคอย: มันปักเขตแดนให้ทุกอย่างข้างบนสร้างต่อยอดขึ้นมา
คำถามนี้มาจาก Hilbert และตั้งใจให้มีคำตอบที่มีความสุข ปี 1928 David Hilbert กับ Wilhelm Ackermann ตีพิมพ์ Grundzüge der theoretischen Logik ตำราเล่มแรกที่อธิบายตรรกศาสตร์อันดับหนึ่ง (first-order logic) อย่างเป็นระบบ และวางคำถาม Entscheidungsproblem ไว้ในเล่ม: มีกระบวนการที่แน่นอนซึ่งรับข้อความเชิงตรรกะใดๆ แล้วตัดสินได้ไหมว่ามันสืบเนื่องมาจากสัจพจน์ (axiom) หรือไม่ (Springer)? Hilbert คาดว่ามี ที่เมือง Königsberg วันที่ 8 กันยายน 1930 เขาปิดปาฐกถาด้วยประโยคที่ภายหลังถูกสลักบนหลุมศพของเขา: Wir müssen wissen — wir werden wissen — เราต้องรู้ เราจะต้องรู้ (MAA Convergence)
วันก่อนหน้านั้น ที่โต๊ะกลมปิดท้ายการประชุมวิชาการในเมืองเดียวกัน นักตรรกวิทยาหนุ่มชื่อ Kurt Gödel เอ่ยขึ้นมาเกือบจะเป็นการพูดผ่านๆ ว่าระบบรูปนัย (formal system) ที่สอดคล้องในตัวเองใดๆ ที่แข็งแรงพอจะอธิบายเลขคณิตได้ ต้องมีข้อความจริงบางข้อที่มันพิสูจน์ไม่ได้อยู่ในตัว ห้องประชุมปล่อยผ่าน; John von Neumann อยู่ในที่ประชุมด้วย และดูเหมือนจะเป็นคนเดียวที่จับได้ว่าเพิ่งเกิดอะไรขึ้น (Davis, Notices of the AMS, 2006) บทความตามมาในปี 1931 (Monatshefte für Mathematik und Physik 38: 173–198)
Gödel เจาะรูเรือไปแล้ว แต่ Entscheidungsproblem ยังลอยอยู่ได้: คุณพิสูจน์ไม่ได้ว่าไม่มีกระบวนการใดอยู่เลย จนกว่าจะนิยามก่อนว่า "กระบวนการ" คืออะไร
นิยามนั้นได้มาจากการเฝ้าดูคน สิ่งที่ Alan Turing ทำตอนอายุยี่สิบสามปีและเป็น Fellow ของ King's College เป็นแนวมานุษยวิทยามากกว่าคณิตศาสตร์ ในปี 1936 คำว่า computer ยังเป็นชื่อตำแหน่งงาน: มนุษย์คนหนึ่ง มักได้ค่าจ้างต่ำ ที่ทำหน้าที่คำนวณ Turing เฝ้าดูคนคนนั้น เขาเขียนไว้ว่า "การคำนวณโดยปกติทำโดยการเขียนสัญลักษณ์บางอย่างลงบนกระดาษ เราอาจสมมติว่ากระดาษแผ่นนี้ถูกแบ่งเป็นช่องสี่เหลี่ยมเหมือนสมุดเลขคณิตของเด็ก" (On Computable Numbers, §9) เขาถอดความสามารถของมนุษย์ออกทีละอย่าง: จำกัดสัญลักษณ์ที่รับรู้ได้ในการมองแต่ละครั้ง จำกัด "สภาวะทางความคิด (states of mind)" ที่เขาจำไว้ได้ ไม่เหลืออะไรให้ทำนอกจากมอง เขียน และขยับ สิ่งที่เหลืออยู่คือเทป ตารางกฎจำนวนจำกัด และหัวอ่านที่อ่านและเขียนได้ — คือเครื่องทัวริง (Turing machine) ที่เป็นคำอธิบายว่ามนุษย์ทำอะไรเมื่อหยุดคิดแล้วเริ่มทำตามคำสั่ง มากกว่าจะเป็นเครื่องจักรจริงๆ เสียอีก London Mathematical Society รับบทความนี้ไว้เมื่อวันที่ 28 พฤษภาคม 1936
ทุกคนที่นิยามมันขึ้นมาอย่างเป็นอิสระต่อกัน ต่างมาลงเอยที่จุดเดียวกัน Alonzo Church ถึงจุดนั้นก่อนใครด้วยเส้นทางอื่น: บทพิสูจน์เมื่อเดือนเมษายน 1936 สร้างบน lambda calculus ของเขา ว่าไม่มีกระบวนการแบบนั้นอยู่จริง (American Journal of Mathematics 58: 345–363) Emil Post ถึงระบบรูปนัยที่แทบจะเหมือนกันในปีเดียวกัน; Gödel กับ Kleene ถึงด้วย general recursive functions ทั้งหมดนี้นิยามคลาสเดียวกันเป๊ะ และการที่ต่างเส้นทางมาบรรจบกันนี้เองคือหลักฐานของข้อตั้ง Church–Turing (Church–Turing thesis): คลาสนี้*คือ*สิ่งที่เราหมายถึงอย่างไม่เป็นทางการเมื่อพูดว่า "คำนวณได้อย่างมีประสิทธิผล" ("effectively calculable") มันเป็นข้อตั้ง ไม่ใช่ทฤษฎีบท และเป็นอย่างอื่นไปไม่ได้: มันเชื่อมไอเดียของมนุษย์ที่ไม่เป็นทางการเข้ากับวัตถุที่เป็นรูปนัย และไม่มีบทพิสูจน์ใดข้ามช่องว่างนั้นได้ (Stanford Encyclopedia of Philosophy) นี่คือเหตุผลที่ผลลัพธ์ของชั้นนี้ทนทานต่อฮาร์ดแวร์ทุกชนิด: สร้างเครื่องคำนวณขึ้นจากอะไรก็ได้ที่คุณอยากใช้ — หลอดสุญญากาศ ซิลิคอน คิวบิต (qubit) — ถ้ามันคำนวณได้จริง มันก็คำนวณได้แค่คลาสนี้ ไม่มากไปกว่านี้
เครื่องเดียวเป็นเครื่องทุกเครื่องได้ ส่วนที่ 6 ของบทความของ Turing เปิดด้วยประโยคที่ส่งผลสะเทือนที่สุดในบทความทั้งฉบับ: "เป็นไปได้ที่จะประดิษฐ์เครื่องเดี่ยวเครื่องหนึ่งขึ้นมา ซึ่งใช้คำนวณลำดับที่คำนวณได้ใดๆ ก็ได้ทั้งหมด" ("It is possible to invent a single machine which can be used to compute any computable sequence.") ป้อน*คำอธิบาย*ของเครื่องอื่นให้เครื่องหนึ่ง มันก็ทำตัวเป็นเครื่องนั้น ก่อนหน้านี้ อุปกรณ์คำนวณถูกสร้างมาเพื่องานเฉพาะของมัน — กี่ทอผ้าสำหรับทอผ้า เครื่องวิเคราะห์เชิงอนุพันธ์ (differential analyzer) สำหรับสมการ หลังจากนั้น ตัวเครื่องว่างเปล่า และงานมาถึงในรูปข้อมูล ทุกอย่างที่ตามมาขึ้นอยู่กับจุดนั้น: ซอฟต์แวร์ที่แยกออกจากฮาร์ดแวร์ได้ คอมไพเลอร์ อีมูเลเตอร์ (emulator) เครื่องเสมือน (virtual machine) ระบบปฏิบัติการที่รันโปรแกรมซึ่งไม่เคยถูกออกแบบมาให้มันรัน ความเป็นสากล (universality) คือบานพับที่หอคอยทั้งหลังแกว่งอยู่บน
บางคำถามไม่มีกระบวนการตอบเลยจริงๆ บทพิสูจน์คือการทแยงมุม (diagonalization) ของ Cantor จากปี 1891 หันมาใช้กับเครื่องจักร สมมติว่าตัวตรวจสอบการหยุด (halting checker) มีอยู่จริง สร้างโปรแกรมที่ป้อนคำอธิบายของตัวมันเองให้ตัวตรวจสอบ แล้วทำตรงข้ามกับคำทำนายที่ได้รับ: หยุดถ้าถูกบอกว่ามันจะวนลูป วนลูปถ้าถูกบอกว่ามันจะหยุด ถามตัวตรวจสอบเกี่ยวกับโปรแกรมนั้น มันต้องตอบผิดเสมอ มันจึงไม่เคยมีอยู่จริงตั้งแต่แรก
เชิงอรรถแห่งความซื่อตรงสองข้อ Turing ไม่ได้ใช้ทั้งชื่อนั้นและบทพิสูจน์แบบนั้นเลย เขาพิสูจน์การตัดสินไม่ได้ (undecidability) ของปัญหาที่เกี่ยวข้องกับเครื่องจักรของเขาเท่านั้น ทั้งชื่อ "ปัญหาการหยุด (halting problem)" และรูปแบบสมัยใหม่มาทีหลัง ใน Computability and Unsolvability ของ Martin Davis ปี 1958 (Hamkins & Nenu, 2024) ข้อสอง การหยุดไม่ใช่กรณีพิเศษแปลกๆ: H. G. Rice พิสูจน์ในปี 1953 ว่าคำถามที่ไม่ธรรมดา*ทุก*ข้อเกี่ยวกับสิ่งที่โปรแกรมคำนวณนั้นตัดสินไม่ได้ทั้งหมด (Transactions of the American Mathematical Society 74: 358–366) นั่นคือรั้วกั้นเขต ไม่ใช่หลุมบ่อ — คือเหตุผลที่ไม่มีคอมไพเลอร์ตัวไหนรับประกันได้ว่าลูปของคุณจะจบ เหตุผลที่ไม่มีโปรแกรมป้องกันไวรัสตัวไหนตัดสินได้จากการวิเคราะห์อย่างเดียวว่าโปรแกรมหนึ่งเป็นอันตรายหรือไม่ และเหตุผลที่ static analyzer ทุกตัวตอบได้แค่ "ใช่" "ไม่ใช่" หรือ "บอกไม่ได้" คำตอบที่สามนั้นคือทฤษฎีบท ไม่ใช่บั๊ก
พ้นกำแพงแห่งความเป็นไปได้ไปแล้ว ยังมีกำแพงที่สอง: ความคุ้มต้นทุน ปัญหาหนึ่งอาจตัดสินได้ (decidable) แต่แพงกว่าที่เอกภพทั้งใบจะจ่ายไหว Stephen Cook แสดงให้เห็นในปี 1971 ว่า Boolean satisfiability เป็น NP-complete และ Leonid Levin พิสูจน์เรื่องเดียวกันอย่างเป็นอิสระในปี 1973 (บันทึกของ Cook เอง) เครื่องมือเบื้องหลังข้อกล่าวอ้างแบบนี้คือ การลดรูป (reduction): การแปลงที่ถูกพอจนตัวแก้ปัญหาที่เร็วสำหรับปัญหาหนึ่ง กลายเป็นตัวแก้ปัญหาที่เร็วสำหรับอีกปัญหาหนึ่ง — ปัญหายากข้อเดียวกลายเป็นคันโยกที่ยกปัญหาที่เหลือทั้งหมดได้ ปี 1972 Richard Karp ใช้มันแสดงให้เห็นว่าปัญหาที่ดูเป็นธรรมชาติอีกยี่สิบข้อ แท้จริงคือปัญหาเดียวกันที่แค่ปลอมตัวมา (Karp, 1972); พอถึงปี 1979 หนังสือ Computers and Intractability ของ Garey กับ Johnson รวบรวมได้ถึงสามร้อยปัญหา ส่วนคำถามว่าการตรวจคำตอบได้เร็วบ่งบอกว่าหาคำตอบได้เร็วด้วยหรือไม่ — P vs NP — ตั้งขึ้นในจดหมายที่ Gödel เขียนถึง von Neumann ผู้กำลังจะเสียชีวิตเมื่อวันที่ 20 มีนาคม 1956 (คำแปล) มาพร้อมเงินรางวัลหนึ่งล้านดอลลาร์จาก Clay Institute และยังไม่มีคำตอบมาจนถึงทุกวันนี้ (CMI) กำแพงนี้รั่วอย่างเป็นประโยชน์อยู่บ้าง: ขอบเขตที่พิสูจน์ได้ดีที่สุดสำหรับ 3-SAT คือเชิงเลขชี้กำลัง (exponential) แต่ตัวแก้ปัญหาระดับอุตสาหกรรมจัดการอินสแตนซ์ที่มีโครงสร้างชัดเจนซึ่งมีตัวแปรกว่าล้านตัวได้เป็นประจำ (Gomes et al.) กรณีแย่สุด (worst case) ไม่ใช่กรณีทั่วไป (typical case) — และนี่คือจุดที่ชั้นถัดไปเริ่มต้น
เชื่อมโยง
ชั้นล่าง: บทที่ 00 แผนที่ ชั้นบน: บทที่ 02 ที่หยิบทุกปัญหาซึ่งชั้นนี้เรียกว่าเป็นไปได้ มาถามต่อว่ามันมีต้นทุนเท่าไร โดยเปลี่ยนข้อโต้แย้งเชิงการนับชุดเดียวกันให้กลายเป็นขอบล่าง (lower bound) ความเป็นสากล (universality) คือสิ่งที่บทที่ 05 ขายในชื่อการทำเสมือน (virtualization) และบทที่ 06 ขายในชื่อการคอมไพล์ (compilation) บทที่ 11 สร้างต่อจากกำแพงที่สอง: วิทยาการรหัสลับ (cryptography) คือการจงใจผลิตปัญหาที่เชื่อกันว่าไม่คุ้มต้นทุนจะแก้
คำถามที่ยังเปิดอยู่
P vs NP แน่นอนอยู่แล้ว — แม้ว่าบทพิสูจน์ว่า P = NP จะเป็นเหตุการณ์มากกว่าทฤษฎีบท: ความปลอดภัยของอินเทอร์เน็ตสลายไป คณิตศาสตร์ส่วนใหญ่ถูกส่งมอบให้เครื่องจักรทำแทน ข้อตั้ง Church–Turing เองปลอดภัยหรือเปล่า? คอมพิวเตอร์ควอนตัม (quantum computer) คำนวณอะไรที่ Turing machine คำนวณไม่ได้เลยสักอย่าง แต่อาจทำลายเวอร์ชัน*ประสิทธิภาพ*ของมันได้ — ดินแดนของบทที่ 14 และคำถามที่ลึกที่สุด: การตัดสินไม่ได้ (undecidability) จำกัดขอบเขตของเครื่องจักร และผ่านทางข้อตั้งนี้ ก็จำกัดกระบวนการใดๆ ที่มนุษย์จะทำตามได้ด้วย มีอะไรหนีพ้นมันได้ไหม หรือรั้วที่ล้อมรอบสิ่งที่เป็นไปได้ ก็คือรูปทรงของความคิดเองนั่นแหละ?
อ่านต่อ
- Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2012 — ตำราเรียนมาตรฐานของวิชานี้ (หน้าเว็บของผู้เขียน)
- A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem," Proceedings of the London Mathematical Society, ser. 2, 42 (1936–37): 230–265 — คุ้มค่าจะอ่านแค่ §9 ก็ยังคุ้ม (PDF)
- Richard Karp, "Reducibility Among Combinatorial Problems," 1972 — เปเปอร์ที่เปลี่ยน NP-completeness จากทฤษฎีบทให้กลายเป็นแผนที่ (PDF)