บทความวิชาการที่ทรงอิทธิพลที่สุดในประวัติศาสตร์วิทยาการคอมพิวเตอร์
(terriblesoftware.org)- บทความวิชาการด้านวิทยาการคอมพิวเตอร์ 7 ฉบับ ตั้งแต่ปี 1936 ถึง 1998 ได้ก่อรูปชั้นแกนหลักของคอมพิวติ้งสมัยใหม่ ได้แก่ ความสามารถในการคำนวณ ทฤษฎีสารสนเทศ ฐานข้อมูล ความซับซ้อน อินเทอร์เน็ต เว็บ และการค้นหา
- บทความปี 1936 ของ Alan Turing ใช้ Turing Machine แยกแยะว่าสิ่งใดที่เครื่องจักรสามารถคำนวณได้ในเชิงหลักการ และสิ่งใดคำนวณไม่ได้ จนกลายเป็นจุดตั้งต้นของโมเดลการคำนวณสมัยใหม่
- Claude Shannon, Edgar F. Codd และ Stephen A. Cook สร้างภาษากลางให้กับการสื่อสาร ข้อมูล และระดับความยากของปัญหา ผ่านการวัดสารสนเทศและการแก้ไขข้อผิดพลาด, โมเดลข้อมูลเชิงสัมพันธ์, รวมถึง NP-completeness และ SAT ตามลำดับ
- บทความของ Vinton G. Cerf กับ Robert E. Kahn, Tim Berners-Lee, Sergey Brin กับ Larry Page วางโครงสร้างของการเชื่อมต่อเครือข่าย การเชื่อมโยงเอกสาร และการค้นหาเว็บ ด้วย TCP/IP, World Wide Web และ PageRank
- เมื่อมองไปถึงรายชื่อเสริมอย่าง Lisp, structured programming, logical clock, ความซับซ้อนของซอฟต์แวร์ และ Transformer การเข้าใจ แนวคิดพื้นฐาน จึงเป็นความได้เปรียบที่อยู่ได้นานกว่าเครื่องมือใหม่ ๆ
เกณฑ์การคัดเลือกและภาพรวมของพัฒนาการ
- รายชื่อนี้ไม่ใช่อันดับแบบตายตัว แต่เป็นการคัดเลือกเชิงอัตวิสัยโดยอิงจาก อิทธิพล ที่มีต่อโลกปัจจุบัน
- บทความทั้ง 7 ฉบับเรียงตามลำดับเวลา แสดงพัฒนาการต่อเนื่องจากการคำนวณ การสื่อสาร การจัดเก็บข้อมูล ระดับความยากของการคำนวณ เครือข่าย เว็บ ไปจนถึงการค้นหา
- แม้ภาษาใหม่ ๆ ความก้าวหน้าของ AI การก้าวกระโดดของควอนตัม และ JavaScript framework จะเกิดขึ้นอย่างต่อเนื่อง แต่รากฐานของคอมพิวติ้งสมัยใหม่ยังคงมีแนวคิดที่บทความเหล่านี้สร้างไว้
1. “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936)
- Alan Turing วางรากฐานว่าในทางทฤษฎีคอมพิวเตอร์สามารถทำอะไรได้บ้าง ผ่าน Turing Machine ในจินตนาการเมื่อทศวรรษ 1930
- โมเดลหลักประกอบด้วยเทป หัวอ่าน/เขียน และชุดสถานะที่มีจำนวนจำกัด
- โมเดลนี้นิยามว่าปัญหาใดแก้ได้ในความหมายเชิงกลไก และปัญหาใดแก้ไม่ได้
- ภาษาโปรแกรมและโค้ดทั้งหมดทำงานอยู่ภายในกฎที่ Turing นิยามไว้ และแม้เมื่อพูดถึงควอนตัมคอมพิวติ้ง ก็ยังอ้างอิงขอบเขตที่ Turing เสนอไว้
- อ่านเพิ่มเติม:
2. “A Mathematical Theory of Communication” (1948)
- Claude Shannon สร้าง ทฤษฎีสารสนเทศ เพื่อจัดการสารสนเทศอย่างเข้มงวด และวางระบบแนวคิดอย่าง bit, entropy และ noisy channel
- “สารสนเทศ” ที่เคยเป็นนามธรรมกลายเป็นสิ่งที่วัดได้ และเกิดรากฐานของการบีบอัดข้อมูลกับโค้ดแก้ไขข้อผิดพลาด
- แนวคิดนี้ถูกใช้ตั้งแต่การส่งสัญญาณสู่อวกาศ ไปจนถึงการสตรีม Netflix เพื่อบรรจุข้อมูลอย่างมีประสิทธิภาพและปกป้องข้อมูลจากข้อผิดพลาด
- การสื่อสารในชีวิตประจำวัน เช่น การส่งข้อความ การสตรีมวิดีโอ และการโทรผ่าน FaceTime ก็ทำงานอยู่บนแนวคิดของ Shannon
- อ่านเพิ่มเติม:
3. “A Relational Model of Data for Large Shared Data Banks” (1970)
- Edgar F. Codd เสนอ โมเดลเชิงสัมพันธ์ สำหรับจัดเก็บและค้นคืนข้อมูลขนาดใหญ่
- แนวคิดหลักคือการเก็บข้อมูลในตารางและจัดการด้วยการดำเนินการเชิงตรรกะ
- การออกแบบนี้นำไปสู่ SQL และตระกูลฐานข้อมูลเชิงสัมพันธ์ ซึ่งรองรับธนาคาร เว็บไซต์ค้าปลีก และระบบองค์กร
- แม้ในยุค NoSQL แนวคิดการจัดระเบียบข้อมูลอย่างตาราง schema และ consistency ก็ยังเชื่อมโยงกับโมเดลของ Codd
- อ่านเพิ่มเติม:
4. “The Complexity of Theorem-Proving Procedures” (1971)
- บทความของ Stephen A. Cook กล่าวถึงข้อเท็จจริงที่ว่าปัญหาการคำนวณบางอย่างยากมาก และนำเสนอแนวคิด NP-completeness
- Cook แสดงให้เห็นว่า Boolean satisfiability problem หรือ SAT เป็น NP-complete
- สิ่งนี้ทำให้เกิดภาษากลางในการพูดถึงระดับความยากของปัญหา เช่น ถ้าแก้ SAT ได้อย่างรวดเร็ว ปัญหายากอื่น ๆ จำนวนมากก็จะแก้ได้ด้วย
- คำว่า “NP-hard” หรือสถานการณ์ที่การหาทางที่เหมาะสมที่สุดทำให้ CPU ทำงานหนัก ล้วนเชื่อมโยงกับอิทธิพลของบทความนี้
- แนวคิดนี้ส่งผลอย่างมากต่ออัลกอริทึม วิทยาการรหัสลับ และการค้นหาวิธีแก้ที่มีประสิทธิภาพหรือวิธีแก้แบบประมาณ
- อ่านเพิ่มเติม:
5. “A Protocol for Packet Network Intercommunication” (1974)
- บทความของ Vinton G. Cerf และ Robert E. Kahn เสนอรากฐานของ TCP สำหรับเชื่อมต่อเครือข่ายที่แยกขาดจากกัน
- เครือข่ายต่างชนิดกันมีภาษาสากลสำหรับสื่อสารกัน ข้อมูลถูกแบ่งเป็นแพ็กเก็ตเล็ก ๆ วิ่งผ่านหลายเส้นทาง แล้วประกอบกลับอีกฝั่งหนึ่ง
- ความยืดหยุ่นนี้ทำให้การเชื่อมต่อระดับโลกเป็นไปได้ โดยไม่จำเป็นต้องมีเครือข่ายเดี่ยวขนาดมหึมาเพียงเครือข่ายเดียว
- กิจกรรมอย่างการท่องเว็บ การส่งอีเมล และการล็อกอินเว็บไซต์ธนาคาร ต่างพึ่งพา TCP/IP ในการเคลื่อนย้าย bit อย่างน่าเชื่อถือ
- แอปพลิเคชันเรียลไทม์บางประเภทใช้ UDP แต่แนวคิดหลักของเครือข่ายบนฐาน IP ที่ Cerf และ Kahn เสนอ ได้ผูกอุปกรณ์ต่าง ๆ ไว้ภายใต้เครือข่ายระดับโลกเดียวกัน
- อ่านเพิ่มเติม:
6. “Information Management: A Proposal” (1989)
- Tim Berners-Lee เสนอทิศทางของ World Wide Web เพื่อให้ผู้คนใช้งานได้ง่ายขึ้น หลังจากเครื่องจักรต่าง ๆ สามารถสื่อสารกันได้สะดวกแล้ว
- แนวคิดหลักคือระบบไฮเปอร์เท็กซ์ระดับโลกที่มี hyperlink, URL และ HTTP
- เมื่อเอกสารทั่วโลกไม่ได้อยู่อย่างโดดเดี่ยวอีกต่อไป แต่เชื่อมโยงถึงกัน อินเทอร์เน็ตจึงกลายเป็นรูปแบบที่ไม่ใช่แค่นักวิทยาศาสตร์ แต่ผู้ใช้ทั่วไปก็สำรวจได้
- เมล็ดพันธุ์ของประสบการณ์การใช้เว็บอย่างโซเชียลมีเดีย ช้อปปิ้งออนไลน์ และการอ่านบล็อกตอนตีสาม ล้วนมาจากข้อเสนอนี้
- อ่านเพิ่มเติม:
7. “The Anatomy of a Large-Scale Hypertextual Web Search Engine” (1998)
- Sergey Brin และ Larry Page สร้างแนวทางบนฐาน การวิเคราะห์ลิงก์ เพื่อรับมือกับเว็บที่มีลิงก์และหน้าเว็บเพิ่มขึ้นอย่างระเบิด และสิ่งนี้พัฒนาต่อมาเป็นเสิร์ชเอนจิน Google
- PageRank ซึ่งเป็นแนวคิดหลัก มองลิงก์ไม่ใช่แค่องค์ประกอบสำหรับคำนวณคีย์เวิร์ด แต่เป็นคะแนนโหวตแห่งความน่าเชื่อถือ
- วิธีนี้ปรับปรุงผลการค้นหาที่เกี่ยวข้องได้อย่างมาก ทำให้เว็บกลายเป็นพื้นที่ที่ค้นหาได้
- ประสบการณ์การพิมพ์คำถามลงใน Google แล้วได้คำตอบทันที ทำงานอยู่บน PageRank และนวัตกรรมอีกมากมายที่ตามมา
- PageRank นิยามวิธีสำรวจข้อมูลออนไลน์ขึ้นใหม่ และกลายเป็นจุดเริ่มต้นของยุคใหม่ของเทคโนโลยีที่ขับเคลื่อนด้วยข้อมูล เช่น โฆษณา analytics และ machine learning
- อ่านเพิ่มเติม:
อีก 5 ฉบับที่เกือบได้อยู่ในเนื้อหาหลัก
- “Recursive Functions of Symbolic Expressions and Their Computation by Machine” (1960) – John McCarthy
- นำ Lisp และสไตล์การเขียนโปรแกรมเชิงฟังก์ชันเข้ามา ซึ่งสไตล์นี้ยังคงอยู่ในภาษาและเฟรมเวิร์กสมัยใหม่
- “Go To Statement Considered Harmful” (1968) – Edsger Dijkstra
- วิจารณ์ว่า
gotoทำให้โค้ดรกและไร้โครงสร้าง พร้อมจุดกระแสการปฏิวัติ structured programming
- วิจารณ์ว่า
- “Time, Clocks, and the Ordering of Events in a Distributed System” (1978) – Leslie Lamport
- ในระบบกระจาย ไม่สามารถซิงก์นาฬิกาจริงได้อย่างสมบูรณ์ จึงจำเป็นต้องมี logical clock
- “No Silver Bullet—Essence and Accident in Software Engineering” (1986) – Fred Brooks
- เห็นว่าไม่มีวิธีมหัศจรรย์เพียงอย่างเดียวที่จะจัดการความซับซ้อนเชิงแก่นแท้ของการพัฒนาซอฟต์แวร์ได้
- “Attention Is All You Need” (2017) – Vaswani et al.
- เสนอ architecture แบบ Transformer ที่อยู่เบื้องหลัง GPT และโมเดล AI ชื่อดังหลายตัว
ผลกระทบที่แนวคิดพื้นฐานทิ้งไว้
- ปัจจุบันมีภาษาใหม่ นวัตกรรม AI การก้าวกระโดดของควอนตัม และ JavaScript framework ที่โผล่มาทุกสัปดาห์หลั่งไหลออกมาอย่างต่อเนื่อง
- หากไม่เข้าใจว่าแนวคิดแกนหลักอย่าง data structure, algorithm และเว็บมาจากไหน ก็จะกลายเป็นเพียงการสะสมเครื่องมือใหม่ ๆ ไปเรื่อย ๆ
- บทความทั้ง 7 ฉบับนี้และบทความเสริมช่วยพาย้อนดูแนวคิดที่กลายเป็นรากฐานสำคัญของคอมพิวติ้งสมัยใหม่
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
Communicating Sequential Processes (Hoare), The Next 700 Programming Languages (Landin), As We May Think (Bush), Can Programming Be Liberated from the von Neumann Style (Backus) ก็น่าจะใส่ไว้ด้วย
และคอร์สนี้ก็ดูน่าสนใจ: https://canvas.harvard.edu/courses/34992/assignments/syllabu...
“คอร์สนี้ครอบคลุมงานวิจัยที่นักวิทยาการคอมพิวเตอร์ทุกคนควรได้อ่าน ตั้งแต่ทศวรรษ 1930 จนถึงปัจจุบัน เป็นประสบการณ์แบบบูรณาการที่ช่วยให้นักศึกษาขั้นสูงด้านวิทยาการคอมพิวเตอร์มองเห็นภาพรวมของทั้งสาขา ไม่ใช่แค่การสำรวจแบบผิวเผิน แต่เป็นวิธีที่ทำให้ได้สัมผัสกระบวนการสร้างสรรค์นั้นอีกครั้ง จุดประสงค์คือการฉายวิวัฒนาการทั้งหมดของวิทยาการคอมพิวเตอร์อย่างรวดเร็วให้กับนักศึกษาที่มีพื้นฐานอยู่บ้างแล้ว เพื่อสร้างมุมมองที่เป็นเอกภาพต่อสาขานี้”
ลิสต์นี้ให้ความรู้สึกเหมือนเป็นการรวมกันที่แปลกอยู่หน่อย ไม่ชัดว่ากำลังเลือกงานวิจัยที่มีอิทธิพลต่อวิทยาการคอมพิวเตอร์ หรือก็คือ ทฤษฎีการคำนวณ หรือเลือกงานวิจัยที่มีอิทธิพลต่อเทคโนโลยี หรือแค่เรียก “ทุกอย่างที่เกี่ยวกับคอมพิวเตอร์” ว่าวิทยาการคอมพิวเตอร์กันแน่
งานของ Turing เป็นรากฐานของวิทยาการคอมพิวเตอร์ก็จริง แต่ก็สงสัยว่าถ้าไม่มีงานนั้น เทคโนโลยีจะพัฒนาไปต่างออกไปไหม วิศวกรซอฟต์แวร์ส่วนใหญ่ไม่เคยอ่านด้วยซ้ำ ในทางกลับกัน มาตรฐาน IP เป็นหมุดหมายทางเทคโนโลยี แต่แทบไม่มีเนื้อหาเชิงวิทยาศาสตร์ และใกล้เคียงกับสเปกโปรโตคอลที่ค่อนข้างเรียบง่ายซึ่งต้องรู้หากทำงานเกี่ยวกับเครือข่าย
“On Computable Numbers, with an Application to the Entscheidungsproblem” มีอายุเกือบ 90 ปีแล้ว แต่ทุกวันนี้ก็ยังจริงและใช้ได้เหมือนตอนนั้น ส่วน PageRank ยังเกี่ยวข้องเท่ากับปี 1998 หรือไม่ ยิ่งไปกว่านั้นอีก 50 ปีข้างหน้าจะยังเป็นแบบนั้นไหม ก็ไม่ค่อยแน่ใจ
เป็นลิสต์งานวิจัยที่ดี ผมอ่านไปแล้ว 5 ใน 7 ชิ้นในลิสต์ ที่ยังไม่ได้อ่านคือบทความของ Cerf กับ Kahn และบทความของ Berners-Lee
บทความว่าด้วยความสามารถในการคำนวณ ของ Turing ตามอ่านยากเป็นพิเศษ เพราะเขาตั้งชื่อสิ่งต่าง ๆ ด้วยอักษรใหญ่แบบกอทิก และตัวอักษรเหล่านั้นก็ดูคล้ายกันไปหมด ต้องดูเอกสารประกอบถึงจะอ่านบทความนั้นได้ ถ้าเป็นตอนนี้ ผมแนะนำให้อ่านคู่กับหนังสืออธิบายของ Charles Petzold https://www.amazon.com/Annotated-Turing-Through-Historic-Com...
บทความ NP-completeness ของ Cook ก็ยากเช่นกัน และเหมือนบทความของ Turing คือต้องมีเอกสารประกอบ ถ้าเป็นตอนนี้ ผมแนะนำให้อ่านหนังสือเบื้องต้นด้านความซับซ้อนเชิงคำนวณที่พาไล่ตามบทพิสูจน์ของ Cook ก่อน
บทความของ Shannon เขียนได้ชัดเจนและงดงามราวกับงานศิลปะ แต่ไม่ใช่บทความที่อ่านสบาย ๆ เลย
เท่าที่จำได้ บทความของ Brin กับ Page และบทความของ Codd ไม่ได้ยากมากนัก แต่ถ้าจะเข้าใจงานของ Brin กับ Page ก็ต้องมีความรู้พีชคณิตเชิงเส้นอยู่บ้าง
“อัลกอริทึมวนซ้ำอย่างง่าย” เป็นวิธีหาจุดตรึงของ contraction mapping ใด ๆ ไม่ว่าจะเป็นเชิงเส้นหรือไม่ก็ตาม ความจริงที่ว่ามันเป็น eigenvector ด้วยนั้นกลับค่อนข้างเป็นสิ่งรบกวนเสียมากกว่า และถ้าเป็นคนที่รู้จริง ก็คงไม่ใช้ Gaussian elimination
.texได้ การขอให้ GPT ช่วยเปลี่ยนชื่อตัวแปรให้อ่านง่ายขึ้น เป็นชื่อที่ยาวกว่าตัวอักษรตัวเดียว จะช่วยได้ถ้าคิดว่า A Mathematical Theory of Communication ของ Shannon คือคุณูปการที่พื้นฐานที่สุดที่เขาทิ้งไว้ให้วิทยาการคอมพิวเตอร์ แสดงว่ายังไม่เคยเห็นวิทยานิพนธ์ปริญญาโทที่เขาเขียนไว้ก่อนหน้านั้น 10 ปี
https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a...
เขาเสนอว่าสามารถนิยาม ตรรกะบูลีน ด้วยองค์ประกอบสวิตช์ในวงจร หรือก็คือทรานซิสเตอร์ได้
แน่นอนว่าไม่ได้ตั้งใจจะลดความสำคัญของผลงานที่วางรากฐานให้ทฤษฎีสารสนเทศทั้งหมด
คำอธิบายที่ว่า “แสดงให้เห็นว่าหากบางสิ่งคำนวณได้ โดยหลักการแล้วเครื่องจักรก็สามารถประมวลผลได้ และวาดภาพ ‘Turing Machine’ ในจินตนาการขึ้นมา” ไม่ใช่สิ่งที่ Turing พิสูจน์
สิ่งที่เขาพิสูจน์ในบทความนั้นคือมี ปัญหาที่ Turing Machine แก้ไม่ได้ อยู่ และดังนั้นก็น่าจะไม่มีเครื่องจักรใดแก้ได้ ปัญหา Entscheidungsproblem หรือปัญหาการตัดสินใจที่อยู่ในชื่อนั่นเอง
สิ่งที่ข้อความต้นฉบับชี้ถึงคือสิ่งที่เรียกว่า Church-Turing Thesis ซึ่งตามตัวอักษรแล้วใกล้เคียงกับข้อเสนอเชิงหลักการ จริง ๆ แล้วพิสูจน์ไม่ได้ แต่มีเหตุผลให้เชื่ออย่างหนักแน่นมาก เพราะตลอดเกือบ 100 ปีที่ผ่านมา เรายังไม่พบระบบการคำนวณที่ทรงพลังกว่า Turing Machine
แทนที่จะสร้างเครื่องจักรที่บรรจุความจริงที่รู้ทั้งหมด การสำรวจ AI ที่อิงเครื่องจักรในยุคใหม่โดยมากกลับใกล้เคียงกับการคุ้ยและเรียบเรียงข้อคิดเห็นของมนุษย์ให้เป็นเครื่องจักรแบบ feuilleton มากกว่า และต่างจากแนวทางสัจพจน์แบบ Leibniz
งานดีเลย ผมเองก็กำลังทำอะไรคล้าย ๆ กันเป็นการส่วนตัว เลยขอแนะนำเพิ่มอีกสักสองสามชิ้น
RSA: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (1978)
PageRank: The PageRank Citation Ranking: Bringing Order to the Web (1999)
MapReduce: MapReduce: simplified data processing on large clusters (2008)
Bitcoin: Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
Backpropagation: Learning representations by back-propagating errors (1986)
ตรรกะของ Hoare: An Axiomatic Basis for Computer Programming (1969)
แล้ว Evolution of Unix time-sharing systems อันโด่งดังของ Dennis Ritchie หายไปไหน?
https://www.bell-labs.com/usr/dmr/www/cacm.pdf
https://web.archive.org/web/20070926212100/http://www.almade...
ในเมื่อทุกคนกำลังเสริมรายการแนะนำของตัวเอง ผมก็ขอเพิ่มอีกสักอัน: แม้ Cook จะเป็นคนแนะนำ NP-completeness เป็นครั้งแรก แต่บทความของ Karp ที่นำเสนอปัญหา 21 ข้อซึ่งสามารถลดรูปแบบเวลาเชิงพหุนามไปเป็น 3SAT ได้ ก็เป็นรากฐานสำคัญขนาดใหญ่ที่จุดประกายความสนใจต่อทฤษฎีของ Cook ในวงกว้างขึ้น
https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_proble...
New Directions in Cryptography (1976) ของ Diffie และ Hellman หลุดไปหรือเปล่า?
แม้จะไม่ใช่บทความวิชาการ แต่ Why Software Is Eating the World ของ Marc Andreessen และจดหมายถึงผู้ถือหุ้นฉบับแรกของ Amazon ในปี 1997 ก็ควรค่าแก่การกล่าวถึงเป็นพิเศษ
“บริษัทในทุกอุตสาหกรรมควรถือไว้ก่อนว่าการปฏิวัติซอฟต์แวร์กำลังจะมาถึง ซึ่งรวมถึงอุตสาหกรรมที่ทุกวันนี้ขับเคลื่อนด้วยซอฟต์แวร์อยู่แล้วด้วย”
https://a16z.com/why-software-is-eating-the-world/
“แต่ตอนนี้ยังเป็น Day 1 ของอินเทอร์เน็ต และหากเราดำเนินการได้ดี ก็จะเป็น Day 1 สำหรับ Amazon.com ด้วย”
https://www.aboutamazon.com/news/company-news/amazons-origin...