Karar Verilemezlik

Önceki ders iki durumlu makine ailesini üç kümeye ayırdı: 9784 makine durdu, 5040 makinenin hiç durmayacağı kanıtlandı, 5912 makine için hiçbir şey söylenmedi. Üçüncü kümenin varlığı bir eksiklik gibi görünebilir; bu ders onun bir eksiklik olmadığını gösterir.

Bunun için makine ailesi bırakılıp tek bir kurala bakılır. Kural bir satırdır ve bir çocuğun anlayacağı kadar basittir: sayı tekse üçle çarpılıp bir eklenir, çiftse ikiye bölünür; sayı 1 olunca durulur. Kuralda ne dallanma derinliği ne de saklanan bir durum var. Kuralın kısalığı ile davranışının öngörülemezliği arasındaki uçurum bu dersin bütün konusudur.

Tek Satırlık Kural, Öngörülemez Davranış

Ölçü önceki derslerdekiyle aynı biçimde kurulur. Bütçe adım sayısıdır, evren başlangıç sayılarının kümesidir ve her bütçe değerinde kaç başlangıcın durduğu birikimli sayılır.

• HM27 — Kural tek satırdır ve hiçbir seçenek taşımaz: verilen sayı için sonraki sayı tektir. Belirlenimci bir kuraldır, hiçbir rastgelelik içermez.
• HM28 — Evren, 1’den üst sınıra kadar olan tam sayılardır. İlk ölçümde üst sınır 1000.
• HM29 — Bütçe adım sayısıdır. Bütçe dolduğunda koşum kesilir ve o başlangıç için sonuç bilinmiyor sayılır; “durmaz” yazılmaz.
• HM30 — Harcanan adım da ayrıca toplanır, çünkü bir bütçenin bedeli sonucun yanında durmadıkça okunamaz.
• HM31 — Ara değerlerin en yükseği kaydedilir. Kuralın çıktısı düşerek gitmiyor; önce büyüyor.

"""Tek satirlik sayac kurali: adim butcesi supuruluyor."""


def sayac_kosumu(n, butce):
    """n tek ise 3n+1 , cift ise n/2. n=1 olunca durur."""
    adim, en_yuksek = 0, n
    while n != 1 and adim < butce:
        n = 3 * n + 1 if n % 2 else n // 2
        en_yuksek = max(en_yuksek, n)
        adim += 1
    return {"durdu": n == 1, "adim": adim, "en_yuksek": en_yuksek}


def butce_taramasi(butceler, ust=1000):
    bilinen = set()
    print(f"tek satirlik sayac kurali , {ust} baslangic")
    print("butce  durdugu bilinen  bilinmeyen  harcanan adim")
    for b in butceler:
        harcanan = 0
        for n in range(1, ust + 1):
            k = sayac_kosumu(n, b)
            harcanan += k["adim"]
            if k["durdu"]:
                bilinen.add(n)
        print(f"{b:5d}  {len(bilinen):15d}  {ust - len(bilinen):10d}  {harcanan:13d}")


butce_taramasi((5, 20, 50, 100, 200))
en_uzun = max(range(1, 1001), key=lambda n: sayac_kosumu(n, 1000)["adim"])
k = sayac_kosumu(en_uzun, 1000)
print(f"en uzun kosum: n = {en_uzun} -> {k['adim']} adim ,"
      f" ara degerin en yuksegi {k['en_yuksek']}")

tek satirlik sayac kurali , 1000 baslangic
butce  durdugu bilinen  bilinmeyen  harcanan adim
    5                7         993           4985
   20              155         845          19159
   50              569         431          37815
  100              756         244          54426
  200             1000           0          59542
en uzun kosum: n = 871 -> 178 adim , ara degerin en yuksegi 190996

Üç sayı yan yana. Bütçe: 5, 20, 50, 100, 200 adım. Bütçenin yanıtladığı: karara bağlanan başlangıç sayısı 7, 155, 569, 756 ve 1000. Bütçenin yanıtlayamadığı: 993, 845, 431, 244 ve sonunda 0 başlangıç.

Önceki dersin makine ailesinde bütçeyi büyütmek 6. adımdan sonra hiçbir şey değiştirmiyordu. Burada tersi oluyor: bütçe 40 katına çıkarken karara bağlanan başlangıç sayısı 7’den 1000’e, yani 142 katına çıkıyor. Bütçeyi büyütmek bazen hiçbir şeyi değiştirmez, bazen her şeyi değiştirir ve hangisi olduğu ancak ölçülerek görülür. Bedeli de ölçülmüştür: 4985 adımdan 59.542 adıma, on iki katına.

Son satır kuralın neden öngörülemez olduğunu gösteriyor. En uzun koşum n=871 için 178 adım sürüyor ve bu koşumda ara değer 190.996‘ya çıkıyor. Yani 871’den başlayan bir dizi, 1’e inmeden önce başlangıcının 219 katına yükseliyor. Kuralın kendisi bir satır; davranışı ise başlangıca göre bu kadar sıçrıyor.

