Hesaplanabilir Sayılabilir Kümeler ve Turing Dereceleri
Hesaplanabilir sayılabilir kümeler, üyeleri etkin bir şekilde listelenebilen kümelerdir; Turing dereceleri ise tüm kümeleri göreceli hesaplanabilirliklerine göre sıralayarak çözülemeyen problemlerin genel yapısını düzenlemektedir.
Tanım
Bir küme, eğer bir algoritma tam olarak üyelerini listeleyebiliyorsa hesaplanabilir sayılabilir olarak tanımlanır; bir küme, başka bir küme bir kahin (oracle) olarak kullanılarak hesaplanabiliyorsa ona Turing indirgenebilir olarak kabul edilir ve karşılıklı indirgenebilirlik altındaki denklik sınıfları, göreceli hesaplanabilirlik ile kısmen sıralanmış Turing derecelerini oluşturur.
Kapsam
Bu konu, hesaplanabilir sayılabilir kümeleri ve temel özelliklerini, Turing indirgenebilirliğini ve derecelerin kısmi sıralamasını, tam sayılabilir bir küme olarak durma kümesini, Post'un problemini ve öncelik yöntemiyle çözümünü, ayrıca hesaplanabilir sayılabilir derecelerin yapısal kuramını kapsamaktadır.
Temel sorular
- Hesaplanabilir bir küme ile sadece hesaplanabilir sayılabilir bir küme arasındaki fark nedir?
- Turing indirgenebilirliği, iki kümenin zorluğunu nasıl karşılaştırmaktadır?
- Hesaplanabilir kümeler ile durma problemi arasında kesinlikle hesaplanabilir sayılabilir dereceler var mıdır?
- Çözümsüzlük derecelerinin küresel yapısı nasıldır?
Temel kuramlar
- Tümleme ve durma kümesi
- Bir küme, hem kendisi hem de tümleyeni hesaplanabilir sayılabilir olduğunda tam olarak hesaplanabilirdir; durma kümesi ise hesaplanabilir sayılabilir ancak hesaplanabilir değildir ve kanonik tam sayılabilir kümedir.
- Post'un problemi ve öncelik yöntemi
- Post, hesaplanabilir kümeler ile durma problemi arasında kesinlikle hesaplanabilir sayılabilir derecelerin olup olmadığını sormuştur; Friedberg ve Muchnik, sonlu-hasar öncelik yöntemini (finite-injury priority method) icat ederek bu soruya evet yanıtını vermişlerdir.
- Derecelerin yapısı
- Turing dereceleri ve hesaplanabilir sayılabilir dereceler, gelişmiş öncelik yapıları aracılığıyla incelenen zengin, yoğun sıralı yapılar oluşturarak karmaşık tanımlanabilirlik ve gömme özelliklerini ortaya koymaktadır.
Klinik önem
Derece kuramı, çözülemeyen problemlerin ince sınıflandırmasını sağlamaktadır; bu kuram, çözümsüzlüğün sonsuz sayıda kesinlikle artan seviyelerde ortaya çıktığını göstermekte ve bunları incelemek için geliştirilen öncelik yöntemi, tersine matematik ile algoritmik rastgelelik analizini etkileyen merkezi bir ispat tekniği olarak öne çıkmaktadır.
Tarihçe
Post, 1944 yılında hesaplanabilir sayılabilir kümeleri tanıtmış ve eksik, hesaplanamaz sayılabilir derecelerin var olup olmadığını sorarak kendi problemini ortaya koymuştur. Friedberg ve Muchnik, 1956 civarında öncelik yöntemiyle bu problemi bağımsız olarak çözmüşlerdir; bu yöntem, Sacks, Soare ve diğer birçok araştırmacı tarafından yürütülen derecelerin derin yapısal incelemesi için temel bir araç haline gelmiştir.
Öne çıkan isimler
- Emil Post
- Richard Friedberg
- Albert Muchnik
- Robert Soare
İlgili konular
Temel eserler
- soare1987
- post1944
- rogers1987
Sıkça sorulan sorular
- Hesaplanabilirlik kuramında kahin (oracle) nedir?
- Kahin, belirli bir küme için üyelik sorularını anında yanıtlayan harici bir kaynaktır. Kahinli bir makine, hesaplaması sırasında bu yanıtları kullanabilir ve Turing indirgenebilirliği, bir kümenin başka bir küme kahin olarak donatılmış bir makine tarafından hesaplanıp hesaplanamayacağını sorgulamaktadır.
- Post'un problemi neden önemliydi?
- Bu problem, çözümsüzlüğün hesaplanabilir sayılabilir kümeler arasında, karar verilebilir ve durma problemi arasında ara seviyelere sahip olup olmadığını sorgulamıştır. Olumlu yanıt, derecelerin ince bir yapısını ortaya çıkarmış ve tüm konuyu şekillendiren güçlü yeni bir teknik olan öncelik yöntemini gerektirmiştir.