İçeriğe atla

Savitch teoremi

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, uzay kullanan bir belirlenimsiz Turing makinesi (nondeterministic turing machine ), belirlenimli bir turing makinesine (deterministic turing machine ) dönüştürülürken uzay gerektirir.[1]

Teorem

Herhangi bir fonksiyonu için, gereksinimi karşılamak koşuluyla,
dir.

İspat fikri

uzay kullanan bir simule ederken, akla ilk gelen yol 'nin tüm kollarını tek tek hesaplayarak, işlemi ilerletmektir. Bu yolu kullanırken, işlenen kola ait bilgilerin tutulması gerekmektedir. uzay kullanan bir kol, en kötü ihtimalle adımda, hesaplanabilir. Bütün kolların sırayla hesaplanması ise, hepsinin kayıt altında tutulması manasına gelir ki bu 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. 'i başlangıç, 'yi kabul konfigurasyonu ve t'yi 'nin kullanabileceği maksimum adım sayısı olarak kabul edersek, yieldability probleminin çözümü, 'nin verilen katarı kabul edip etmediğine karar verebilir.

Yieldability problemi

Yinelemeli bir algoritma mantığıyla çözülebilecek olan yieldability probleminin çözümünde aşağıdaki algoritma kullanılır.
CANYIELD() # başlangıç ve kabul konfigürasyonları, adım sayısı

  • 1. Eğer ise olup olmadığına veya 'den 'ye tek bir adımda geçip geçmediğine bakılır. Eğer ikisinden biri doğru ise kabul, ikisi de yanlış ise ret döner
  • 2. Eğer ise bütün uzay kullanan ara konfigürasyonlar() için:
  • 3. CANYIELD() çağır
  • 4. CANYIELD() çağır
  • 5. Eğer 3. ve 4. adım kabulse, kabul eder
  • 6. Eğer kabul değilse ret döner

İspat

makinesi uzayda diline karar veren bir olsun. diline karar veren bir belirlenimli makinesi oluşturalım. makinesi, 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.
katarı makinesi için bir girdi katarı olsun. katarı üzerinde ve konfigürasyonları için, makinesi 'den 'ye veya daha az adımda geliyorsa, CANYIELD algoritması kabul döner, değilse ret döner.
Şimdi de makinesini simüle eden bir makinesi oluşturalım:

()

  • 1. CANYIELD(, , ) sonucu çıktı olarak döner.


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

Kaynakça

  1. ^ Sipser 2006 Introduction to the Theory of Computation, Second

Dış bağlantılar

İlgili Araştırma Makaleleri

Klasik mekanikte momentum ya da devinirlik, bir nesnenin kütlesi ve hızının çarpımıdır; (p = mv). Hız gibi, momentum da vektörel bir niceliktir, yani büyüklüğünün yanı sıra bir yöne de sahiptir. Momentum korunumlu bir niceliktir ; yani bu, eğer kapalı bir sistem herhangi bir dış kuvvetin etkisi altında değilse, o kapalı sistemin toplam momentumunun değişemeyeceği anlamına gelir. Momentum benzer bir konu olan açısal momentum ile karışmasın diye, bazen çizgisel momentum olarak da anılır.

<span class="mw-page-title-main">Kinetik enerji</span> bir cismin harekiyle oluşan enerji

Kinetik enerji, fiziksel bir cismin hareketinden dolayı sahip olduğu enerjidir.

<span class="mw-page-title-main">Beygir gücü</span> İmparatorluk birim sistemindeki güç birimi (745.69987 W)

Beygir gücü, genellikle otomobil ve elektrik motorlarının güçlerinin belirlenmesi için kullanılan güç birimi. Birimin kısaltması hp'tir. Terim, buhar makinelerinin üretilmeye başlandığı yıllarda, bu makinelerin güçlerinin olası alıcılar tarafından kolayca anlaşılabilmesi için James Watt tarafından kullanılmıştır.

<span class="mw-page-title-main">PageRank</span>

PageRank, Google tarafından geliştirilen ve web sayfalarının önemini belirlemek için kullanılan bir algoritmadır. İnternet üzerindeki bağlantıların analiz edilmesiyle hesaplanan Pagerank değeri Google Arama sonuçlarında sayfaların sıralanması için kullanılan faktörlerden biridir.

Doğrusal dönüşüm, bir fonksiyon çeşididir. T, M boyutlu bir vektörden N boyuta bir doğrusal dönüşüm ise, o zaman;

Hipotez testi, bir hipotezin doğruluğunun istatistiksel bir güvenilirlik aralığında saptanması için kullanılan yöntem.

Kolmogorov karmaşıklığı, bilgisayar biliminde, bir metin parçası gibi bir nesneyi tanımlamak için kullanılması gereken bilgi işlemsel kaynakların ölçüsü.

<span class="mw-page-title-main">İş (fizik)</span>

Fizikte, bir kuvvet bir cisim üzerine etki ettiğinde ve kuvvetin uygulama yönünde konum değişikliği olduğunda iş yaptığı söylenir. Örneğin, bir valizi yerden kaldırdığınızda, valiz üzerine yapılan iş kaldırıldığı yükseklik süresince ağırlığını kaldırmak için aldığı kuvvettir.

<span class="mw-page-title-main">Tork</span> bir kuvvetin nesnenin ekseninde, dayanak noktasında ya da çevresinde dönme eğilimi

