Hierarki Aritmetika

Hierarki aritmetika mengklasifikasikan himpunan bilangan asli berdasarkan jumlah kuantor bergantian yang dibutuhkan untuk mendefinisikannya, menghubungkan kompleksitas logis dengan tingkat ketidakkomputasian.

Definition

Hierarki aritmetika menstratifikasi himpunan yang dapat didefinisikan dalam aritmetika orde pertama dengan menghitung pergantian kuantor tak terbatas di depan matriks komputabel, dengan himpunan sigma-n didefinisikan oleh blok yang dimulai dengan kuantor eksistensial dan himpunan pi-n oleh blok yang dimulai dengan kuantor universal.

Scope

Topik ini mencakup klasifikasi himpunan terdefinisi ke dalam tingkat sigma, pi, dan delta berdasarkan pergantian kuantor atas relasi komputabel, teorema Post yang menghubungkan hierarki dengan masalah penghentian berulang dan lompatan Turing, keketatan hierarki, dan perluasannya ke hierarki analitis.

Core questions

• Bagaimana pergantian kuantor mengukur kompleksitas suatu himpunan?
• Bagaimana kelas sigma, pi, dan delta pada setiap tingkat saling berhubungan?
• Bagaimana hierarki ini sesuai dengan pengulangan masalah penghentian?
• Mengapa hierarki ini ketat, dengan setiap tingkat secara tepat lebih besar dari yang terakhir?

Key theories

Klasifikasi kuantor

Suatu himpunan adalah sigma-n jika dapat didefinisikan oleh n blok kuantor bergantian yang dimulai secara eksistensial atas relasi komputabel, dan pi-n jika dimulai secara universal; himpunan yang dapat dihitung secara enumeratif adalah persis himpunan sigma-satu.

Teorema Post

Suatu himpunan adalah sigma-(n+1) tepat ketika himpunan tersebut dapat dihitung secara enumeratif relatif terhadap lompatan Turing ke-n, mengaitkan tingkat hierarki dengan masalah penghentian relatif yang berulang.

Keketatan hierarki

Setiap lompatan Turing secara ketat lebih kompleks daripada yang sebelumnya, sehingga setiap tingkat hierarki aritmetika secara tepat mengandung tingkat di bawahnya dan hierarki tidak runtuh.

Clinical relevance

Hierarki aritmetika adalah tolok ukur standar untuk kompleksitas masalah yang dapat didefinisikan dalam logika dan ilmu komputer: hierarki ini menempatkan masalah seperti totalitas, kefinitan, dan kofinitas himpunan komputabel pada tingkat yang tepat, dan membingkai batas antara apa yang dapat dihitung secara enumeratif dan apa yang membutuhkan sumber daya nonkomputabel yang lebih kuat.

History

Kleene dan Mostowski secara independen memperkenalkan hierarki aritmetika sekitar tahun 1943, mengklasifikasikan himpunan berdasarkan kompleksitas kuantor atas predikat komputabel. Teorema Post menghubungkan hierarki dengan lompatan Turing, menyatukan perspektif berbasis keterdefinisan dan berbasis komputabilitas, dan kerangka kerja ini kemudian diperluas ke atas menjadi hierarki analitis.

Key figures

• Stephen Cole Kleene
• Andrzej Mostowski
• Emil Post

Seminal works

• rogers1987
• soare1987
• cutland1980

Frequently asked questions

Apa arti tingkat yang lebih tinggi dalam hierarki?

Lebih banyak kuantor bergantian berarti definisi yang lebih kompleks dan, menurut teorema Post, masalah yang membutuhkan lebih banyak iterasi masalah penghentian untuk diputuskan. Himpunan yang lebih tinggi dalam hierarki secara ketat kurang dapat diakses oleh komputasi daripada himpunan di bawahnya.

Di mana letak himpunan yang dapat dihitung secara enumeratif?

Himpunan tersebut menempati tingkat sigma-satu, yang dapat didefinisikan oleh satu kuantor eksistensial atas relasi komputabel. Komplemennya menempati tingkat pi-satu, dan himpunan yang keduanya, himpunan delta-satu, adalah persis himpunan komputabel.