Ve tam burada dersin en önemli cümlesi yazılmalıdır. 1000 başlangıcın 1000’inin durması, hepsinin duracağının kanıtı değildir. Tablo yalnız şunu söyler: denenen bin başlangıcın her biri, en çok 200 adımda 1’e indi. Denenmeyenler hakkında hiçbir şey söylemez ve bir sonraki bölüm bunun boş bir kaygı olmadığını sayıyla gösterir.

Aynı Bütçe, Başka Evren

Bir bütçenin “yeterli” olması onun bir özelliği değildir. İlk derste bu, üç durumlu otomatların uzunluk sınırı 1 olan evrende her dili tanıyıp uzunluk 4’te milyonda yarımı tanımasıyla ölçülmüştü. Aynı ölçü burada yinelenir: bütçe sabit tutulur, evren büyütülür.

• HM32 — Evren süpürmesi üst sınırı 1000, 2000 ve 5000 yapar. Bütçe 200’de sabittir.
• HM33 — Bütçeli karar verici, bütçe dolduğunda “durmaz” diyen yordamdır. Bu yordam yanılabilir ve yanıldığı başlangıç aranarak bulunur.
• HM34 — Bir başlangıcın durduğu kanıtla da gösterilebilir: sayı ikinin bir kuvvetiyse her adımda ikiye bölünür ve üs kadar adımda 1’e iner. Bu bir koşum sonucu değil, kuralın okunmasıdır.

"""Ayni butce baska evrende: yeterlilik butcenin ozelligi degil."""


def sayac_kosumu(n, butce):
    adim = 0
    while n != 1 and adim < butce:
        n = 3 * n + 1 if n % 2 else n // 2
        adim += 1
    return n == 1


print("butce 200 , evren supurmesi")
print("  ust  durdugu bilinen  bilinmeyen")
for ust in (1000, 2000, 5000):
    b = sum(1 for n in range(1, ust + 1) if sayac_kosumu(n, 200))
    print(f"{ust:5d}  {b:15d}  {ust - b:10d}")
print()
print("her butceyi yaniltan en kucuk baslangic")
for butce in (5, 20, 50, 100, 200, 300):
    n = 1
    while sayac_kosumu(n, butce):
        n += 1
    print(f"  butce {butce:4d} -> n = {n}")
print()
kuvvetler = [n for n in range(1, 1001) if n & (n - 1) == 0]
print("kanitla karara baglanan: ikinin kuvvetleri")
print("  1000'e kadar", len(kuvvetler), "baslangic ,",
      "sinama tek karsilastirma , en uzun kosumu",
      max(len(bin(n)) - 3 for n in kuvvetler), "adim")
print("  hepsi gercekten duruyor mu:",
      all(sayac_kosumu(n, 1000) for n in kuvvetler))

butce 200 , evren supurmesi
  ust  durdugu bilinen  bilinmeyen
 1000             1000           0
 2000             2000           0
 5000             4991           9

her butceyi yaniltan en kucuk baslangic
  butce    5 -> n = 3
  butce   20 -> n = 25
  butce   50 -> n = 27
  butce  100 -> n = 27
  butce  200 -> n = 2463
  butce  300 -> n = 26623

kanitla karara baglanan: ikinin kuvvetleri
  1000'e kadar 10 baslangic , sinama tek karsilastirma , en uzun kosumu 9 adim
  hepsi gercekten duruyor mu: True

İlk tablo önceki bölümün sonucunu bozuyor. Bütçe 200, bin başlangıcın bininde ve iki bin başlangıcın iki bininde yetiyor; beş bin başlangıçta 9 tanesini karara bağlayamıyor. “Bütçe 200 yeter” cümlesi, evren yazılmadan hiçbir şey anlatmaz.

İkinci tablo daha keskindir. Her bütçe için, o bütçeyle çalışan karar vericiyi yanıltan bir başlangıç bulundu: bütçe 5 için 3, bütçe 20 için 25, bütçe 100 için 27, bütçe 200 için 2463, bütçe 300 için 26.623. Yanıltan başlangıç bütçe büyüdükçe uzaklaşıyor ama kaybolmuyor. Ölçümün söylediği tam olarak şudur: denenen altı bütçenin altısı için de bir karşı örnek bulundu. Her bütçe için böyle bir örneğin var olduğu bu tablodan çıkarılamaz; o, ölçümün değil kuramın işidir.

