Herhangi bir konuda bir şeyin doğruluğuna veya bir şeyi yapmaya ‘objektif olarak’ karar vermek, sanıldığından daha zor bir süreçtir. Özellikle de hata yapmanın iyi olmayan sonuçlar doğurduğu durumlarda. Bu durum bilgisayarlar için her zaman geçerlidir. Bir bilgisayarın hesaplamada hata yapması asla beklenmez, dolayısıyla bilgisayar ve bu bilgisayarı tasarlayanların bilgisayarın karar verme mekanizmasında, ‘diğer insanların aksine’ hata yapma lüksü yoktur ve bu sürecin tamamen doğru şekilde çalışması gerekir. Bu yüzden bilgisayarların ‘karar verme’ algoritmaları detaylı her olasılığı kapsayacak şekilde incelenmelidir. Bu da şu anda bilgisayar biliminin bir alt alanı olan hesaplanabilirlik kuramının incelediği bir durumdur. Peki bir bilgisayarın verilen girdiden bağımsız olarak her şeyi doğru olarak hesaplayabilmesi ya da soruyu daha da basitleştirirsek karar verebilmesi mümkün müdür? Bundan önce “bilgisayar” kelimesinden ne anlamak gerektiğini açıklamak gerekiyor.
Şekil 1: Turing makinesinin örnek bir şeması (Kaynak, 4)
Her ne kadar yakın zamandaki gelişmelerle de beraber bilgisayarlar fazlasıyla karmaşık bir yapıda ve onların ne olduğunu açıklamak zor gibi görünse de gerçekte bilgisayarlar çok basit şekilde bir Turing makinesi olarak açıklanabilir. Bilgisayar biliminin babası sayılan Alan Turing’in bu hayali makinesi basitçe, birbirinden ayrık hücreler içeren bir hareketli bant ile bu banttaki verilerin taranmasını ve belirli bir işlem kümesine göre değiştirilmesini sağlayan bir işlem biriminden oluşur1.
Bunu gerçek bir bilgisayarla karşılaştırırsak, bahsedilen işlem birimi bilgisayarın işlemcisine, spesifik olarak CPU’ya, bahsedilen hareketli bant da bilgisayarın hafızasına, daha spesifik olarak RAM’e denk gelir. Her ne
kadar modern bilgisayarlar buna ek olarak farklı yapılar kullansa da ana olarak bu modelin gerçekleştirdiği işlemleri yaparlar. Bununla beraber bir Turing makinesini bir bilgisayar programı olarak da yorumlamak mümkündür. Bu modeli kullanarak bir bilgisayara verilecek tüm girdilerle beraber, yani bantta Turing makinesinin ilk oluşturulduğu durumda hücrelerinde yazılı olan veriler, yazılabilecek tüm programları da formel olarak ifade etmek mümkündür. Bununla beraber bu model kullanılarak bir Turing makinesinin herhangi bir girdiye göre karar verip veremeyeceği ispatlanabilir.
Şimdi de konunun daha iyi anlaşılabilmesi için daha önce bilgisayarlar için bahsedilmiş olan karar verme kavramından bahsedelim. Bilgisayarların karar vermesini, aslında insanların da karar alma yollarından biri olarak, verilen girdiye göre belirli bir algoritma vasıtasıyla evet ya da hayır çıktısını vermesi olarak tanımlayabiliriz. Buradaki önemli soru, daha önce değinilmiş olan “Verilebilecek tüm girdiler için, bir girdiye göre herhangi bir algoritma sonucunda evet ya da hayır olarak karar vermek mümkün müdür?” sorusudur ve bu soru karar problemi anlamına gelen Entscheidungsproblem olarak da bilinir2.
Girdiler, herhangi bir şekilde ve konuda olabilir. Eğer bir girdinin karşılığında aşamaları sonlu ve belirli olan bir algoritma ile evet ya da hayır cevabı alınabilen en az bir algoritma varsa bu girdi karar verilebilir bir girdidir. Burada algoritmanın ne kadar kompleks olduğu, diğer bir deyişle sonuç verebilmesi için ne kadar uzun süre çalıştığı eğer bir şekilde çalışma sonlanıyorsa karar verilebilir olması için önemli değildir. Bu tip girdilere örnek olarak “3 sayısı 181 sayısını böler mi?” ifadesini verebiliriz. Bu ifadenin cevabını bölme algoritmasını kullanarak bulabiliriz. Bununla beraber bir girdi için böyle bir algoritma yoksa bu girdi karar verilemeyen bir girdidir. Peki böyle bir girdi oluşturmak, bir nevi hiçbir cevabı olmayan bir soru sormak mümkün müdür?
Böyle bir sorunun olup olamayacağına basit bir soruyla başlayıp sorun için geliştirilecek tüm algoritmalar için hiçbir zaman çıktı verilemeyen bir durum bulabilirsek ulaşabiliriz. O halde girdisi bir program, ya da bir Turing makinesi, olan bir program düşünelim ve programın çıktısı, girdi olarak verilen programın sınırlı bir zaman sonra durup durmayacağı olsun. Daha kolay anlaşılması için bunun adına program 1 diyelim.
Yani örneğin bahsedilen program, girdi programı sonsuz döngüye giriyorsa, diğer bir deyişle hiçbir zaman sonlanamayacaksa 0 çıktısını, eğer girdinin aldığı zamandan bağımsız olarak sonlanabiliyorsa 1 çıktısını versin. Bununla birlikte bir iki girdi alan program daha düşünelim. Bu program da bir programı ilk girdi olarak alsın, bununla birlikte program 1’in az önce bahsedilen ilk girdiden verdiği çıktısını ikinci girdi olarak alsın ve çıktı olarak eğer ikinci girdi 1, yani eğer program 1’e göre bu program sonlanıyorsa, sonsuz döngüye girsin. İkinci girdi 0, yani eğer program 1’e göre ilk girdi sonlanmıyorsa, program tamamen dursun. Buna da program 2 diyelim. Program 2’ye herhangi bir programı girdi olarak verebiliriz, fakat en başta sorduğumuz soruya cevap olması için program 1’in çelişki oluşturduğu bir durumu incelememiz gerekiyor.
Bunu görmek için program 2’nin girdisi olarak kendisini verelim ve ortaya çıkan sonucu inceleyelim. Eğer program 1 bu programın durduğu çıktısını, yani 1 sonucunu, verirse program 2 sonsuz döngüye girecek ve hiçbir zaman durmayacak. Bu durum anlaşılacağı üzere doğrudan program 1’in çıktısıyla çelişiyor. O halde program 1, program 2’nin sonsuz döngüye girdiği çıktısını, yani 0 vermeli. Bu durumda ise program 2 ikinci girdisinin 0 olması sebebiyle durması gerekecek ve bu sonuç yine program 1’in verdiği çıktıyla çelişmekte. Anlaşılacağı üzere burada program 1, hiçbir zaman program 2 için doğru sonucu bulamayacak. Burada program 1 ile aynı işi yapacak bir programın varlığı çelişkiye yol açıyor, dolayısıyla bahsedilen programın var olamayacağını söylemek mümkün.
Bununla birlikte az önceki örnekte varsayımsal bir programın yalnızca çıktısının oluşturduğu sonuçları incelediğimizden dolayı hiçbir zaman böyle bir çıktı veren programın yazılamayacağını, dolayısıyla bu problemin karar verilemeyen bir problem olduğunu söyleyebiliriz. Bu problem sonlanma problemi olarak bilinir ve problemin karar verilemeyen bir problem olduğunun ispatı Alan Turing tarafından yapılmıştır3. Bununla birlikte karar verilemeyen problemler az önceki örnekle sınırlı değil. Matematik gibi çoğu alanda da buna benzer tamamen karar verilemeyen problemler mevcut.
Bu yazıda bilgisayar biliminin alt alanlarından hesaplanabilirlik kuramının uğraştığı sorulardan biri olan ‘karar problemi’ni inceledik. Bir programın sonlanıp sonlanmayacağı gibi evet ya da hayır cevabının hiçbir zaman verilemeyeceği soruların var olduğunu gördük. Umarım ilk bakışta mümkün olmadığı düşünülen ve bu yazıda vurgulamaya çalıştığım her sorunun cevabının verilemeyeceği fikri, günümüzde yine ilk bakışta mümkün ve mantıklı, ya da tam tersi şekilde görülebilen fakat bilinçli veya bilinçsiz yanıltmalarla, mantıksal hatalarla dolu, bilgi kirliliğine yol açan içeriklerin yorumlanmasında doğrudan sonuca atlamak yerine onu detaylı şekilde analiz etmenin önemli olduğunu göstermek adına iyi bir örnek olmuştur.
Kaynakça
1-De Mol, Liesbeth. ”Turing Machines”, The Stanford Encyclopedia of Philosophy (Winter 2019 Edition). Edward N. Zalta (ed.),https://plato.stanford.edu/archives/win2019/entries/turing-machine
2-Weisstein, Eric W. ”Decision Problem.” From MathWorld–A Wolfram WebResource.https://mathworld.wolfram.com/DecisionProblem.html
3-A. M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, vol. s2-42, no. 1, pp. 230–265, 1937, doi: 10.1112/plms/s2-42.1.230.
4-“Turing machines.” [Online]. Erişilebilir: http://2009.igem.org/Turing_machines.
Kapak Görseli: https://medium.com/@INGENIATalent/why-when-partner-with-recruiters-513e143d6a43
