İmkânsızlık hiyerarşisi

Cem Say
İmkânsızlık hiyerarşisi

Herkese Bilim Teknoloji dergisinin 8. sayısında yayımlanan “Problemler Bilimi” başlıklı yazımda Hesaplama Kuramı’na bir giriş yapmıştım. Okurlardan gelen yüzlerce telefon ve mesaj üzerine (tamam, bu kısmı biraz abartmış olabilirim) konuya bu yazıda da devam ediyorum:

Hesaplama kuramcıları, bilgi işlem problemlerini birbirleriyle karşılaştırarak aralarındaki doğal zorluk sıralamasını keşfetmeyi amaçlarlar. Genellikle de başaramazlar! Mesela önceki yazıda iki tam sayının çarpımını bulmanın, toplamlarını bulmaktan daha zor olup olmadığını (Andrey Kolmogorov’un bu soruyu ilk sormasından bu yana 60 yıl geçmiş olmasına karşın) hâlâ bilmediğimizi anlatmıştım. Her ne kadar bildiğimiz en iyi çarpma yöntemi aynı boydaki sayılar üzerinde toplama yöntemimizden daha yavaş çalışıyorsa da, ondan daha üstün bir çarpma algoritmasını ne bulabiliyoruz, ne de var olmadığını kanıtlayabiliyoruz. Çoğu problemin doğal zorluğunu anlamak konusunda henüz bu aşamadayız maalesef.

Ama ben bugün zorluğunu anlayabildiğimiz problemlerden söz etmek istiyorum.


Durma Problemi ve daha beterleri

Yirminci yüzyılın bilim devi Alan Turing, kimi bilgi işlem problemlerinin çözümsüz olduğunu, yani o konuda hangi soru verilirse verilsin kesinkes doğru yanıtı bulmamıza elverecek bir yöntemin var olmadığını kanıtladı. Derslerde buna verdiğimiz ilk örnek şudur:

Bize bir bilgisayar programı gösterilsin. (Programın detaylarını inceleme, bilgisayara yükleyip çalıştırma, vs. her türlü hakkımız var.) İşi basit tutmak için bunun dışarıdan hiç komut almayan, sadece “başlat” düğmesine bastığınızda başlayıp kendi kendine çalışan bir program olduğunu varsayalım. Bizden istenen, “Bu program çalıştırıldığında önünde sonunda durur mu, yoksa asla durmaz ve sonsuza dek çalışır mı?” sorusunu yanıtlamamız. Bir zaman kısıtımız yok, ama sonlu bir sürede doğru cevabı vermemiz bekleniyor.

Buna “Durma Problemi” diyoruz. Turing’in deha ürünü kanıtı gösteriyor ki bu işi verilecek her program için yapabilen bir yöntem yok. Milyarlar harcasanız da bu hesabı yapan bir makine inşa edemezsiniz! Yani bu çözümsüz bir problem.

Ve bu olanaksız iş sonsuz bir olanaksızlık hiyerarşisinin en alt basamağında oturuyor sadece! Bunu göstermek için bir anlığına Durma Problemi’ni çözebilen ihtiyar bir kâhinin var olduğunu hayal ediyoruz. (Matematikçilerin böyle şeyler yapmasına bayılıyorum!) Varsayalım ki bu kâhin kendisine e-posta gönderenlerin bu konudaki sorularına anında doğru cevabı veriyor. Eh, bu durumda Durma Problemi’ni çözememe sorunumuz ortadan kalkmış oluyor!

Şimdi gelin yeni bir problem tanımlayalım, adı da “Süper Durma Problemi” olsun:

Bize yine bir bilgisayar programı gösterilecek. Yine istediğimiz incelemeyi yapma hakkımız var. Yalnız bu programın önceki örneğimizdekilerden farklı olarak arada kâhine e-posta gönderip yanıtı okumak, sonraki davranışını buna göre belirlemek hakkı da var. (Bilgisayarların bunu yapması kolay; bu hikâyedeki tek gerçek ötesi unsur kâhinin Durma Problemi’ni çözebilme becerisi.) Bizden istenen de yine aynı “Bu program durur mu, durmaz mı?” sorusunu sonlu sürede yanıtlamamız, üstelik unutmayın, bu kez bizim de kâhine soru sorma hakkımız var!

Turing’in orijinal kanıtında kullandığı teknik bu Süper Durma Problemi’nin de çözümsüz olduğunu göstermeye yetiyor. Yani Durma Problemi'ni çözecek gücümüz olsa bile çözemeyeceğimiz daha zor bir problem bu.

Peki neden burada duralım ki? Süper Durma Problemi’ni de çözebilen daha da cevval bir kâhin hayal edip bu kez de “Süperden de Süper Durma Problemi”ni tanımlıyoruz. Ve aynı şekilde bu ötekilerden de zor çıkıyor. Bu böyle sonsuza dek gidiyor!

Çözümsüzlük denizinde biz

Aslında, biraz da bu işler yüzünden hayatı bir akıl hastanesinde sonlanan büyük matematikçi Georg Cantor’un sonsuz kümelerin “nüfus”larına dair bulgularına göre problemlerin sayısı çözümlerin sayısından çok daha fazla. Yani sonsuz büyüklükteki problemler kümesinin neredeyse bütün elemanları çözümsüz. Bizler geriye kalan görece az sayıda çözülebilir problemle uğraşıyoruz. Evrim beyinlerimizi bu gezegende muhtemelen sonraki nesli üretebilecek kadar bir süre hayatta kalmaya yetecek kalitede algoritmalarla donatmış.

Ama herhalde atalarımız birbirleriyle tam da bu “sonraki nesli kim üretsin” konusunda rekabet ederken evrilen kıvrak zekamız sayesinde hiç de sağ kalım avantajı olmayan kimi hususlarda düşünüp kafamıza sonsuzlukları sığdırabiliyoruz.

İnsan olmak güzel şey.

Cem Say

Cem Say

1987'den beri Boğaziçi Üniversitesi Bilgisayar Mühendisliği Bölümü'nde çalışıyor. Çalışmaları Yapay Zeka ve Kuramsal Bilgisayar Bilimi üzerine. Sahte dijital deliller üzerine incelemeleri var. Bilimkurgu, uzay yolculuğu, seçim hileleri ve başka bir çok konuya da meraklı.