Tork, kuvvet momenti ya da dönme momenti, bir cismin bir eksen etrafındaki dönme, bükülme veya burulma eğilimini dönme ekseni merkezine indirgeyerek ölçen fiziksel büyüklüktür. Torkun büyüklüğü moment kolu uzunluğuna, uygulanan kuvvete ve moment kolu ile kuvvet vektörü arasındaki açıya bağlıdır.

<span class="mw-page-title-main">Doğrusal denklem</span>

Doğrusal ya da lineer denklem terimlerinin her biri ya birinci dereceden değişken ya da bir sabit olan denklemlerdir. Böyle denklemlere "doğrusal" denmesinin nedeni içerdikleri terim ve değişkenlerin sayısına bağlı olarak (n) düzlemde ya da uzayda bir doğru belirtmesindendir. Doğrusal denklemlerin en yaygını bir ve değişkeni içeren aşağıdaki formdur:

Termodinamiğin(Isıldevinimin) ikinci yasası, izole sistemlerin entropisinin asla azalamayacağını belirtir. Bunun sebebini izole sistemlerin termodinamik dengeden spontane olarak oluşmasıyla açıklar. Buna benzer olarak sürekli çalışan makinelerin ikinci kanunu imkânsızdır.

Olasılık kuramı ve istatistik bilim dallarında, bir rassal değişken X için, eğer beklenen değer var ise, moment üreten fonksiyon şöyle tanımlanır:

SAT problemi bir NP-tam sınıfı problemidir.

Boolean Formülü içerisinde; boolean değişkenleri, sabitler {0,1} ve işlemler {, , } içeren formüllerdir. Bu formüller, (bütün hepsi) ve belirleyicilerinin eklenmesiyle daha genel bir yapıya sokulabilir. ifadesi bütün x değişkenleri için Q formülü doğrudur anlamı taşımaktadır. Benzer bir şekilde; ifadesi ise bazı x değişkenleri için Q formülü doğrudur anlamı taşımaktadır.

Post Karşılık Problemi (PCP), 1946 yılında Emil Leon Post tarafından ortaya atılan Automatanın kararlaştırılamazlık problemlerinden birisidir. Güncel matematik ve teorik bilgisayar bilimleri ile bir PCP örneğinin çözümü olup olmadığına karar verecek bir algoritma geliştirilemez. Diğer kararlaştırılamazlık problemlerine göre gösterimi daha kolay olduğu için kararlaştırılamazlık problemlerinin ispatında sıklıkla kullanılır.

Tek anakütle ortalaması için parametrik hipotez sınaması veya tek-örneklem için sınama veya μ için sınama, bir rastgele örneklem ortalaması ile bu örneklemin çekilmiş olduğunu düşündüğümüz anakütlenin μ ile belirtilen "anakütle ortalaması" hakkında bir hipotez değeri belirtilmesinin anlamlı olup olmadığını araştırmamızı sağlayan parametrik hipotez sınamasıdır.

<span class="mw-page-title-main">Vektör alanı</span> oklid uzayının seçilen bir alt kümesinin her bir noktasında yöneyin belirlenmesidir.

Yöney alan, Öklid uzayının seçilen bir alt kümesinin her bir noktasında yöneyin belirlenmesidir. Düzlemdeki bir yöney alanı, her biri düzlemdeki bir noktaya ilişik, yönü ve büyüklüğü olan oklar topluluğu olarak düşünülebilir.

Modern kuantum (nicem) mekaniğinden önce gelen eski kuantum (nicem) kuramı, 1900 ile 1925 yılları arasında elde edilen sonuçların birikimidir. Bu kuramın, klasik mekaniğin ilk doğrulamaları olduğunu günümüzde anladığımız bu kuram, ilk zamanlar tamamlanmış veya istikrarlı değildi. Bohr modeli çalışmaların odak noktasıydı. Eski kuantum döneminde, Arnold Sommerfield, uzay nicemlenimi olarak anılan açısal momentumun (devinimin) z-bileşkesinde nicemlenim yaparak önemli katkılarda bulunmuştur. Bu katkı, electron yörüngelerinin dairesel yerine eliptik olduğunu ortaya çıkarmıştır ve kuantum çakışıklık kavramını ortaya atmıştır. Bu kuram, electron dönüsü hariç Zeeman etkisini açıklamaktadır.

<span class="mw-page-title-main">Petri ağı</span>

Bir petri ağı sistemlerin incelenmesi için kullanılabilecek bir araçtır. Petri ağları, sistemin matematiksel bir modelle modellenebilmesine izin verir. Bir Petri ağı, geçiş ve yerleşim düğümlerinden oluşan tek yönlü iki parçalı graf olarak da tanımlanabilir. Ok şeklinde gösterilen yönlü eğriler, bir geçişten önce ve sonra hangi yerlerin olduğunu tanımlarlar.

<span class="mw-page-title-main">Hesaplanabilir sayı</span>

Matematikte, hesaplanabilir sayılar, belirlenen herhangi bir doğruluk seviyesine ulaşacak şekilde sonlu ve sona eren bir algoritma ile hesaplanabilen reel sayıları ifade eder. Bu sayılar, yinelemeli sayılar, etkili sayılar ya da hesaplanabilir reel sayılarolarak da adlandırılır. Hesaplanabilir reel sayılar kavramı, o dönemde mevcut olan sezgisel hesaplanabilirlik kavramı üzerinden Emile Borel tarafından 1912'de ortaya konmuştur.