ลำดับชั้นเลขคณิต

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

Definition

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

Scope

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

Core questions

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

Key theories

การจำแนกตัวบ่งปริมาณ

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

ทฤษฎีบทของโพสต์

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

ความเข้มงวดของลำดับชั้น

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

Clinical relevance

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

History

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

Key figures

• Stephen Cole Kleene
• Andrzej Mostowski
• Emil Post

Seminal works

• rogers1987
• soare1987
• cutland1980

Frequently asked questions

ระดับที่สูงขึ้นในลำดับชั้นหมายถึงอะไร?

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

เซตที่สามารถแจงนับได้ด้วยการคำนวณอยู่ที่ใด?

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