01 · Theory of Computation
01 · ทฤษฎีการคำนวณ
This chapter is the bedrock of the tower — the floor that decides what every floor above it is permitted to attempt.
บทนี้คือชั้นรากฐานของหอคอย — ชั้นที่ตัดสินว่าทุกชั้นเหนือขึ้นไปได้รับอนุญาตให้ลองทำอะไรได้บ้าง
What can be computed at all — and what never, on any hardware?
อะไรบ้างที่คำนวณได้เลย — และอะไรที่คำนวณไม่ได้เด็ดขาด ไม่ว่าจะบนฮาร์ดแวร์ชนิดไหนก็ตาม
Here is a tool every working programmer would like to own. It reads a program and its input and answers one question: will this finish, or will it run forever? No more hung builds, no more servers looping overnight. It need not even fix the program, only report on it.
โปรแกรมเมอร์ทำงานจริงทุกคนอยากมีเครื่องมือชิ้นนี้ไว้ในมือ มันอ่านโปรแกรมกับข้อมูลนำเข้าของโปรแกรมนั้น แล้วตอบคำถามเดียว: โปรแกรมนี้จะจบ หรือจะวนซ้ำไปตลอดกาล? หมด build ที่ค้าง หมดเซิร์ฟเวอร์ที่วนลูปข้ามคืน มันไม่ต้อง แก้ โปรแกรมด้วยซ้ำ แค่รายงานผลก็พอ
It cannot exist. Not "nobody has managed it yet," not "it would be too slow" — no such program can be written, on any machine ever built or ever to be built, and the proof was published in 1936, before there was a machine to run it on. Why is the whole of this floor, and the reason the floor sits at the bottom of the tower: it fences the territory everything above builds on.
มันไม่มีทางมีอยู่จริง ไม่ใช่ "ยังไม่มีใครทำสำเร็จ" ไม่ใช่ "มันคงช้าเกินไป" — ไม่มีใครเขียนโปรแกรมแบบนี้ขึ้นมาได้ ไม่ว่าจะบนเครื่องไหนที่เคยสร้างมาแล้วหรือจะสร้างขึ้นในอนาคต และบทพิสูจน์ตีพิมพ์ตั้งแต่ปี 1936 ก่อนจะมีเครื่องจักรสักเครื่องให้รันมันด้วยซ้ำ "ทำไม" คือเนื้อหาทั้งหมดของชั้นนี้ และคือเหตุผลที่ชั้นนี้อยู่ล่างสุดของหอคอย: มันปักเขตแดนให้ทุกอย่างข้างบนสร้างต่อยอดขึ้นมา
The question came from Hilbert, and was meant to have a happy answer. In 1928 David Hilbert and Wilhelm Ackermann published Grundzüge der theoretischen Logik, the first textbook exposition of first-order logic, and posed in it the Entscheidungsproblem: is there a definite procedure that takes any statement of logic and decides whether it follows from the axioms (Springer)? Hilbert expected there was. In Königsberg on 8 September 1930 he closed a speech with the line later carved on his gravestone: Wir müssen wissen — wir werden wissen — we must know, we will know (MAA Convergence).
คำถามนี้มาจาก 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)
The day before, at a roundtable closing a conference in the same city, a young logician named Kurt Gödel had mentioned almost in passing that any consistent formal system strong enough to describe arithmetic must contain true statements it cannot prove. The room let it go by; John von Neumann, present, appears to have been the only person who grasped what had happened (Davis, Notices of the AMS, 2006). The paper followed in 1931 (Monatshefte für Mathematik und Physik 38: 173–198).
วันก่อนหน้านั้น ที่โต๊ะกลมปิดท้ายการประชุมวิชาการในเมืองเดียวกัน นักตรรกวิทยาหนุ่มชื่อ 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 had holed the ship, but the Entscheidungsproblem stayed afloat: you cannot prove no procedure exists until you have said what a procedure is.
Gödel เจาะรูเรือไปแล้ว แต่ Entscheidungsproblem ยังลอยอยู่ได้: คุณพิสูจน์ไม่ได้ว่าไม่มีกระบวนการใดอยู่เลย จนกว่าจะนิยามก่อนว่า "กระบวนการ" คืออะไร
The definition was found by watching a person. Alan Turing's move, at twenty-three and a Fellow of King's College, was less mathematical than anthropological. In 1936 a computer was a job title: a human being, usually poorly paid, who calculated. Turing watched one. "Computing is normally done by writing certain symbols on paper," he wrote. "We may suppose this paper is divided into squares like a child's arithmetic book" (On Computable Numbers, §9). Then he stripped the human away one faculty at a time: a bound on the symbols taken in at a glance, a bound on the "states of mind" he can hold, nothing to do but look, write, and move. What remains is a tape, a finite table of rules, and a head that reads and writes — the Turing machine, less a machine than a description of what a person does when they stop thinking and start following instructions. The London Mathematical Society received it on 28 May 1936.
นิยามนั้นได้มาจากการเฝ้าดูคน สิ่งที่ Alan Turing ทำตอนอายุยี่สิบสามปีและเป็น Fellow ของ King's College เป็นแนวมานุษยวิทยามากกว่าคณิตศาสตร์ ในปี 1936 คำว่า computer ยังเป็นชื่อตำแหน่งงาน: มนุษย์คนหนึ่ง มักได้ค่าจ้างต่ำ ที่ทำหน้าที่คำนวณ Turing เฝ้าดูคนคนนั้น เขาเขียนไว้ว่า "การคำนวณโดยปกติทำโดยการเขียนสัญลักษณ์บางอย่างลงบนกระดาษ เราอาจสมมติว่ากระดาษแผ่นนี้ถูกแบ่งเป็นช่องสี่เหลี่ยมเหมือนสมุดเลขคณิตของเด็ก" (On Computable Numbers, §9) เขาถอดความสามารถของมนุษย์ออกทีละอย่าง: จำกัดสัญลักษณ์ที่รับรู้ได้ในการมองแต่ละครั้ง จำกัด "สภาวะทางความคิด (states of mind)" ที่เขาจำไว้ได้ ไม่เหลืออะไรให้ทำนอกจากมอง เขียน และขยับ สิ่งที่เหลืออยู่คือเทป ตารางกฎจำนวนจำกัด และหัวอ่านที่อ่านและเขียนได้ — คือเครื่องทัวริง (Turing machine) ที่เป็นคำอธิบายว่ามนุษย์ทำอะไรเมื่อหยุดคิดแล้วเริ่มทำตามคำสั่ง มากกว่าจะเป็นเครื่องจักรจริงๆ เสียอีก London Mathematical Society รับบทความนี้ไว้เมื่อวันที่ 28 พฤษภาคม 1936
Everyone who defined it independently landed in the same place. Alonzo Church got there first by another road: an April 1936 proof, built on his lambda calculus, that no such procedure exists (American Journal of Mathematics 58: 345–363). Emil Post reached a near-identical formalism that year; Gödel and Kleene, general recursive functions. All define exactly the same class, and that convergence is the evidence for the Church–Turing thesis: this class is what we informally mean by "effectively calculable." It is a thesis, not a theorem, and cannot be otherwise: it joins an informal human idea to a formal object, and no proof bridges that gap (Stanford Encyclopedia of Philosophy). It is also why this floor's results are hardware-proof: build a computer from anything you like — tubes, silicon, qubits — and if it computes at all, it computes this set and no more.
ทุกคนที่นิยามมันขึ้นมาอย่างเป็นอิสระต่อกัน ต่างมาลงเอยที่จุดเดียวกัน 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) — ถ้ามันคำนวณได้จริง มันก็คำนวณได้แค่คลาสนี้ ไม่มากไปกว่านี้
One machine can be all machines. Section 6 of Turing's paper opens with the most consequential sentence in it: "It is possible to invent a single machine which can be used to compute any computable sequence." Hand a machine the description of another and it behaves as that one. Before this, a calculating device was built for its task — a loom for weaving, a differential analyzer for equations. After, the machine is blank and the task arrives as data. Everything downstream depends on that: software separable from hardware, the compiler, the emulator, the virtual machine, the operating system running programs it was never designed for. Universality is the hinge the tower swings on.
เครื่องเดียวเป็นเครื่องทุกเครื่องได้ ส่วนที่ 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) คือบานพับที่หอคอยทั้งหลังแกว่งอยู่บน
And some questions simply have no procedure. The proof is Cantor's diagonal argument of 1891, turned on machines. Suppose the halting checker exists. Build a program that hands the checker its own description and does the opposite of the prediction: halt if told it loops, loop if told it halts. Ask the checker about that program and it must be wrong. So it never existed.
บางคำถามไม่มีกระบวนการตอบเลยจริงๆ บทพิสูจน์คือการทแยงมุม (diagonalization) ของ Cantor จากปี 1891 หันมาใช้กับเครื่องจักร สมมติว่าตัวตรวจสอบการหยุด (halting checker) มีอยู่จริง สร้างโปรแกรมที่ป้อนคำอธิบายของตัวมันเองให้ตัวตรวจสอบ แล้วทำตรงข้ามกับคำทำนายที่ได้รับ: หยุดถ้าถูกบอกว่ามันจะวนลูป วนลูปถ้าถูกบอกว่ามันจะหยุด ถามตัวตรวจสอบเกี่ยวกับโปรแกรมนั้น มันต้องตอบผิดเสมอ มันจึงไม่เคยมีอยู่จริงตั้งแต่แรก
Two footnotes of honesty. Turing used neither that name nor that proof; he proved undecidability for related problems about his machines, and both name and modern formulation appear later, in Martin Davis's Computability and Unsolvability of 1958 (Hamkins & Nenu, 2024). And halting is no exotic special case: H. G. Rice proved in 1953 that every non-trivial question about what a program computes is undecidable (Transactions of the American Mathematical Society 74: 358–366). That is a fence, not a pothole — why no compiler will promise your loop terminates, why no antivirus can decide by analysis alone whether a program is malicious, and why every static analyzer answers "yes," "no," or "I cannot tell." That third answer is a theorem, not a bug.
เชิงอรรถแห่งความซื่อตรงสองข้อ 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 ทุกตัวตอบได้แค่ "ใช่" "ไม่ใช่" หรือ "บอกไม่ได้" คำตอบที่สามนั้นคือทฤษฎีบท ไม่ใช่บั๊ก
Past the wall of the possible stands a second wall: the affordable. A problem can be decidable and still cost more than the universe can pay. Stephen Cook showed in 1971 that Boolean satisfiability is NP-complete, and Leonid Levin proved as much independently in 1973 (Cook's own account). The instrument behind such a claim is reduction: a translation cheap enough that a fast solver for one problem becomes a fast solver for another — one hard problem made into a lever on all the rest. In 1972 Richard Karp used it to show that twenty more natural problems were the same problem in disguise (Karp, 1972); by 1979 Garey and Johnson's Computers and Intractability catalogued three hundred. Whether checking an answer quickly implies finding one quickly — P versus NP — was posed in a letter Gödel wrote to the dying von Neumann on 20 March 1956 (translation), carries a million-dollar Clay Institute prize, and is unsolved (CMI). The wall leaks usefully, though: the best proven bound for 3-SAT is exponential, yet industrial solvers routinely dispatch structured instances of over a million variables (Gomes et al.). Worst case is not typical case — where the next floor begins.
พ้นกำแพงแห่งความเป็นไปได้ไปแล้ว ยังมีกำแพงที่สอง: ความคุ้มต้นทุน ปัญหาหนึ่งอาจตัดสินได้ (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) — และนี่คือจุดที่ชั้นถัดไปเริ่มต้น
Connections
เชื่อมโยง
Below: 00, the map. Above: 02, which takes every problem this floor calls possible and asks what it costs, turning the same counting arguments into lower bounds. Universality is what 05 sells as virtualization and 06 as compilation. 11 builds on the second wall: cryptography is the deliberate manufacture of problems believed unaffordable.
ชั้นล่าง: บทที่ 00 แผนที่ ชั้นบน: บทที่ 02 ที่หยิบทุกปัญหาซึ่งชั้นนี้เรียกว่าเป็นไปได้ มาถามต่อว่ามันมีต้นทุนเท่าไร โดยเปลี่ยนข้อโต้แย้งเชิงการนับชุดเดียวกันให้กลายเป็นขอบล่าง (lower bound) ความเป็นสากล (universality) คือสิ่งที่บทที่ 05 ขายในชื่อการทำเสมือน (virtualization) และบทที่ 06 ขายในชื่อการคอมไพล์ (compilation) บทที่ 11 สร้างต่อจากกำแพงที่สอง: วิทยาการรหัสลับ (cryptography) คือการจงใจผลิตปัญหาที่เชื่อกันว่าไม่คุ้มต้นทุนจะแก้
Open questions
คำถามที่ยังเปิดอยู่
P versus NP, obviously — though a proof that P = NP would be less a theorem than an event: the security of the internet dissolved, much of mathematics handed to a machine. Is the thesis itself safe? Quantum computers compute nothing a Turing machine cannot, but may break its efficiency version — chapter 14's territory. And the deepest: undecidability limits machines and, through the thesis, any procedure a human could follow. Does anything escape it, or is the fence around the possible simply the shape of thought?
P vs NP แน่นอนอยู่แล้ว — แม้ว่าบทพิสูจน์ว่า P = NP จะเป็นเหตุการณ์มากกว่าทฤษฎีบท: ความปลอดภัยของอินเทอร์เน็ตสลายไป คณิตศาสตร์ส่วนใหญ่ถูกส่งมอบให้เครื่องจักรทำแทน ข้อตั้ง Church–Turing เองปลอดภัยหรือเปล่า? คอมพิวเตอร์ควอนตัม (quantum computer) คำนวณอะไรที่ Turing machine คำนวณไม่ได้เลยสักอย่าง แต่อาจทำลายเวอร์ชัน*ประสิทธิภาพ*ของมันได้ — ดินแดนของบทที่ 14 และคำถามที่ลึกที่สุด: การตัดสินไม่ได้ (undecidability) จำกัดขอบเขตของเครื่องจักร และผ่านทางข้อตั้งนี้ ก็จำกัดกระบวนการใดๆ ที่มนุษย์จะทำตามได้ด้วย มีอะไรหนีพ้นมันได้ไหม หรือรั้วที่ล้อมรอบสิ่งที่เป็นไปได้ ก็คือรูปทรงของความคิดเองนั่นแหละ?
Go deeper
อ่านต่อ
- Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2012 — the standard course text (author's page).
- 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 — worth reading for §9 alone (PDF).
- Richard Karp, "Reducibility Among Combinatorial Problems," 1972 — the paper that turned NP-completeness from a theorem into a map (PDF).
- 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)