Bu maddede birçok sorun bulunmaktadır. Lütfen sayfayı geliştirin veya bu sorunlar konusunda tartışma sayfasında bir yorum yapın. Bu madde, Vikipedi biçem el kitabına uygun değildir. Maddeyi, Vikipedi standartlarına uygun biçimde düzenleyerek Vikipedi'ye katkıda bulunabilirsiniz. Gerekli düzenleme yapılmadan bu şablon kaldırılmamalıdır. (Ocak 2010) Bu maddenin veya maddenin bir bölümünün gelişebilmesi için matematik konusunda uzman kişilere gereksinim duyulmaktadır. Ayrıntılar için lütfen tartışma sayfasını inceleyin veya yeni bir tartışma başlatın. Konu hakkında uzman birini bulmaya yardımcı olarak ya da maddeye gerekli bilgileri ekleyerek Vikipedi'ye katkıda bulunabilirsiniz. (Ocak 2010) Bu maddede kaynak listesi bulunmasına karşın metin içi kaynakların yetersizliği nedeniyle bazı bilgilerin hangi kaynaktan alındığı belirsizdir. Lütfen kaynakları uygun biçimde metin içine yerleştirerek maddenin geliştirilmesine yardımcı olun. (Haziran 2016) (Bu şablonun nasıl ve ne zaman kaldırılması gerektiğini öğrenin) Bu madde tümüyle ya da çoğunluğuyla tek kaynağa dayanıyor. Konuya dair fikir alışverişi tartışma sayfasında bulunabilir. Lütfen başka kaynaklar ekleyerek bu maddeyi geliştirmeye yardım ediniz. (Haziran 2016)

Savitch Teoremi, uzay karmaşıklığını konu edinen ve bu hususta sonuca varan en eski teoremlerden biridir. Belirlenimsiz makinelerin belirlenimli makinelere dönüştürülmesinde, gerekli olan uzay karmaşıklığını incelemiştir ve beklenenden çok daha küçük uzay gereksinimi olduğunu ortaya koymuştur. Daha formal bir ifadeyle, ${\displaystyle f(n)}$ uzay kullanan bir belirlenimsiz Turing makinesi (nondeterministic turing machine ${\displaystyle NTM}$), belirlenimli bir turing makinesine (deterministic turing machine ${\displaystyle TM}$) dönüştürülürken ${\displaystyle f(n)^{2}}$ uzay gerektirir.^[1]

Teorem[değiştir | kaynağı değiştir]

Herhangi bir ${\displaystyle f:N\to R^{+}}$ fonksiyonu için, ${\displaystyle f(n)\geq n}$ gereksinimi karşılamak koşuluyla,
${\displaystyle NSPACE(f(n))\subseteq SPACE(f(n))}$ dir.

İspat fikri[değiştir | kaynağı değiştir]

${\displaystyle f(n)}$ uzay kullanan bir ${\displaystyle NTM}$ simule ederken, akla ilk gelen yol ${\displaystyle NTM}$'nin tüm kollarını tek tek hesaplayarak, işlemi ilerletmektir. Bu yolu kullanırken, işlenen kola ait bilgilerin tutulması gerekmektedir. ${\displaystyle f(n)}$ uzay kullanan bir kol, en kötü ihtimalle ${\displaystyle 2^{O(f(n))}}$ adımda, hesaplanabilir. Bütün kolların sırayla hesaplanması ise, hepsinin kayıt altında tutulması manasına gelir ki bu ${\displaystyle 2^{O(f(n))}}$ uzay gerektirir. Üssel bir ilişki kuran bu yöntem, Savitch teoreminin iddia ettiği uzaydan çok daha fazla uzay gerektirmiş olur.

Bunun yerine, çözümü yinelemeli bir algoritma olan, yieldability probleminin yöntemi uygulanmıştır. ${\displaystyle c_{1}}$'i başlangıç, ${\displaystyle c_{2}}$'yi kabul konfigurasyonu ve t'yi ${\displaystyle NTM}$'nin kullanabileceği maksimum adım sayısı olarak kabul edersek, yieldability probleminin çözümü, ${\displaystyle NTM}$'nin verilen katarı kabul edip etmediğine karar verebilir.

Yieldability problemi[değiştir | kaynağı değiştir]

Yinelemeli bir algoritma mantığıyla çözülebilecek olan yieldability probleminin çözümünde aşağıdaki algoritma kullanılır.
CANYIELD(${\displaystyle c_{1},c_{2},t}$) #${\displaystyle c_{1}vec_{2}}$ başlangıç ve kabul konfigürasyonları, ${\displaystyle t}$ adım sayısı


İspat[değiştir | kaynağı değiştir]

${\displaystyle N}$ makinesi ${\displaystyle f(n)}$ uzayda ${\displaystyle A}$ diline karar veren bir ${\displaystyle NTM}$ olsun. ${\displaystyle A}$ diline karar veren bir belirlenimli ${\displaystyle TM}$ ${\displaystyle M}$ makinesi oluşturalım. ${\displaystyle M}$ makinesi, ${\displaystyle N}$ makinesinin herhangi bir konfigürasyonunun belirli adımda çözülüp çözülmediğini test etmek için yukarıda bahsedilen CANYIELD algortimasını kullanır.
${\displaystyle w}$ katarı ${\displaystyle N}$ makinesi için bir girdi katarı olsun.${\displaystyle w}$ katarı üzerinde ${\displaystyle c_{1}}$ ve ${\displaystyle c_{2}}$ konfigürasyonları için, ${\displaystyle N}$ makinesi ${\displaystyle c_{1}}$'den ${\displaystyle c_{2}}$'ye ${\displaystyle t}$ veya daha az adımda geliyorsa, CANYIELD algoritması kabul döner, değilse ret döner.
Şimdi de ${\displaystyle N}$ makinesini simüle eden bir ${\displaystyle M}$ makinesi oluşturalım:

${\displaystyle M}$(${\displaystyle w}$)

CANYIELD algoritması kendisini yinelemeli olarak çağırdığında, mevcut durumu; ${\displaystyle c_{1}}$ ve ${\displaystyle c_{2}}$ değerlerini tutmak zorunda kalır. Öyleyse her bir yineleme adımında, ekstra ${\displaystyle O(f(n))}$ uzay gereklidir. Ayrıca, her bir yineleme adımında, ${\displaystyle t}$ adım yarıya düştüğünden, toplamda, ${\displaystyle log_{2}2^{f(n)}=f(n)}$ uzay gereklidir. O zaman bütün simüle için gerekli olan uzay, ${\displaystyle f(n)f(n)=f(n)^{2}}$ olur. Bu da Savitch'in iddia ettiği gibi ${\displaystyle O(f(n)^{2})}$ uzayda, bir ${\displaystyle O(f(n))}$ uzay ${\displaystyle NTM}$ bir ${\displaystyle TM}$'e dönüştürülebilir.

Kaynakça[değiştir | kaynağı değiştir]

Dış bağlantılar[değiştir | kaynağı değiştir]

• Lance Fortnow, Foundations of Complexity, Lesson 18: Savitch's Theorem (18 Mayıs 2009 tarihinde Wayback Machine sitesinde arşivlendi.)