• hesaplama kuramında, bir programın bir zaman sonra bitip/bitmeyeceğinin belirsizliğini ifade eden problem.

    elimizde bir programın bitip bitmeyeceğini söyleyen bir p programı olsun, bu p programı kendisinin bitip bitmeyeceğini söylememektedir.
  • diger dusunce deneyleri icin
    (bkz: #92649934)
  • temel tanımlarla bu kavramı bir türlü anlayamamıştım neden böyle diye ama sonunda anladım. şöyle düşünebilirsiniz. elinizde bir program var. içinde türlü türlü looplar assignmentlar var. bu döngülerin her hangi bir infinite loop oluşturup oluşturmadığını bu programı çalıştırıp test etmeden bilemezsiniz. yani program da kendisinin bitip bitmeyeceğini bilemez. bu kadar.

    yaklaşık iki yıl sonra gelen edit:

    zamanında yazığım bu informal tanım bu durumun doğruluğuna kendimi ikna etmek için yeterli olsa da tam olarak kanıtlamak için yeterli değil. bu problemi şu an son sınıf bir bilgisayar bilimi öğrencisi olarak hesaplanabilirlik teorisi dersinde yoğun olarak kullanmaktayım. eğer daha iyi anlamak istiyorsanız okulunuzda bu dersi almanızı öneririm. kısaca bu problemin karar verilemez olduğunu şu şekilde ispatlayabiliriz. bunu anlamak için şu konuları anlamaya çalışmanız faydalı olur.

    (bkz: decidability)
    (bkz: diagonalization theorem)
    (bkz: turing machine)

    öncelikle bu problemin semidecidable olduğunu ama decidable olmadığını belirtelim. yani bize verilen bir turing makinesinin (programın) asla durmuyorsa durmayacağına emin olamayız fakat duruyorsa durduktan sonra durduğuna emin olabiliriz. bu duruma theory of computation'da semi-decidability deniyor.

    şimdi bu problemin deciable olmadığını kanıtlayalım.

    x,y hem veri hem de çalıştırılabilir bir program olarak yorumlanabilecek kodlar olsun.

    halts (x, y) bir doğru-yanlış fonksiyonu olsun ve x programı y verisi üzerinde duruyorsa doğru durmuyorsa yanlış değeri dönsün.
    bu fonksiyonu kullanarak köşegen adında yeni bir fonksiyon oluşturalım.

    köşegen (x)
    a : if halts(x,x) go to a; else halt

    bu durumda halts(x,x) doğru olursa köşegen sonsuz döngüye girecek ve durmayacak ama halts(x,x) yanlış olursa köşegen duracak.

    şimdi köşegen (köşegen) 'i inceleyelim

    köşegen (köşegen) ancak ve ancak halts(köşegen, köşegen) false olursa durur ve bu ancak ve ancak köşegen(köşegen) durmuyorsa olur.

    bu durum da mantıksal olarak çelişkilidir ve halts(x,y) fonksiyonu var olamaz. kanıtımız da bu şekilde biter.
  • bu problem hesaplanabilirliğin sınırlarını gösteren bir problemdir. bir turing makinesinin verilen bir girdi üzerinde durup durmayacağını belirlemenin imkansız olduğunu gösterir. turing makineleri teorisindeki en temel problemlerden biridir ve bilgisayar biliminde çok önemli bir yere sahiptir.

    bir programın durup durmayacağı sorusunu sormaktadır. bir bilgisayar programının durup durmayacağını sormak, aslında programın ne kadar sürede çalışacağı sorusunu sormakla aynı şey. işte bu yüzden bu problem bir programın ne kadar sürede çalışacağı sorusunun cevabının bulunamayacağını gösteriyor.

    ayrıca turing'in hesaplanabilirliğin sınırlarını göstermek için öne sürdüğü bir problemdir. turing, "entscheidungsproblem (karar problemi)" adlı bir soru ortaya atmıştır: bir cümle matematiksel olarak doğru mudur yoksa yanlış mıdır?sorunun cevabı, matematiksel mantık kuralları ile belirlenebilir. ama turing, bir matematiksel cümleyi doğru veya yanlış olarak belirlemenin ne kadar sürede yapılacağı sorusunun cevabının bulunamayacağını göstermiştir. bu yüzden halting problemi, matematiksel problemlerin hesaplanabilirliğinin sınırlarını göstermek için kullanılan bir araç haline gelmiştir.

    turing makinesinin verilen bir girdi üzerinde durup durmayacağını da belirlemenin imkansız olduğunu gösterir. bu yüzden halting problemi çözülemeyen bir problemdir. bir programın ne kadar sürede çalışacağı sorusu da halting problemi ile aynı sonucu verir. bir programın ne kadar sürede çalışacağı sorusu da cevapsız bir sorudur.

    hesaplanabilirliğin sınırlarını gösterir. özellikle, programlama dillerinin ve derleyicilerin tasarımı sırasında, halting problemi çözümüne benzer teknikler kullanılır. programların çalışma sürelerini tahmin etmek ve sınırlamak için kullanılan yöntemler, halting problemine dayanır.
hesabın var mı? giriş yap