Durma problemi

Açılış sahnesi

Selin, büyük bir kâğıda bir tablo çiziyor. Satırlara katalog programının yazılabilecek bütün sürümlerini, kısa olandan uzun olana doğru sıralıyor: birinci program, ikinci program, üçüncü program. Sütunlara da programlara verilebilecek bütün girdileri aynı sırayla yazıyor. Her karenin içine, o satırdaki programın o sütundaki girdiyle çalıştırıldığında durup durmadığını koyuyor: "durur" ya da "durmaz." Tablo sonsuz, ama Selin onun her karesinin belirli bir cevabı olduğunu biliyor.

Sonra Selin, tablonun köşegenine, yani her programın kendi sırasındaki girdiyle kesiştiği karelere bakıyor ve bir şey fark ediyor. Kerem, bir programın kendi kodunu girdi olarak almasının ne anlama geldiğini soruyor. Tolga, yazılabilecek programların sayısı ile programların hesaplayabileceği işlevlerin sayısını karşılaştırmayı düşünüyor. Lina, bir çeviri programının hiç "hata" yazıp yazmayacağını önceden bilmenin, programın durup durmayacağını bilmekle ilişkili olup olmadığını merak ediyor. Barış, her yazılımın sözleşmeye uygun davranıp davranmadığını mekanik olarak denetleyen bir yasa kuralının uygulanabilir olup olmadığını soruyor. Defne ise bir tıbbi cihazın yazılımının güvenli olduğunu kanıtlamanın, bu sonuçtan sonra hâlâ mümkün olup olmadığını düşünüyor. Bu ders, Mantık ve Akıl Yürütme programının Metalojik ve Hesaplanabilirlik kursunda, bir programın durup durmayacağını her durumda belirleyen bir algoritmanın neden var olamayacağını gösteren köşegen argümanının adımlarını, bu argümanın evrensel makineye ve kendine gönderime nasıl dayandığını ve durma probleminin çözümsüzlüğünden başka soruların çözümsüzlüğünün indirgeme yoluyla nasıl çıkarıldığını soruyor.

Bu derste ne olacak

Önce bu dersin yerini belirleyelim. Metateori modülünün Karar verilebilirlik dersi, durma problemini tanımladı ve onun çözümsüzlüğünü gösteren argümanın ana hatlarını, bir denetçi programın kendi üzerine uygulanmasıyla verdi. Hesaplanabilirlik modülünün Turing makinesi dersi evrensel makineyi, Church–Turing tezi dersi ise Turing makineleri hakkındaki sonuçların algoritmalar hakkında sonuçlar olarak okunmasını mümkün kılan tezi inceledi. Akademinin önceki derslerinde Hilbert'in 1900 tarihli problemler konuşması ve Grelling ile Nelson'ın kendine gönderen sıfatlar paradoksu da ele alınmıştı. Bu ders, modülü kapatıyor: durma probleminin çözümsüzlüğünü, bu kez argümanın yapısı, dayandığı araçlar ve doğurduğu sonuçlar bakımından inceliyor.

Sonra üç kaynağa bakacağız. Georg Cantor, 1891'de yayımladığı Küme Kuramının Temel Bir Sorusu Üzerine makalesinde, bugün köşegen argümanı adıyla bilinen yöntemi verir. Henry Gordon Rice, 1953'te yayımladığı Özyinelemeli Sayılabilir Kümelerin Sınıfları ve Karar Problemleri makalesinde, programların davranışı hakkındaki hemen her sorunun çözümsüz olduğunu gösterir. Yuri Matiyasevich ise 1970'te yayımladığı Sayılabilir Kümelerin Diyofant Denklemleriyle Tanımlanabilirliği makalesinde, Hilbert'in onuncu probleminin, yani tam sayı denklemlerinin çözülebilirliğinin, çözümsüz olduğunu gösteren zincirin son halkasını ekler.

Ardından üç itirazı tartacağız: argümanın yapay bir kendine gönderim hilesine dayandığı, pratikte programların durup durmadığının çoğu zaman bilinebildiği ve gerçek bilgisayarların sonlu belleği yüzünden durma sorusunun onlar için karar verilebilir olduğu itirazları.

Sonda, bir sorunun çözümsüz olduğunu göstermenin dört adımını göstereceğiz: sorunu kesin olarak tanımlamak, onu çözen bir algoritmanın var olduğunu varsaymak, bu algoritmayla durma problemini çözen bir yöntem kurmak ve bu yöntemin var olamayacağından varsayımın yanlış olduğu sonucuna varmak.

