เซตแจงนับเชิงคำนวณได้และระดับทัวริง

เซตแจงนับเชิงคำนวณได้คือเซตที่สมาชิกสามารถแจงนับได้อย่างมีประสิทธิภาพ และระดับทัวริงจัดอันดับเซตทั้งหมดตามความสามารถในการคำนวณสัมพัทธ์ จัดระเบียบภูมิทัศน์ของปัญหาที่แก้ไขไม่ได้

Definition

เซตหนึ่งเป็นเซตแจงนับเชิงคำนวณได้หากมีอัลกอริทึมบางอย่างที่แจงนับสมาชิกของเซตนั้นได้อย่างแม่นยำ เซตหนึ่งสามารถลดทอนแบบทัวริงได้ไปยังอีกเซตหนึ่งหากสามารถคำนวณได้โดยใช้อีกเซตหนึ่งเป็นออราเคิล และคลาสสมมูลภายใต้การลดทอนร่วมกันคือระดับทัวริง ซึ่งจัดเรียงตามลำดับบางส่วนโดยความสามารถในการคำนวณสัมพัทธ์

Scope

หัวข้อนี้ครอบคลุมเซตแจงนับเชิงคำนวณได้และคุณสมบัติพื้นฐาน การลดทอนแบบทัวริงและอันดับบางส่วนของระดับทัวริง เซตการหยุดทำงานในฐานะเซตแจงนับที่สมบูรณ์ ปัญหาของโพสต์และการแก้ไขด้วยวิธีลำดับความสำคัญ และทฤษฎีโครงสร้างของระดับแจงนับเชิงคำนวณได้

Core questions

• อะไรคือความแตกต่างระหว่างเซตที่คำนวณได้และเซตที่เพียงแค่แจงนับเชิงคำนวณได้?
• การลดทอนแบบทัวริงเปรียบเทียบความยากของสองเซตได้อย่างไร?
• มีระดับแจงนับเชิงคำนวณได้ที่อยู่ระหว่างเซตที่คำนวณได้กับปัญหาการหยุดทำงานอย่างเคร่งครัดหรือไม่?
• โครงสร้างโดยรวมของระดับความไม่สามารถแก้ไขได้เป็นอย่างไร?

Key theories

ส่วนเติมเต็มและเซตการหยุดทำงาน

เซตหนึ่งจะคำนวณได้ก็ต่อเมื่อทั้งเซตนั้นและส่วนเติมเต็มของมันเป็นเซตแจงนับเชิงคำนวณได้ และเซตการหยุดทำงานเป็นเซตแจงนับเชิงคำนวณได้แต่ไม่สามารถคำนวณได้ ซึ่งเป็นเซตแจงนับที่สมบูรณ์ตามแบบฉบับ

ปัญหาของโพสต์และวิธีลำดับความสำคัญ

โพสต์ถามว่ามีระดับแจงนับเชิงคำนวณได้ที่อยู่ระหว่างเซตที่คำนวณได้กับปัญหาการหยุดทำงานอย่างเคร่งครัดหรือไม่ ฟรีดเบิร์กและมัชนิกตอบว่ามีโดยการคิดค้นวิธีลำดับความสำคัญแบบบาดเจ็บจำกัด

โครงสร้างของระดับทัวริง

ระดับทัวริงและระดับแจงนับเชิงคำนวณได้ก่อให้เกิดโครงสร้างที่อุดมสมบูรณ์และมีการจัดเรียงอย่างหนาแน่น ซึ่งศึกษาผ่านการสร้างลำดับความสำคัญขั้นสูง เผยให้เห็นคุณสมบัติการนิยามและการฝังที่ซับซ้อน

Clinical relevance

ทฤษฎีระดับทัวริงให้การจำแนกปัญหาที่แก้ไขไม่ได้อย่างละเอียด แสดงให้เห็นว่าการตัดสินใจไม่ได้มีหลายระดับที่เพิ่มขึ้นอย่างเคร่งครัด และวิธีลำดับความสำคัญที่พัฒนาขึ้นเพื่อศึกษาปัญหาเหล่านี้เป็นเทคนิคการพิสูจน์หลักที่มีอิทธิพลต่อคณิตศาสตร์ย้อนกลับและการวิเคราะห์ความสุ่มเชิงอัลกอริทึม

History

โพสต์ได้แนะนำเซตแจงนับเชิงคำนวณได้และตั้งปัญหาของเขาในปี 1944 โดยถามว่ามีระดับแจงนับที่ไม่สมบูรณ์และไม่สามารถคำนวณได้หรือไม่ ฟรีดเบิร์กและมัชนิกได้แก้ไขปัญหานี้อย่างอิสระประมาณปี 1956 ด้วยวิธีลำดับความสำคัญ ซึ่งกลายเป็นเครื่องมือหลักสำหรับการศึกษาโครงสร้างเชิงลึกของระดับทัวริงที่ดำเนินการโดยแซคส์ โซอาเร และนักวิจัยอื่นๆ อีกมากมาย

Key figures

• Emil Post
• Richard Friedberg
• Albert Muchnik
• Robert Soare

Seminal works

• soare1987
• post1944
• rogers1987

Frequently asked questions

ออราเคิลในทฤษฎีความสามารถในการคำนวณคืออะไร?

ออราเคิลคือแหล่งข้อมูลภายนอกที่ตอบคำถามเกี่ยวกับการเป็นสมาชิกสำหรับเซตที่กำหนดไว้ทันที เครื่องจักรที่มีออราเคิลสามารถใช้คำตอบเหล่านั้นระหว่างการคำนวณได้ และการลดทอนแบบทัวริงถามว่าเซตหนึ่งสามารถคำนวณได้โดยเครื่องจักรที่ติดตั้งอีกเซตหนึ่งเป็นออราเคิลหรือไม่

ทำไมปัญหาของโพสต์จึงมีความสำคัญ?

มันถามว่าความไม่สามารถแก้ไขได้มีระดับกลางในหมู่เซตแจงนับเชิงคำนวณได้หรือไม่ ระหว่างปัญหาที่ตัดสินใจได้กับปัญหาการหยุดทำงาน คำตอบที่เป็นบวกเผยให้เห็นโครงสร้างละเอียดของระดับทัวริงและต้องใช้วิธีลำดับความสำคัญ ซึ่งเป็นเทคนิคใหม่ที่มีประสิทธิภาพที่ได้กำหนดทิศทางของวิชานี้ทั้งหมด