Üçüncü blok bambaşka bir kaynaktan gelen bilgiyi gösteriyor. İkinin kuvvetleri için durma, koşturulmadan bilinir: her adım sayıyı ikiye böler, üs kadar adımda 1’e iner. Bu kanıt tek bir karşılaştırmayla sınanır ve 1000’e kadar 10 başlangıcı kapsar. Koşum ise 59.542 adım harcayarak 1000 başlangıcı kapsıyor. Kanıt ucuz ve dar, koşum pahalı ve geniş; ikisi farklı türden bilgi verir ve biri ötekinin yerini tutmaz. İleri Algoritmalar kursundaki ucuz sınama da tek yöne çalışıyordu; buradaki de öyledir.

İki Yanıt ve Üç Yanıt

Bütçeli bir karar vericinin iki tasarımı vardır ve aralarındaki fark ölçülebilir. Birincisi bütçe dolduğunda “durmaz” der ve her başlangıç için bir yanıt üretir. İkincisi bütçe dolduğunda “bilinmiyor” der ve bazı başlangıçları yanıtsız bırakır. İkisi tam olarak aynı koşumu yapar, aynı adımı harcar; ayrıldıkları tek yer, bütçenin bittiği andaki cümledir.

• HM35 — Referans yanıt 100.000 adımlık bir bütçeden alınır. Bu evrendeki başlangıçların tümü 300 adımın altında durduğu için referans, bu evren için kesindir; daha büyük bir evren için aynı şey söylenemez.
• HM36 — Yanlış sayısı, karar vericinin verdiği yanıtın referanstan ayrıldığı başlangıç sayısıdır. “Bilinmiyor” bir yanıt sayılmaz ve yanlış sayılmaz.

"""Iki yanitli karar verici ile uc yanitli olanin ayni evrende karsilastirilmasi."""


def sayac_kosumu(n, butce):
    adim = 0
    while n != 1 and adim < butce:
        n = 3 * n + 1 if n % 2 else n // 2
        adim += 1
    return n == 1, adim


def iki_yanitli(n, butce):
    """Butce dolunca 'durmaz' der. Yanilabilir."""
    durdu, _ = sayac_kosumu(n, butce)
    return "durur" if durdu else "durmaz"


def uc_yanitli(n, butce):
    """Butce dolunca 'bilinmiyor' der. Yanilmaz , ama her zaman yanit vermez."""
    durdu, _ = sayac_kosumu(n, butce)
    return "durur" if durdu else "bilinmiyor"


UST = 5000
gercek = {n: sayac_kosumu(n, 100000)[0] for n in range(1, UST + 1)}
print(f"evren {UST} baslangic , gercek yanit 100000 adimlik kosumdan alindi")
print("butce  iki yanitli: yanlis  uc yanitli: yanlis  bilinmiyor  harcanan adim")
for butce in (5, 20, 50, 100, 200, 300):
    yanlis2 = yanlis3 = bilinmiyor = harcanan = 0
    for n in range(1, UST + 1):
        harcanan += sayac_kosumu(n, butce)[1]
        y2, y3 = iki_yanitli(n, butce), uc_yanitli(n, butce)
        if (y2 == "durur") != gercek[n]:
            yanlis2 += 1
        if y3 == "bilinmiyor":
            bilinmiyor += 1
        elif (y3 == "durur") != gercek[n]:
            yanlis3 += 1
    print(f"{butce:5d}  {yanlis2:19d}  {yanlis3:18d}  {bilinmiyor:10d}  {harcanan:13d}")

evren 5000 baslangic , gercek yanit 100000 adimlik kosumdan alindi
butce  iki yanitli: yanlis  uc yanitli: yanlis  bilinmiyor  harcanan adim
    5                 4993                   0        4993          24985
   20                 4758                   0        4758          98948
   50                 3110                   0        3110         218633
  100                 1666                   0        1666         332345
  200                    9                   0           9         387867
  300                    0                   0           0         387968

Aynı bütçe, aynı koşum, aynı adım — iki ayrı sonuç. İki yanıtlı tasarım bütçe 5’te 4993 başlangıçta yanılıyor; bütçe 200’de 9, bütçe 300’de 0. Üç yanıtlı tasarım hiçbir bütçede yanılmıyor: yanlış sütunu altı satırda da 0. Ödediği bedel yanıtsız bıraktığı başlangıçlardır ve bu sayı yanlış sütunundakiyle birebir aynı. Yani üçüncü yanıt bir bilgi kaybı değil, yanlışın adının doğru konmasıdır.

Son sütun bir şeyi daha söylüyor. Bütçe 200’den 300’e çıkarken harcanan adım 387.867’den 387.968’e, yani yalnız 101 adım artıyor — çünkü 200 adımı geçen yalnız 9 başlangıç var. Kalan belirsizliği kapatmanın bedeli, ona kadar harcanan bütün bütçenin yanında on binde üçtür. Belirsizliğin ucuz kapandığı yerde kapatılmaması bir tasarım kusurudur; ama bu evrende ucuz olması, her evrende ucuz olacağı anlamına gelmez.

