จากวิกิพีเดีย สารานุกรมเสรี
 |
บทความนี้มีลิงก์แทรกในบทความที่ข้ามไปภาษาอื่นโดยเป็นลิงก์สีฟ้าอ่อน
โดยผู้เขียนใส่ไว้เพื่อสะดวกในการเขียน และควรแก้ลิงก์ภาษาอื่นเป็นข้อความธรรมดา เมื่อมีลิงก์ภาษาไทยที่ถูกต้อง หรือเห็นควร เพื่อไม่ให้ผู้อ่านสับสน |
การคำนวณ หรือ การคณนา สามารถนิยามได้ว่าเป็นการหาคำตอบของปัญหาจากข้อมูลป้อนเข้าโดยการใช้อัลกอริทึม ศาสตร์ที่ศึกษาเกี่ยวกับเรื่องนี้คือ ทฤษฎีการคำนวณ ซึ่งเป็นสาขาย่อยของวิทยาการคอมพิวเตอร์และคณิตศาสตร์ เป็นเวลากว่าพันปีที่การคำนวณนั้นกระทำด้วยปากกาและกระดาษ หรือชอล์กและกระดานชนวน หรือด้วยการใช้สมอง โดยบางครั้งมีการใช้ตารางประกอบด้วย
การศึกษาเกี่ยวกับ ทฤษฎีการคำนวณ เริ่มขึ้นเมื่อต้นศตวรรษที่ยี่สิบ ก่อนจะมีการคิดค้นคอมพิวเตอร์อิเล็กทรอนิกส์ขึ้น
ในช่วงเวลาดังกล่าว นักคณิตศาสตร์ได้เริ่มศึกษาว่า ปัญหาทางคณิตศาสตร์ใดบ้างที่สามารถแก้ได้ด้วยวิธีพื้นฐาน และปัญหาใดที่ไม่สามารถแก้ได้ ขั้นตอนแรกก็คือการนิยามให้ได้ว่าวิธีพื้นฐานในการแก้ปัญหานั้นคืออะไรบ้าง นั่นคือ พวกเขาต้องการโมเดลอย่างเป็นทางการของการคำนวณ (formal model of computation)
ได้มีการสร้างโมเดลในรูปแบบต่างๆ มากมาย โมเดลเครื่องจักรทัวริงมองการคำนวณเป็นการทำงานของเครื่องจักรที่ทำงานบนเทปเก็บตัวอักษรที่มีความยาวไม่จำกัด โดยมีหัวอ่าน/เขียนที่จะทำงานกับช่องบนเทปทีละช่อง อีกโมเดลหนึ่งพิจารณาการคำนวณผ่านทางฟังก์ชันเวียนบังเกิด ซึ่งใช้ฟังก์ชันและการประกอบกัน (composition) ของฟังก์ชันที่ทำงานบนตัวเลข โมเดลแลมดาแคลคูลัสใช้วิธีคล้ายๆกัน นอกจากนี้ยังมีโมเดลอื่นๆ เช่น อัลกอริทึมของมาคอฟและระบบของโพสต์ที่ใช้ไวยากรณ์บนสตริง โมเดลทางการต่างๆเหล่านี้ได้รับการแสดงว่ามีความสามารถเทียบเท่ากัน นั่นคือ การคำนวณใดๆที่กระทำได้โดยโมเดลหนึ่งจะสามารถทำได้ในอีกโมเดลด้วยเช่นกัน โมเดลเหล่านี้ยังมีความสามารถเท่ากันกับเครื่องคอมพิวเตอร์ทั่วไปที่เราใช้อยู่ ถ้าเราสมมติว่าเครื่องคอมพิวเตอร์นั้นมีหน่วยความจำไม่รู้จบ
นอกจากนี้ ยังเป็นที่เชื่อกันอีกว่า ทุกๆ โมเดลการคำนวณที่ "สมเหตุสมผล" จะมีความสามารถเทียบเท่ากับเครื่องจักรทัวริ่ง ซึ่งความเชื่อนี้เรียกว่า ข้อปัญหาของเชิร์ช-ทัวริง (Church-Turing thesis) ศาสตร์ที่ศึกษาเกี่ยวกับขอบเขตของปัญหาที่คำนวณได้ด้วยโมเดลของเครื่องจักรแบบต่างๆนั้นคือ ทฤษฎีการคำนวณได้
ทฤษฎีการคำนวณศึกษาโมเดลการคำนวณ พร้อมๆกับขีดจำกัดของการคำนวณ เช่น ปัญหาใดที่สามารถพิสูจน์ได้ว่าไม่สามารถแก้ได้ด้วยคอมพิวเตอร์? (ดู ปัญหาการยุติการทำงาน หรือ ปัญหาความสัมพันธ์ของโพสต์) ปัญหาใดบ้างที่สามารถแก้ไขได้ด้วยคอมพิวเตอร์ แต่ต้องการเวลามหาศาลจนทำให้การหาคำตอบนั้นเป็นไปไม่ได้ (ดู en:Presburger arithmetic) การหาคำตอบยากกว่าการตรวจคำตอบของปัญหาหรือไม่ (ดู กลุ่มความซับซ้อน พี และ เอ็นพี) ศาสตร์ที่ศึกษาเกี่ยวกับเวลาและเนื้อที่ที่ต้องการสำหรับปัญหาต่างๆ คือ ทฤษฎีความซับซ้อนในการคำนวณ
นอกจากโมเดลในการคำนวณทั่วไปแล้ว ยังมีรูปแบบในการคำนวณอื่นๆ ที่ง่ายกว่านั้น เช่น โมเดลของนิพจน์ regular ที่เป็นวิธีที่ใช้กำหนดรูปแบบของสตริงในยูนิกซ์ และในบางภาษาคอมพิวเตอร์ เช่น ภาษาเพิร์ล โดยมีโมเดล เช่น เครื่องจักรสถานะจำกัดที่มีความสามารถเทียบเท่ากัน โมเดลที่มีความสามารถกว่าโมเดลนิพจน์ regular เช่น โมเดลที่อธิบายการคำนวณผ่านทางไวยากรณ์ที่ไม่ขึ้นกับสภาพรอบข้าง (context-free grammar) ใช้สำหรับระบุไวยากรณ์ของภาษาโปรแกรม โดยที่มีเครื่องจักรกดลง (pushdown automata) เป็นอีกรูปแบบที่เทียบเท่ากัน ฟังก์ชันเวียนบังเกิดพื้นฐานก็เป็นโมเดลย่อยของฟังก์ชันเวียนบังเกิด
โมเดลที่แตกต่างกันอาจมีความสามารถที่แตกต่างกันได้ อีกวิธีหนึ่งที่จะวัดความสามารถของโมเดลต่างๆ ก็คือการศึกษากลุ่มของภาษาทางการ (formal language) ที่โมเดลเหล่านั้นสามารถสร้างได้ ยกตัวอย่างเช่น เครื่องจักรสถานะจำกัดสามารถสร้างได้เพียงภาษาที่เทียบเท่ากับนิพจน์ regular ส่วนเครื่องจักรกดลงนั้นสามารถสร้างภาษาที่ระบุด้วยไวยากรณ์ที่ไม่ขึ้นกับสภาพรอบข้างได้ด้วย ระดับความสามารถทางภาษาทางการของโมเดลเหล่านี้เป็นที่มาของระดับชั้นของ Chomsky
ตารางด้านล่างแสดงกลุ่มของปัญหา (หรือภาษา หรือไวยากรณ์) ที่พิจารณาในทฤษฎีการคำนวณได้. ถ้ากลุ่ม X เป็นซับเซ็ตแท้ของ Y เราจะแสดง X ด้านล่าง Y และมีเส้นทึบเชื่อมระหว่างสองกลุ่ม. ถ้า X เป็นซับเซ็ตแต่ไม่ทราบแน่นอนว่าจะเท่ากันหรือไม่ เราจะเชื่อมด้วยเส้นที่บางกว่าและเป็นเส้นประ.
[แก้] ข้อมูลเพิ่มเติม
- Garey, Michael R., and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. The standard reference on NP-Complete problems - an important category of problems whose solutions appear to require an impractically long time to compute.
- Hein, James L: Theory of Computation. Sudbury, MA: Jones & Bartlett, 1996. A gentle introduction to the field, appropriate for second-year undergraduate computer science students.
- Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison-Wesley, 1979. One of the standard references in the field.
- Taylor, R. Gregory: Models of Computation. New York: Oxford University Press, 1998. An unusually readable textbook, appropriate for upper-level undergraduates or beginning graduate students.
- The Complexity Zoo: A huge list of complexity classes, as reference for experts.
- Computability Logic: A theory of interactive computation. The main web source on this new subject.
[แก้] ดูเพิ่ม
