ทฤษฎีการคำนวณได้
ทฤษฎีการคำนวณได้ศึกษาว่าปัญหาใดบ้างที่สามารถแก้ไขได้ด้วยอัลกอริทึม และจำแนกปัญหาที่ไม่สามารถแก้ไขได้ตามระดับความยากง่าย
Definition
ทฤษฎีการคำนวณได้ หรือที่เรียกว่า ทฤษฎีการเรียกซ้ำ (recursion theory) เป็นสาขาหนึ่งของตรรกะทางคณิตศาสตร์ที่ทำให้แนวคิดของฟังก์ชันที่คำนวณได้อย่างมีประสิทธิภาพมีความแม่นยำ ศึกษาเซตและฟังก์ชันที่อัลกอริทึมสามารถและไม่สามารถคำนวณได้ และวัดความยากเชิงสัมพัทธ์ของปัญหาที่ไม่สามารถแก้ไขได้
Scope
สาขานี้ครอบคลุมแบบจำลองเชิงรูปนัยของการคำนวณและวิทยานิพนธ์เชิร์ช-ทัวริง (Church-Turing thesis), เซตที่คำนวณได้และเซตที่นับได้โดยการคำนวณ, ปัญหาที่ตัดสินใจไม่ได้ เช่น ปัญหาการหยุดทำงาน (halting problem), ความสามารถในการลดทอน (reducibilities) และระดับทัวริง (Turing degrees) ที่ใช้วัดความไม่สามารถแก้ไขได้เชิงสัมพัทธ์, และลำดับชั้นทางคณิตศาสตร์ (arithmetical hierarchy) ที่จัดลำดับนิยามโดยความซับซ้อนของตัวบ่งปริมาณ (quantifier complexity)
Sub-topics
Core questions
- การที่ฟังก์ชันหรือเซตจะคำนวณได้หมายความว่าอย่างไร?
- ปัญหาธรรมชาติใดบ้างที่ไม่สามารถตัดสินใจได้ด้วยอัลกอริทึม?
- จะเปรียบเทียบและจัดอันดับความยากของปัญหาที่ไม่สามารถแก้ไขได้อย่างไร?
- ความซับซ้อนเชิงตรรกะสอดคล้องกับระดับของการคำนวณได้อย่างไร?
Key theories
- วิทยานิพนธ์เชิร์ช-ทัวริง (Church-Turing thesis)
- แนวคิดเชิงสัญชาตญาณของการคำนวณได้อย่างมีประสิทธิภาพสอดคล้องกับการคำนวณได้ด้วยเครื่องทัวริง ซึ่งเทียบเท่ากับฟังก์ชันเรียกซ้ำและฟังก์ชันที่นิยามด้วยแลมบ์ดา ซึ่งเป็นการกำหนดนิยามทางคณิตศาสตร์ของอัลกอริทึมที่แข็งแกร่ง
- ความไม่สามารถแก้ไขได้ของปัญหาการหยุดทำงาน (Unsolvability of the halting problem)
- ไม่มีอัลกอริทึมใดที่สามารถตัดสินใจได้สำหรับทุกโปรแกรมและข้อมูลนำเข้าว่าโปรแกรมจะหยุดทำงานหรือไม่ ซึ่งเป็นตัวอย่างแรกและเป็นต้นแบบของปัญหาที่ตัดสินใจไม่ได้
- ระดับทัวริง (Turing degrees)
- ความสามารถในการลดทอนแบบทัวริงจัดอันดับเซตตามความสามารถในการคำนวณเชิงสัมพัทธ์ และระดับที่เกิดขึ้นเป็นลำดับบางส่วนที่ซับซ้อน ซึ่งโครงสร้างของมัน รวมถึงการมีอยู่ของระดับกลาง เป็นวัตถุประสงค์หลักของการศึกษา
Clinical relevance
ทฤษฎีการคำนวณได้กำหนดขอบเขตสัมบูรณ์ของความสามารถในการแก้ไขด้วยอัลกอริทึม ซึ่งเป็นรากฐานของวิทยาการคอมพิวเตอร์เชิงทฤษฎี และให้ผลลัพธ์ของการตัดสินใจไม่ได้ เช่น ความไม่สามารถแก้ไขได้ของปัญหาการหยุดทำงานและปัญหาคำ (word problems) ซึ่งปรากฏซ้ำในวิชาคณิตศาสตร์และเป็นข้อมูลสำหรับทฤษฎีความซับซ้อนของการคำนวณ
History
ทฤษฎีการคำนวณได้เกิดขึ้นในทศวรรษ 1930 เมื่อเชิร์ช (Church), ทัวริง (Turing), คลีนี (Kleene) และโพสต์ (Post) ได้กำหนดแนวคิดของกระบวนการที่มีประสิทธิภาพอย่างเป็นอิสระผ่านแคลคูลัสแลมบ์ดา (lambda calculus), เครื่องทัวริง (Turing machines), ฟังก์ชันเรียกซ้ำ (recursive functions) และระบบการรวมกัน (combinatory systems) ซึ่งทั้งหมดได้รับการพิสูจน์ว่าเทียบเท่ากัน โพสต์และคลีนีได้พัฒนาทฤษฎีระดับ (theory of degrees) และลำดับชั้นทางคณิตศาสตร์ และวิธีการจัดลำดับความสำคัญ (priority method) ที่นำมาใช้ในทศวรรษ 1950 ได้ขับเคลื่อนการศึกษาโครงสร้างเชิงลึกของระดับที่นับได้โดยการคำนวณ
Key figures
- Alan Turing
- Alonzo Church
- Stephen Cole Kleene
- Emil Post
Related topics
Seminal works
- soare1987
- rogers1987
- cutland1980
Frequently asked questions
- ทฤษฎีการคำนวณได้เหมือนกับทฤษฎีความซับซ้อนหรือไม่?
- ไม่เหมือนกัน ทฤษฎีการคำนวณได้ถามว่าปัญหาหนึ่งสามารถแก้ไขได้ด้วยอัลกอริทึมใดๆ ได้หรือไม่ โดยไม่คำนึงถึงทรัพยากร ในขณะที่ทฤษฎีความซับซ้อนถามว่าปัญหาที่แก้ไขได้ต้องใช้เวลาหรือหน่วยความจำเท่าใด ทฤษฎีการคำนวณได้ขีดเส้นแบ่งระหว่างปัญหาที่แก้ไขได้และแก้ไขไม่ได้ ส่วนทฤษฎีความซับซ้อนจะจัดระดับด้านที่แก้ไขได้
- ทำไมวิทยานิพนธ์เชิร์ช-ทัวริงจึงไม่ใช่ทฤษฎีบท?
- เนื่องจากเป็นการเทียบเคียงแนวคิดที่ไม่เป็นทางการ นั่นคือ การคำนวณได้อย่างมีประสิทธิภาพ กับแนวคิดทางคณิตศาสตร์ที่แม่นยำ จึงไม่สามารถพิสูจน์ได้อย่างเป็นทางการ การยอมรับวิทยานิพนธ์นี้ขึ้นอยู่กับการบรรจบกันของการกำหนดรูปแบบที่เป็นอิสระหลายอย่างไปยังฟังก์ชันประเภทเดียวกัน ซึ่งเป็นหลักฐานที่แข็งแกร่งมากกว่าการพิสูจน์