Merkez soru

Sorumuz şu: bir programın durup durmayacağını her durumda belirleyen bir algoritma neden var olamaz ve bu sonuçtan başka soruların çözümsüzlüğü nasıl çıkarılır?

Ölçülü iddiam şu: durma probleminin çözümsüzlüğü, Cantor'un köşegen argümanının hesaplanabilirliğe uygulanmasıdır. Bütün programlar bir listede sıralanabilir, çünkü her program sonlu bir işaret dizisidir. Bir programın her girdiyle durup durmadığı, satırları programlar, sütunları girdiler olan sonsuz bir tabloda gösterilebilir. Durmayı her durumda belirleyen bir program varsa, tablonun köşegenini okuyup her kareyi tersine çeviren bir program da yazılabilir. Bu program, kendi kodu girdi olarak verildiğinde, kendi hakkındaki cevabı tersine çevirmek zorunda kalır ve bir çelişki doğar. Bu yüzden böyle bir program yoktur. Argümanın iki dayanağı vardır. Birincisi, evrensel makinenin varlığıdır: bir program, başka bir programın kodunu okuyup onu çalıştırabilir. İkincisi, programların kendi kodlarını girdi olarak alabilmesidir, çünkü kod da bir işaret dizisidir. Durma probleminin çözümsüzlüğü, başka soruların çözümsüzlüğünü göstermenin de aracıdır. Bir sorunu çözen bir algoritmadan durma problemini çözen bir algoritma kurulabiliyorsa, o sorun da çözümsüzdür. Bu yönteme indirgeme denir. Rice, bu yöntemle, bir programın hesapladığı işlev hakkındaki hemen her sorunun çözümsüz olduğunu gösterdi. Matiyasevich ise aynı zincirin sonunda, programlarla ilgisi yokmuş gibi görünen bir sorunun, tam sayı denklemlerinin çözülebilirliğinin de çözümsüz olduğunu kanıtladı. Durma probleminin çözümsüzlüğü, belirli programlar hakkında bir şey bilmeyi olanaksız kılmaz. Olanaksız kıldığı, bütün programlar için işleyen tek bir yöntemdir.

Sıfır noktası

Bir öğrenci durma probleminin çözümsüzlüğünü ilk duyduğunda, bunu bir teknik sınırlama sanar. Belki bugünün programları yetersizdir; belki daha akıllı bir program bir gün bu soruyu cevaplayacaktır. Ama çözümsüzlük, programların yeteneği hakkında değil, sorunun kendisinin yapısı hakkında bir sonuçtur. Hiçbir program, ne kadar akıllı olursa olsun, bu soruyu her durumda cevaplayamaz.

Bu sonucun gücü, onun bir sayma argümanıyla da desteklenebilmesinden gelir. Programlar sonlu işaret dizileridir ve bu diziler bir listede sıralanabilir: önce bir işaretlik diziler, sonra iki işaretlik diziler ve böyle devam eder. Bu yüzden programların sayısı sayılabilirdir. Doğal sayılardan evet ya da hayır cevaplarına giden işlevlerin sayısı ise, Cantor'un gösterdiği gibi, sayılamazdır. Programlardan çok daha fazla işlev vardır. Öyleyse hiçbir programın hesaplamadığı işlevler bulunmalıdır.

Sayma argümanı, hesaplanamayan işlevlerin var olduğunu gösterir, ama hangilerinin hesaplanamadığını söylemez. Durma problemi, böyle bir işlevin somut ve doğal bir örneğini verir. Bir programın bir girdiyle durup durmadığını söyleyen işlev, hiçbir programla hesaplanamaz.

Görüşler ve pozisyonlar

Durma probleminin çözümsüzlüğünün anlamı konusunda üç görüş var.

Birinci görüş, mutlak sınır görüşüdür. Buna göre durma probleminin çözümsüzlüğü, mekanik bilginin aşılamaz bir sınırını gösterir. Programların davranışı hakkındaki bazı sorular, ilke olarak, hiçbir mekanik yöntemle her durumda cevaplanamaz.

İkinci görüş, pratik ilgisizlik görüşüdür. Buna göre sonuç, yalnızca yapay ve kendine gönderen programlar için geçerlidir. Gerçek hayattaki programlar için durma sorusu çoğu zaman cevaplanabilir ve çözümsüzlük pratikte bir fark yaratmaz.

