สารบัญ:
- เมื่อปัญหาเรียกว่ากึ่งตัดสินใจได้
- ปัญหาที่ตัดสินได้บางส่วนคืออะไร
- ปัญหาการหยุดชะงักบางส่วนตัดสินใจได้หรือไม่
- ทำไมปัญหาการหยุดชะงักจึงตัดสินใจกึ่งตัดสินใจได้
2024 ผู้เขียน: Fiona Howard | [email protected]. แก้ไขล่าสุด: 2024-01-10 06:43
– ปัญหาการตัดสินใจ P ถูกกล่าวว่าเป็นแบบกึ่งตัดสินใจได้ (เช่น มีกึ่งอัลกอริธึม) ถ้าภาษา L ของอินสแตนซ์ใช่ทั้งหมดสำหรับ P คือ r.e – (ปัญหาความเท่าเทียมกันสำหรับ DFA) จาก DFA สองรายการ พวกเขายอมรับภาษาเดียวกันหรือไม่ หลักฐาน: เรียกคืนข้อโต้แย้งของคันทอร์จากการบรรยายครั้งแรก
เมื่อปัญหาเรียกว่ากึ่งตัดสินใจได้
ปัญหากึ่งตัดสินใจได้คือปัญหาสำหรับ ซึ่งเครื่องทัวริงหยุดรับอินพุตที่ยอมรับ แต่มันสามารถหยุดหรือวนซ้ำตลอดไปในอินพุตซึ่งถูกปฏิเสธโดยเครื่องทัวริง. ปัญหาดังกล่าวเรียกว่าปัญหาที่รู้จักทัวริง
ปัญหาที่ตัดสินได้บางส่วนคืออะไร
คำจำกัดความ: หนึ่ง ที่มีภาษาที่เกี่ยวข้อง เป็นภาษาที่นับซ้ำได้ในทำนองเดียวกัน มีอัลกอริทึมที่หยุดและส่งออก 1 สำหรับทุกอินสแตนซ์ที่มีคำตอบ "ใช่" แต่สำหรับอินสแตนซ์ที่มีคำตอบ "ไม่" จะได้รับอนุญาตให้ไม่หยุดหรือหยุดและส่งออก 0
ปัญหาการหยุดชะงักบางส่วนตัดสินใจได้หรือไม่
อลัน ทัวริง พิสูจน์ในปี 1936 ว่าอัลกอริธึมทั่วไปที่ทำงานบนเครื่องทัวริงซึ่งแก้ปัญหาการหยุดชะงักของคู่โปรแกรม-อินพุตที่เป็นไปได้ทั้งหมดนั้นไม่จำเป็นต้องมีอยู่จริง ดังนั้น การหยุดนิ่งจึงตัดสินใจไม่ได้สำหรับเครื่องจักรทัวริง.
ทำไมปัญหาการหยุดชะงักจึงตัดสินใจกึ่งตัดสินใจได้
ภาษาหนึ่งเรียกว่ากึ่งตัดสินใจได้ถ้ามีเครื่องทัวริงที่ หยุดถ้าคำนั้นเป็นของภาษานั้น (กรณีใช่) และอาจปฏิเสธหรือกลายเป็นอนันต์ วนซ้ำหากคำนั้นไม่ได้อยู่ในภาษา (ไม่มีตัวพิมพ์ใหญ่)
