Aritmetik Hiyerarşi
Aritmetik hiyerarşi, doğal sayı kümelerini tanımlamak için gereken alternatif niceleyicilerin sayısına göre sınıflandırmakta, mantıksal karmaşıklığı hesaplanamazlık derecelerine bağlamaktadır.
Tanım
Aritmetik hiyerarşi, birinci dereceden aritmetikte tanımlanabilen kümeleri, hesaplanabilir bir matrisin önündeki sınırsız niceleyicilerin alternasyonlarını sayarak katmanlandırmaktadır; burada sigma-n kümeleri bir varoluşsal niceleyiciyle başlayan bir blokla, pi-n kümeleri ise bir evrensel niceleyiciyle başlayan bir blokla tanımlanmaktadır.
Kapsam
Bu konu, tanımlanabilir kümelerin hesaplanabilir ilişkiler üzerindeki niceleyici alternasyonu yoluyla sigma, pi ve delta seviyelerine sınıflandırılmasını, Post teoreminin hiyerarşiyi yinelenen durma problemi ve Turing sıçramalarıyla ilişkilendirmesini, hiyerarşinin kesinliğini ve analitik hiyerarşiye genişletilmesini kapsamaktadır.
Temel sorular
- Niceleyici alternasyonu bir kümenin karmaşıklığını nasıl ölçmektedir?
- Her seviyedeki sigma, pi ve delta sınıfları birbirleriyle nasıl ilişkilidir?
- Hiyerarşi, durma problemini yinelemeye nasıl karşılık gelmektedir?
- Hiyerarşi neden kesindir ve her seviye bir öncekinden neden daha büyüktür?
Temel kuramlar
- Niceleyici sınıflandırması
- Bir küme, hesaplanabilir bir ilişki üzerinde varoluşsal olarak başlayan n alternatif niceleyici bloğu ile tanımlanabiliyorsa sigma-n, evrensel olarak başlıyorsa pi-n olarak adlandırılmaktadır; hesaplanabilir şekilde sayılabilir kümeler tam olarak sigma-bir kümeleridir.
- Post teoremi
- Bir küme, n-inci Turing sıçramasına göre hesaplanabilir şekilde sayılabilir olduğunda tam olarak sigma-(n+1) olarak kabul edilmekte, böylece hiyerarşinin seviyeleri yinelenen göreceli durma problemlerine bağlanmaktadır.
- Hiyerarşinin kesinliği
- Her Turing sıçraması bir öncekinden kesinlikle daha karmaşıktır, bu nedenle aritmetik hiyerarşinin her seviyesi altındaki seviyeleri içermekte ve hiyerarşi çökmemektedir.
Klinik önem
Aritmetik hiyerarşi, mantık ve bilgisayar bilimlerindeki tanımlanabilir problemlerin karmaşıklığı için standart bir ölçüt olarak kabul edilmektedir: hesaplanabilir kümelerin toplamlık, sonluluk ve eş-sonluluk gibi problemlerini belirli seviyelere yerleştirmekte ve hesaplanabilir şekilde sayılabilir olan ile daha güçlü hesaplanamaz kaynaklar gerektiren arasındaki sınırı belirlemektedir.
Tarihçe
Kleene ve Mostowski, 1943 civarında aritmetik hiyerarşiyi bağımsız olarak tanıtmış, kümeleri hesaplanabilir yüklemler üzerindeki niceleyici karmaşıklığına göre sınıflandırmışlardır. Post teoremi, hiyerarşiyi Turing sıçramasına bağlayarak tanımlanabilirlik tabanlı ve hesaplanabilirlik tabanlı perspektifleri birleştirmiş, bu çerçeve daha sonra analitik hiyerarşiye doğru genişletilmiştir.
Öne çıkan isimler
- Stephen Cole Kleene
- Andrzej Mostowski
- Emil Post
İlgili konular
Temel eserler
- rogers1987
- soare1987
- cutland1980
Sıkça sorulan sorular
- Hiyerarşide daha yüksek bir seviye ne anlama gelmektedir?
- Daha fazla alternatif niceleyici, daha karmaşık bir tanım ve Post teoremi uyarınca, durma probleminin daha fazla yinelemesini gerektiren bir problem anlamına gelmektedir. Hiyerarşide daha yüksek seviyelerdeki kümeler, altlarındaki kümelere göre hesaplamaya kesinlikle daha az erişilebilirdir.
- Hesaplanabilir şekilde sayılabilir kümeler nerede yer almaktadır?
- Hesaplanabilir şekilde sayılabilir kümeler, hesaplanabilir bir ilişki üzerinde tek bir varoluşsal niceleyici ile tanımlanabilen sigma-bir seviyesinde yer almaktadır. Bu kümelerin tümleyenleri pi-bir seviyesinde bulunmakta ve her ikisi de olan delta-bir kümeleri ise tam olarak hesaplanabilir kümelerdir.