Üçüncü görüş, harita görüşüdür. Buna göre çözümsüzlük, genel bir yöntemin yokluğunu söyler, ama belirli programlar hakkındaki bilgiyi olanaksız kılmaz. Hangi soruların hangi program sınıfları için cevaplanabildiği, ayrıntılı bir incelemenin konusudur.

Bu ders üçüncü görüşü temel alır ve birinci görüşün, genel bir yöntemin ilke olarak var olamayacağı gözlemini kabul eder. Birinci görüş, sonucun bir teknik sınırlama değil, bir ilke sınırı olduğunu doğru görür. İkinci görüş, birçok gerçek program için durma sorusunun cevaplanabildiğini doğru görür. Ama indirgeme yoluyla elde edilen sonuçların, kendine gönderimle hiçbir ilgisi olmayan doğal sorulara da uzandığını hesaba katmaz. Matiyasevich'in sonucu bunun en açık örneğidir. Üçüncü görüş, iki gözlemi birlikte tutar.

Argümanın yapısı

Bir sorunun çözümsüz olduğunu göstermek için dört adım izlenebilir.

Birinci adım, sorunu kesin olarak tanımlamaktır. Gösteren, sorunun hangi girdiler için hangi cevabı istediğini, örneğin bir programın belirli bir çıktıyı hiç verip vermeyeceğini, açıkça yazar.

İkinci adım, onu çözen bir algoritmanın var olduğunu varsaymaktır. Gösteren, sorunu her durumda doğru cevaplayan bir programın bulunduğunu, yalnızca çelişkiye götürmek üzere varsayar.

Üçüncü adım, bu algoritmayla durma problemini çözen bir yöntem kurmaktır. Gösteren, herhangi bir program ile bir girdi verildiğinde, onları incelenen sorunun bir örneğine dönüştüren ve varsayılan algoritmanın cevabından durma sorusunun cevabını çıkaran bir yöntem yazar.

Dördüncü adım, bu yöntemin var olamayacağından varsayımın yanlış olduğu sonucuna varmaktır. Gösteren, durma problemini çözen bir yöntem olamayacağına göre, onu mümkün kılan varsayımın, incelenen sorunu çözen algoritmanın, var olamayacağını yazar.

En güçlü itiraz

Bu yaklaşıma üç yönden ciddi itiraz yapılabilir.

Durma problemini ciddiye alan düşünce şu cevabı verebilir. Durma probleminin çözümsüzlüğü, Cantor'un köşegen argümanının hesaplanabilirliğe uygulanmasıdır. Selin'in köşegeninde görüldüğü gibi, durmayı her durumda belirleyen bir program varsa, köşegeni tersine çeviren bir program da yazılabilir ve bu program kendi satırında bir çelişkiye düşer. Kerem'in kendi kodunda görüldüğü gibi, argümanın iki temeli vardır: kodun bir işaret dizisi olması ve evrensel makinenin bu diziyi çalıştırabilmesi. Tolga'nın iki sayısında görüldüğü gibi, sayma argümanı hesaplanamayan işlevlerin varlığını gösterir, durma problemi ise somut bir örnek verir. Durma probleminin çözümsüzlüğü, indirgeme yoluyla başka soruların çözümsüzlüğünü göstermenin de aracıdır. Lina'nın hata denetçisinde görüldüğü gibi, bir sorunu çözen bir algoritmadan durma problemini çözen bir yöntem kurulabiliyorsa, o sorun da çözümsüzdür. Rice, bu yöntemle, programların davranışı hakkındaki hemen her genel sorunun çözümsüz olduğunu gösterdi. Matiyasevich ise aynı zincirin sonunda, polinom denklemlerinin tam sayı çözümlerinin de çözümsüz bir soru olduğunu kanıtladı. Ama Barış'ın denetim kuralında ve Defne'nin cihaz yazılımında görüldüğü gibi, çözümsüzlük belirli programlar hakkındaki bilgiyi olanaksız kılmaz. Olanaksız kıldığı, bütün programlar için işleyen tek bir yöntemdir.

Açık kalan sorular

Selin'in köşegeni, durma argümanının Cantor'un yöntemine dayandığını gösterdi. Cantor, bu yöntemle sonsuzlukların farklı büyüklüklerde olduğunu, Turing ise bazı soruların çözümsüz olduğunu gösterdi. Aynı yöntemin bu kadar farklı sonuçlar vermesi, onun mantığın temel bir yapısına dokunduğunu mu gösterir? Kendine gönderim, sınır sonuçlarının kaçınılmaz bir kaynağı mıdır?