Durma Problemi Neden Karar Verilemez

Şimdiye kadar ölçülen her şey tek bir kural içindi. Durma problemi bundan geneldir: verilen bir program betimi ile verilen bir girdi için, o programın durup durmayacağını söylemek. Bu problemin karar verilemez olduğu kuramın kanıtlanmış bir sonucudur ve aşağıdaki taslak o kanıtın biçimidir; bu derste hiçbir koşum bunu kurmaz.

Varsayılsın ki her program betimi ve her girdi için doğru yanıt veren bir karar_ver yordamı var. O zaman ikinci bir yordam yazılabilir: karsit, kendisine verilen bir betimi alır, karar_veri o betim üzerinde o betimin kendisini girdi vererek çağırır; yanıt “durur” ise sonsuza dek döner, yanıt “durmaz” ise hemen durur. Şimdi karsit kendi betimiyle çağrılsın. karar_ver “durur” derse karsit dönmeye başlar, yani durmaz. “Durmaz” derse karsit hemen durur. İki durumda da varsayılan yordam yanlış yanıt vermiştir. Varsayım çelişki ürettiğine göre böyle bir yordam yoktur.

Bu kanıtın gücü, hiçbir bütçeye başvurmamasıdır. Önceki bölümde her bütçe için bir karşı örnek arandı ve bulundu; kanıt ise aramaz, tek bir yordamın var olamayacağını gösterir. Bir önceki derste anılan tez burada işe yarar: sonuç tek bir modele değil, “yordam” kavramının kendisine ilişkindir, çünkü tez bütün makul modelleri aynı kümeye bağlar.

Sonucun mühendislikteki karşılığı şudur: bir programın davranışına ilişkin soruların büyük bölümü için her programda doğru yanıt veren bir yordam yoktur. İki programın aynı çıktıyı verip vermediği, bir kod parçasının hiç çalışmayacağı, bir döngünün sonlanacağı — bunların hepsi durma problemini içerir ve hepsi aynı sonucun kapsamındadır. Bu, çözümleme araçlarının yararsız olduğu anlamına gelmez; söylediği şey, böyle bir aracın iki değil üç yanıt vermek zorunda olduğudur. Önceki dersin durdu, dongu ve bilinmiyor biçimindeki üçlü ayrımı tam olarak buydu ve o üçüncü küme keyfî bir eksiklik değil, sonucun kendisidir.

İleri Algoritmalar kursunun bıraktığı iki borçtan biri burada ödendi. Bazı sorular için yanıtın bilinmemesi bilgimiz hakkında değil, problemler hakkında bir gerçek olabilir ve durma problemi bunun kanıtlanmış örneğidir. İkinci borç, yani kaba kuvvetten daha iyisinin neden bilinmediği, hâlâ açıktır: orada sorulan şey bir sorunun çözülüp çözülemeyeceği değil, ne kadar hızlı çözülebileceğidir.

Özet

• Tek satırlık sayaç kuralında 1000 başlangıçtan bütçe 5’te 7, 20’de 155, 50’de 569, 100’de 756 ve 200’de 1000 tanesi karara bağlanıyor; harcanan adım 4985’ten 59.542’ye çıkıyor.
• En uzun koşum n=871 için 178 adım sürüyor ve ara değer 190.996’ya yükseliyor; kural bir satır, davranış öngörülemez.
• 1000 başlangıcın 1000’inin durması, hepsinin duracağının kanıtı değildir.
• Aynı 200 bütçesi 1000 ve 2000 başlangıçta hepsini karara bağlıyor, 5000 başlangıçta 9 tanesini bağlayamıyor; denenen altı bütçenin altısı için de yanıltan bir başlangıç bulundu.
• Kanıt ucuz ve dardır: ikinin kuvvetleri için durma tek bir karşılaştırmayla bilinir ve 1000’e kadar 10 başlangıcı kapsar; koşum 59.542 adımla 1000 başlangıcı kapsar.
• Durma probleminin karar verilemez olduğu kuramın sonucudur, koşumun değil; sonucun pratik karşılığı ölçülmüştür: iki yanıtlı karar verici 5000 başlangıçta bütçe 5’te 4993 kez yanılırken, aynı koşumu yapan üç yanıtlı tasarımın yanlış sayısı altı bütçede de sıfırdır.

Sonraki Adım

Hesaplama Modelleri konusu sınırın bir yüzünü gösterdi: bazı soruların yanıtı hiçbir yordamla verilemez. Sonraki konu öteki yüzü alır. Orada bütün problemler karara bağlanabilir olacak, soru yalnız kaç adımda olacaktır. Karmaşıklık Sınıfları, İleri Algoritmalar kursunun bıraktığı ikinci borcu üstlenir ve önce en kolay sınıfı kurar: polinom zamanda çözülebilen karar problemleri.