ความสามารถในการคำนวณและการตัดสินใจได้
ทฤษฎีความสามารถในการคำนวณศึกษาข้อจำกัดพื้นฐานของการแก้ปัญหาด้วยขั้นตอนวิธี โดยกำหนดขอบเขตระหว่างปัญหาที่สามารถแก้ไขได้ด้วยกระบวนการที่มีประสิทธิภาพบางอย่าง กับปัญหาที่ไม่มีขั้นตอนวิธีใดสามารถตัดสินใจได้เลย
Definition
ทฤษฎีความสามารถในการคำนวณคือการศึกษาว่าฟังก์ชันและปัญหาการตัดสินใจใดบ้างที่สามารถคำนวณได้ด้วยกระบวนการที่มีประสิทธิภาพ ปัญหาจะตัดสินใจได้ (decidable) หากมีขั้นตอนวิธีบางอย่างที่หยุดทำงานเสมอพร้อมให้คำตอบที่ถูกต้องว่าใช่หรือไม่ใช่ และจะตัดสินใจไม่ได้ (undecidable) หากไม่มีขั้นตอนวิธีดังกล่าวอยู่
Scope
สาขาวิชานี้ครอบคลุมแบบจำลองเชิงรูปนัยของการคำนวณที่มีประสิทธิภาพ เช่น เครื่องจักรทัวริง (Turing machines), วิทยานิพนธ์เชิร์ช-ทัวริง (Church–Turing thesis) ที่ระบุว่าแบบจำลองเหล่านี้สอดคล้องกับแนวคิดเชิงสัญชาตญาณของขั้นตอนวิธี, การมีอยู่ของปัญหาที่ตัดสินใจไม่ได้ (undecidable problems) รวมถึงปัญหาการหยุดทำงาน (halting problem), การลดทอน (reductions) ที่ใช้ในการถ่ายโอนความไม่สามารถแก้ไขได้ระหว่างปัญหา และโครงสร้างของระดับความไม่สามารถแก้ไขได้ (degrees of unsolvability) ที่จำแนกปัญหาที่นอกเหนือจากที่สามารถคำนวณได้
Sub-topics
Core questions
- การที่ปัญหาหนึ่งสามารถแก้ไขได้ด้วยขั้นตอนวิธีหมายความว่าอย่างไร?
- มีปัญหาที่กำหนดไว้อย่างชัดเจนที่ไม่มีขั้นตอนวิธีใดสามารถแก้ไขได้เลยหรือไม่?
- จะใช้ความไม่สามารถแก้ไขได้ของปัญหาหนึ่งเพื่อพิสูจน์ความไม่สามารถแก้ไขได้ของอีกปัญหาหนึ่งได้อย่างไร?
- ปัญหาที่ไม่สามารถแก้ไขได้ถูกจำแนกตามความยากสัมพัทธ์ได้อย่างไร?
Key theories
- แบบจำลองการคำนวณของทัวริง
- เครื่องจักรเชิงนามธรรมของทัวริงได้กำหนดแนวคิดของกระบวนการที่มีประสิทธิภาพอย่างเป็นทางการ และถูกนำมาใช้เพื่อพิสูจน์ว่าปัญหาการหยุดทำงานและปัญหาการตัดสินใจสำหรับตรรกะอันดับหนึ่งไม่สามารถแก้ไขได้ ซึ่งเป็นการกำหนดข้อจำกัดโดยธรรมชาติของการคำนวณ
- การมีอยู่ของปัญหาที่ตัดสินใจไม่ได้
- ด้วยการให้เหตุผลแบบทแยงมุม (diagonal argument) มีปัญหาหลายอย่าง โดยเฉพาะอย่างยิ่งปัญหาการหยุดทำงาน ที่ไม่มีขั้นตอนวิธีใดสามารถตัดสินใจได้ ดังนั้นความไม่สามารถตัดสินใจได้จึงเป็นคุณลักษณะเชิงโครงสร้างที่แพร่หลายมากกว่าที่จะเป็นเพียงความแปลกประหลาด
- ความสมมูลของแบบจำลองการคำนวณ
- เครื่องจักรทัวริง, แคลคูลัสแลมบ์ดา และฟังก์ชันเรียกซ้ำ (recursive functions) กำหนดคลาสเดียวกันของฟังก์ชันที่สามารถคำนวณได้ ซึ่งการบรรจบกันนี้เป็นพื้นฐานของวิทยานิพนธ์เชิร์ช-ทัวริง
Clinical relevance
ผลลัพธ์ของความไม่สามารถตัดสินใจได้ (undecidability) กำหนดข้อจำกัดที่เข้มงวดว่าเครื่องมือซอฟต์แวร์สามารถรับประกันอะไรได้บ้าง: ไม่มีขั้นตอนวิธีทั่วไปใดที่สามารถตัดสินใจได้ว่าโปรแกรมใดๆ จะหยุดทำงาน ถูกต้อง หรือปราศจากข้อบกพร่องบางอย่าง ซึ่งเป็นเหตุผลว่าทำไมเครื่องมือตรวจสอบจึงอาศัยการประมาณค่า ภาษาที่จำกัด และคำแนะนำจากมนุษย์ แทนที่จะเป็นการวิเคราะห์อัตโนมัติที่สมบูรณ์
History
จากปัญหา Entscheidungsproblem ของฮิลเบิร์ต เชิร์ชและทัวริงได้แสดงให้เห็นอย่างอิสระในปี 1936 ว่าไม่มีขั้นตอนวิธีใดที่สามารถตัดสินใจตรรกะอันดับหนึ่ง (first-order logic) ทั้งหมดได้ โดยแบบจำลองเครื่องจักรของทัวริงและแคลคูลัสแลมบ์ดาของเชิร์ชได้รับการพิสูจน์ว่าเทียบเท่ากัน โพสต์และคลีนได้ขยายทฤษฎีนี้ไปสู่การศึกษาระดับความไม่สามารถแก้ไขได้ในทศวรรษต่อมา
Key figures
- Alan Turing
- Alonzo Church
- Kurt Gödel
- Emil Post
Related topics
Seminal works
- turing1937
- church1936
- sipser2013
Frequently asked questions
- ความแตกต่างระหว่างปัญหาที่ตัดสินใจได้และตัดสินใจไม่ได้คืออะไร?
- ปัญหาจะตัดสินใจได้หากมีขั้นตอนวิธีที่หยุดทำงานเสมอและให้คำตอบที่ถูกต้องว่าใช่หรือไม่ใช่สำหรับทุกอินพุต ปัญหาจะตัดสินใจไม่ได้หากไม่มีขั้นตอนวิธีดังกล่าวอยู่ได้เลย ดังที่พิสูจน์แล้วสำหรับปัญหาการหยุดทำงาน ปัญหาที่ตัดสินใจไม่ได้อาจยังคงสามารถจดจำได้ (recognizable) ซึ่งหมายความว่าขั้นตอนวิธีสามารถยืนยันกรณีที่เป็นใช่ได้ แต่อาจทำงานตลอดไปในกรณีที่ไม่ใช่
- ความไม่สามารถตัดสินใจได้หมายความว่าปัญหาเหล่านี้ไม่สามารถแก้ไขได้เลยใช่หรือไม่?
- หมายความว่าไม่มีขั้นตอนวิธีเดียวที่สามารถแก้ไขทุกกรณีได้อย่างถูกต้อง ในทางปฏิบัติ เครื่องมือต่างๆ จะจัดการกับกรณีที่จำกัด ให้คำตอบโดยประมาณหรือแบบอนุรักษ์นิยม หรือแก้ไขหลายกรณีในขณะที่บางครั้งก็ล้มเหลวหรือขอความช่วยเหลือ ดังนั้นความไม่สามารถตัดสินใจได้จึงกำหนดแนวทางในการจัดการกับปัญหามากกว่าที่จะห้ามความก้าวหน้าทั้งหมด