Barış'ın denetim kuralı ve Defne'nin cihaz yazılımı, çözümsüzlüğün genel bir denetimi değil, yalnızca denetimin kimin işi olduğunu değiştirdiğini gösterdi. Bir yazılımın güvenli olduğunu kanıtlama yükünü üreticiye vermek, bu kanıtın doğru olup olmadığını denetleme sorununu ortadan kaldırır mı? Bir kanıtın doğru olup olmadığını denetlemek, karar verilebilir bir soru mudur?

Matiyasevich'in sonucu, çözümsüzlüğün indirgemeyle doğal matematik sorularına uzandığını gösterdi. Matematikçilerin bugün uğraştığı açık sorulardan bazıları da, bir gün çözümsüz çıkabilir mi? Bir sorunun çözümsüz olduğunu bilmek, onun cevabının olmadığını mı, yoksa yalnızca mekanik bir yolla bulunamayacağını mı gösterir?

Yaygın hatalar

Kendin dene

Aklında kalsın

Beş cümlede dersin iskeleti.

Durma probleminin çözümsüzlüğü, Cantor'un köşegen argümanının hesaplanabilirliğe uygulanmasıdır: durmayı her durumda belirleyen bir program varsa, köşegeni tersine çeviren bir program da yazılabilir ve bu program kendi satırında bir çelişkiye düşer.

Cantor'un 1891 tarihli makalesi köşegen argümanını verdi, Rice'ın 1953 tarihli makalesi programların hesapladığı işlevler hakkındaki önemsiz olmayan her özelliğin karar verilemez olduğunu gösterdi, Matiyasevich'in 1970 tarihli makalesi ise indirgeme zincirinin sonunda Hilbert'in onuncu probleminin çözümsüz olduğunu kanıtladı.

Bir sorunun çözümsüzlüğü dört adımla gösterilir: sorunu kesin olarak tanımlamak, onu çözen bir algoritmanın var olduğunu varsaymak, bu algoritmayla durma problemini çözen bir yöntem kurmak ve bu yöntemin var olamayacağından varsayımın yanlış olduğu sonucuna varmak.

Argümanın yapay bir hileye dayandığı, pratikte durmanın çoğu zaman bilinebildiği ve sonlu bellekli bilgisayarlar için sorunun karar verilebilir olduğu itirazları, çözümsüzlüğün indirgemeyle doğal sorulara yayıldığını, sonucun belirli programları değil genel bir yöntemi olanaksız kıldığını ve sonlu bellek için karar yönteminin ilke olarak var olup pratikte uygulanamadığını gördüğümüzde cevaplanabilir.

Bu yüzden durma problemi, hesaplanabilirliğin sınırını çizen temel sonuçtur ve bu sınır, belirli programlar hakkındaki bilgiyi değil, bütün programlar için işleyen tek bir yöntemi olanaksız kılar.

Sonraki derse köprü

Durma argümanı, bir programın kendi kodunu girdi olarak alabilmesine dayanıyordu. Bu, kod bir işaret dizisi olduğu için mümkündü. Kerem, aynı düşüncenin mantığa da uygulanıp uygulanamayacağını soruyor. Aritmetiğin bir biçimsel sistemi, sayılar hakkında konuşuyordu. Sistemin formülleri ve kanıtları da işaret dizileriydi. Bu diziler sayılarla kodlanabilirse, aritmetik, sayılar hakkında konuşurken, kendi formülleri ve kanıtları hakkında da konuşabilirdi.

Selin, bunun yalancı paradoksuna benzer bir cümleyi, "bu cümle kanıtlanamaz" diyen bir cümleyi, aritmetiğin kendi içinde kurmayı mümkün kılacağını fark ediyor. Tolga, programların uzunluklarına göre sıralanıp numaralandırıldığını, formüllerin de aynı biçimde numaralandırılabileceğini söylüyor. Lina, bir sözlüğün her sözcüğüne bir numara vermenin, sözlüğü bir sayı listesine dönüştürdüğünü hatırlatıyor.

Bir sonraki ders bu soruya dönüyor. Aritmetikleştirme dersi, bir biçimsel sistemin formüllerinin ve kanıtlarının sayılarla nasıl kodlanabildiğini, bu kodlamanın aritmetiğin kendi sözdizimi hakkında konuşmasını nasıl mümkün kıldığını ve kendi kanıtlanamazlığını söyleyen bir cümlenin aritmetiğin içinde nasıl kurulduğunu soruyor.