ผลต่างระหว่างรุ่นของ "ปัญหาการตัดสินใจ"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
หน้าใหม่: '''ปัญหาการตัดสินใจ''' {{Lang-en|Decision Problem}} เป็นปัญหาในทฤษฎีการคำนวณได้แ... |
ล เก็บกวาดทันใจด้วยสจห. |
||
บรรทัด 15:
== การตัดสินได้และการรับรองได้ ==
การพิจารณาว่าปัญหาการตัดสินใจหนึ่งๆ เป็นปัญหาที่แก้ได้หรือไม่เป็นประเด็นที่สำคัญใน[[ทฤษฎีการคำนวณได้]] [[ทฤษฎีการคำนวณได้]] จึงได้นิยามศัพท์คำว่า '''การตัดสินได้''' และ '''การรับรองได้''' โดยนิยามไว้ดังนี้
* ปัญหาที่ '''ตัดสินได้ (decidable) ''' '''แก้ได้ (solvable) ''' หรือ '''รู้จำได้ (recognizable) ''' หมายถึงปัญหาที่มี[[เครื่องจักรทัวริง]]ที่สามารถตอบปัญหานี้ได้ว่า "ใช่" หรือ "ไม่ใช่" เสมอสำหรับทุกๆ อินพุต ปัญหานี้จะมีความสัมพันธ์กับ [[recursive set]]
* ปัญหาที่ '''รับรองได้ (acceptable) ''' หมายถึงปัญหาที่มี[[เครื่องจักรทัวริง]]ที่สามารถตอบปัญหานี้ได้ว่า "ใช่" เสมอสำหรับอินพุตที่ "ใช่" แต่สำหรับอินพุตที่ "ไม่ใช่" [[เครื่องจักรทัวริง]] อาจตอบว่า "ไม่ใช่" หรือติด[[วงวน]] (loop) จนไม่ตอบคำถามได้ ปัญหานี้จะมีความสัมพันธ์กับ [[recursively enumerable set]]
* ปัญหาที่ '''ตัดสินไม่ได้ (undecidable) ''' หมายถึงปัญหาการตัดสินใจอื่นๆ ที่ไม่ใช่ '''ปัญหาที่ตัดสินได้'''
จะสังเกตเห็นว่า '''ปัญหาที่ตัดสินได้'''ย่อมเป็น'''ปัญหาที่รับรองได้'''ไปด้วยและ'''ปัญหาที่ตัดสินไม่ได้'''อาจเป็น'''ปัญหาที่รับรองได้'''ก็ได้ ยกตัวอย่างปัญหาที่ตัดสินไม่ได้แต่รับรองได้เช่น [[ปัญหาการยุติการทำงาน]] เป็นต้น
| |||