ปัญหาที่ไม่สามารถตัดสินใจได้
แนะนำใหม่| English | ความหมาย |
|---|---|
| cannot/ˈkænɒt/ | ไม่สามารถ |
| decidable/dɪˈsaɪdəbl/ | สามารถตัดสินใจได้ |
| undecidable/ˌʌndɪˈsaɪdəbl/ | ไม่สามารถตัดสินใจได้ |
| limit/ˈlɪmɪt/ | ขีดจำกัด |
| inefficient/ɪnɪˈfɪʃənt/ | ไม่มีประสิทธิภาพ |
ไม่ใช่ทุกปัญหาสามารถแก้ได้
- ไม่ใช่ทุกปัญหาสามารถแก้ไขได้ด้วยคอมพิวเตอร์ แม้ในทางทฤษฎีก็ตาม
- เพื่อให้เห็นเหตุผล เราจะแบ่งปัญหาออกเป็นสองประเภท
- ประเภทหนึ่งคอมพิวเตอร์สามารถตอบได้เสมอ; อีกประเภทหนึ่งไม่สามารถทำได้
- นี่คือข้อเท็จจริงที่ยืนยันแล้วของวิทยาการคอมพิวเตอร์ ไม่ใช่ช่องว่างที่เราอาจเติมเต็มได้ในอนาคต
ปัญหาที่ตัดสินใจได้คือปัญหาที่:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
"n เป็นเลขคู่หรือไม่" สามารถตัดสินใจได้ — ตอบได้เสมอ
ปัญหาที่ตัดสินใจได้ (Decidable problems)
- ปัญหาที่ ตัดสินใจได้ มีอัลกอริทึมที่ให้คำตอบใช่หรือไม่ใช่ที่ถูกต้องเสมอสำหรับทุกกรณี
- "เลขนี้-even หรือไม่?" เป็นปัญหาที่ตัดสินใจได้ — มีทดสอบอย่างง่ายที่ตอบได้ถูกต้องเสมอ
- "เลขนี้-prime หรือไม่?" ก็เป็นปัญหาที่ตัดสินใจได้เช่นกัน แม้จะช้าสำหรับตัวเลขที่มีค่ามหาศาล
- หากมีอัลกอริทึมที่ถูกต้องสำหรับ ทุก กรณี ปัญหา tersebutคือปัญหาที่ตัดสินใจได้
สามารถตัดสินใจได้หรือไม่
ปัญหาที่ตัดสินใจได้มีอัลกอริทึมที่ตอบคำถามถูกต้องสำหรับทุกกรณีเสมอ; ปัญหาที่ไม่สามารถตัดสินใจได้ไม่มีอัลกอริทึมเช่นนั้น — เป็นไปไม่ได้ ไม่ใช่แค่ช้า
ปัญหาที่ไม่สามารถตัดสินใจได้:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
บางกรณีทำให้โปรแกรมที่เป็นไปได้ทั้งหมดล้มเหลว
การตัดสินโดยทั่วไปว่าโปรแกรมที่กำหนดให้จะหยุดทำงานหรือไม่:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ไม่มีอัลกอริทึมเดียวที่ตอบคำถามนี้ได้ถูกต้องสำหรับทุกโปรแกรม
ความไม่สามารถตัดสินใจได้กำหนดขอบเขตที่แข็ง ______ ต่อสิ่งที่การคำนวณสามารถทำได้
Difficulty 1/5 · 100 coins + a small bonus on first completion today
บางคำถามไม่มีอัลกอริทึมทั่วไป
ปัญหาที่ตัดสินใจไม่ได้
- ปัญหาที่ตัดสินใจไม่ได้ คือปัญหาที่ไม่มีอัลกอริทึมใดสามารถแก้ได้ทุกกรณีได้อย่างถูกต้อง
- ไม่ว่าโปรแกรมจะฉลาดเพียงใด ก็ยังมีบางกรณีที่จะทำให้มันล้มเหลวได้
- ตัวอย่างคลาสสิก: การตัดสินใจโดยทั่วไปว่าโปรแกรมที่กำหนดให้ใด ๆ จะหยุดการทำงานหรือไม่
- ความไม่สามารถตัดสินใจได้คือ ขีดจำกัด ของสิ่งที่การคำนวณทำได้ — บางคำถามไม่มีอัลกอริทึมทั่วไปคำตอบ
ความไม่ประสิทธิภาพและการไม่สามารถตัดสินใจได้มีความหมายเดียวกัน
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ความไม่ประสิทธิภาพสามารถแก้ได้แต่ช้า; ความไม่สามารถตัดสินใจได้ไม่สามารถแก้ได้ในทุกกรณีเลย
การทดสอบว่าตัวเลขเป็นจำนวนเฉพาะหรือไม่สามารถตัดสินใจได้ แม้ว่าจะช้าสำหรับตัวเลข Huge
Difficulty 1/5 · 100 coins + a small bonus on first completion today
อัลกอริทึมให้คำตอบเสมอ; ช้าไม่ใช่สิ่งเดียวกับไปไม่ได้
ความไม่สามารถตัดสินใจได้ไม่ใช่แค่ความช้า
- อย่าสับสนระหว่างปัญหาที่ตัดสินใจไม่ได้กับปัญหาที่ ไม่มีประสิทธิภาพ เท่านั้น
- ปัญหาที่ ไม่มีประสิทธิภาพ สามารถ แก้ไขได้ เพียงแต่ช้า而已 ปัญหาที่ตัดสินใจไม่ได้นั้น ไม่สามารถ แก้ได้สำหรับทุกกรณีเลย
** prime เทียบกับ halting.** การทดสอบว่าเลขหนึ่งเป็น prime หรือไม่ เป็นปัญหาที่ตัดสินใจได้ — อัลกอริทึมจะตอบเสมอ แม้จะช้าสำหรับตัวเลขมหาศาล แต่การตัดสินใจโดยทั่วไปว่า โปรแกรมใด จะหยุดทำงานหรือไม่ เป็นปัญหาที่ตัดสินใจไม่ได้: ไม่มีอัลกอริทึมเดียวที่ตอบถูกต้องสำหรับทุกโปรแกรม ความช้าไม่ใช่สิ่งเดียวกับความเป็นไปไม่ได้
ปัญหาที่ ตัดสินใจได้ มีอัลกอริทึมที่ตอบได้ถูกต้องเสมอ (เช่น "n เป็น-even หรือไม่", "n เป็น-prime หรือไม่") ปัญหาที่ ตัดสินใจไม่ได้ ไม่มีอัลกอริทึม semacamนั้นสำหรับทุกกรณี (เช่น โปรแกรมจะหยุดหรือไม่) — ซึ่งเป็น ขีดจำกัด จริงของการคำนวณ ปัญหาที่ตัดสินใจไม่ได้หมายความว่า ไม่สามารถ แก้ได้เลย ไม่ใช่แค่ ไม่มีประสิทธิภาพ (ช้า)