Turing Makinesi

Önceki iki ders iki modelle bir sınır çizdi. Sonlu otomat girdiyi tek geçişte okuyor ve belleği durum sayısı kadar; üretim kuralı betimini büyütmeden daha çoğunu üretiyor ama karar vermek için arama gerektiriyor. İkisinin de ortak eksiği aynı: okuduklarını değiştiremiyorlar.

Bu ders sınırı olabildiğince gevşetir. Model, iki yönde de sınırsız uzayan bir şeride (tape) sahiptir; şeridin her hücresinde bir simge durur, makine bulunduğu hücreyi okur, üzerine yazar, bir adım sağa ya da sola gider ve durumunu değiştirir. Bu modelin adı Turing makinesidir ve kuram bu adı kullanır. Kursun kuralı gereği burada anılan yalnız addır: kişi anlatılmaz, ad hiçbir kod tanımlayıcısında geçmez. Adın taşıdığı tek bilgi, aşağıdaki tanımın kuramda hangi kavrama karşılık geldiğidir.

Şerit ve Makine

Şerit tek başına yeni bir güç değil, yeni bir bellek biçimidir. Sonlu otomatta bellek durum sayısıyla sınırlıydı ve girdiyle birlikte büyüyemiyordu; şeritte bellek koşum boyunca büyür. Buna karşılık makinenin betimi hâlâ sonludur: durum sayısı ve simge sayısı verildiğinde geçiş tablosunun satır sayısı bellidir. Bu, bir bütçe demektir ve bütçe demek tam sayım demektir.

• HM17 — Şerit iki yönde de boştur; boş hücre 0 simgesini taşır ve 0 yazılmış bir hücre hiç yazılmamış hücreden ayırt edilmez. Abece iki simgelidir.
• HM18 — Bir hücrenin içeriği üçlüdür: yazılacak simge, gidilecek yön, yeni durum. Yeni durum k ise makine durur; başlangıç durumu 0’dır ve makine boş şeritte başlar.
• HM19 — k durumlu, iki simgeli bütün makineler sayılabilir. Geçiş tablosunda 2k hücre vardır ve her hücre $2 \cdot 2 \cdot (k+1)$ seçenekten birini alır. k=1 için 64, k=2 için 20.736 makine.
• HM20 — Bütçe adımdır. Bir adım, tek bir hücre okuma, yazma ve hareketten oluşur. Süre ölçülmez.
• HM21 — “Durduğu bilinen” sayısı birikimlidir: küçük bütçede durduğu görülen bir makine büyük bütçede yeniden sayılmaz.

"""Serit uzerinde calisan makine ailesi: k durumlu , 2 simgeli BUTUN makineler."""
from itertools import product

YAZ = (0, 1)
YON = (-1, 1)


def makineler(k):
    """Hucre: (yazilacak simge, yon, yeni durum). Yeni durum k ise DUR."""
    hucre = [(y, o, d) for y in YAZ for o in YON for d in range(k + 1)]
    yerler = [(durum, simge) for durum in range(k) for simge in (0, 1)]
    for secim in product(hucre, repeat=len(yerler)):
        yield dict(zip(yerler, secim))


def kos(makine, k, butce):
    """Bos serit. Doner: (durdu_mu, adim, serite yazilan 1 sayisi)."""
    serit = {}
    konum, durum, adim = 0, 0, 0
    while adim < butce:
        simge = serit.get(konum, 0)
        yaz, yon, yeni = makine[(durum, simge)]
        serit[konum] = yaz
        konum += yon
        adim += 1
        if yeni == k:
            return True, adim, sum(serit.values())
        durum = yeni
    return False, adim, sum(serit.values())


def butce_taramasi(k, butceler):
    tum = list(makineler(k))
    bilinen = set()
    print(f"k = {k} durumlu aile , makine sayisi {len(tum)}")
    for b in butceler:
        for i, m in enumerate(tum):
            if i not in bilinen and kos(m, k, b)[0]:
                bilinen.add(i)
        print(f"  butce {b:4d}  durdugu bilinen {len(bilinen):6d}"
              f"  bilinmeyen {len(tum) - len(bilinen):6d}")
    return tum


BUTCE = (1, 3, 6, 7, 10, 50, 200)
butce_taramasi(1, BUTCE)
tum = butce_taramasi(2, BUTCE)
print()
dagilim = {}
en_iyi = None
for m in tum:
    durdu, adim, bir = kos(m, 2, 200)
    if durdu:
        dagilim[adim] = dagilim.get(adim, 0) + 1
        if en_iyi is None or (adim, bir) > (en_iyi[1], en_iyi[2]):
            en_iyi = (m, adim, bir)
print("duran makinelerin adim dagilimi:", dict(sorted(dagilim.items())))
print("en uzun duran kosum:", en_iyi[1], "adim ,", en_iyi[2], "adet 1")
print("gecis tablosu:", {f"d{d}s{s}": v for (d, s), v in en_iyi[0].items()})
print()
print("adim  durum  yeni  konum  serit")
serit, konum, durum, adim = {}, 0, 0, 0
while adim < 200:
    simge = serit.get(konum, 0)
    yaz, yon, yeni = en_iyi[0][(durum, simge)]
    serit[konum] = yaz
    konum += yon
    adim += 1
    goster = "".join(str(serit.get(p, 0)) for p in range(min(serit), max(serit) + 1))
    print(f"{adim:4d}  {durum:5d}  {yeni:4d}  {konum:5d}  {goster}")
    if yeni == 2:
        break
    durum = yeni

k = 1 durumlu aile , makine sayisi 64
  butce    1  durdugu bilinen     32  bilinmeyen     32
  butce    3  durdugu bilinen     32  bilinmeyen     32
  butce    6  durdugu bilinen     32  bilinmeyen     32
  butce    7  durdugu bilinen     32  bilinmeyen     32
  butce   10  durdugu bilinen     32  bilinmeyen     32
  butce   50  durdugu bilinen     32  bilinmeyen     32
  butce  200  durdugu bilinen     32  bilinmeyen     32
k = 2 durumlu aile , makine sayisi 20736
  butce    1  durdugu bilinen   6912  bilinmeyen  13824
  butce    3  durdugu bilinen   9600  bilinmeyen  11136
  butce    6  durdugu bilinen   9784  bilinmeyen  10952
  butce    7  durdugu bilinen   9784  bilinmeyen  10952
  butce   10  durdugu bilinen   9784  bilinmeyen  10952
  butce   50  durdugu bilinen   9784  bilinmeyen  10952
  butce  200  durdugu bilinen   9784  bilinmeyen  10952

duran makinelerin adim dagilimi: {1: 6912, 2: 2304, 3: 384, 4: 128, 5: 16, 6: 40}
en uzun duran kosum: 6 adim , 4 adet 1
gecis tablosu: {'d0s0': (1, -1, 1), 'd0s1': (1, 1, 1), 'd1s0': (1, 1, 0), 'd1s1': (1, -1, 2)}

adim  durum  yeni  konum  serit
   1      0     1     -1  1
   2      1     0      0  11
   3      0     1      1  11
   4      1     0      2  111
   5      0     1      1  1111
   6      1     2      0  1111

Üç sayı yan yana. Bütçe: adım bütçesi 1’den 200’e, aile büyüklüğü 64 ve 20.736. Bütçenin yanıtladığı: iki durumlu ailede 9784 makinenin durduğu görüldü; tek durumlu ailede 32. Bütçenin yanıtlayamadığı: iki durumlu ailede 10.952 makine bu bütçede durmadı ve bütçe 6’dan 200’e çıkarıldığında bu sayı hiç değişmedi.

Bütçe süpürmesinin verdiği asıl bilgi doyum noktasıdır. Sayı 1. adımda 6912, 3. adımda 9600, 6. adımda 9784 ve oradan sonra sabit. Adım dağılımı bunu tek satırda gösteriyor: 6912 makine bir adımda, 2304 makine iki adımda duruyor ve altı adımda duran yalnız 40 makine var. Bu ailede duran her koşumun en çok 6 adım sürdüğü kuramın bilinen bir sonucudur; ölçüm bu sonuçla uyuşuyor, onu kurmuyor.

İlk satırdaki 6912 sayısı da hesaplanabilir ve hesaplanması ölçümün doğruluğunu sınar. Makine boş şeritte başladığı için ilk okunan hücre her zaman durum 0 ile simge 0’ın kesişimidir. O hücrenin 12 seçeneği vardır ve bunların 4’ünde yeni durum durma durumudur; yani makinelerin tam üçte biri daha ilk adımda durur. 20.736’nın üçte biri 6912’dir ve tablo bunu veriyor. Ölçümün beklenen bir sayıyı tutturması onu doğrulamaz ama tutturmaması bir kusuru gösterirdi; bu kursta her sayının böyle bir sağlaması aranır.

Son tablo tek bir makinenin izidir ve şeridin ne işe yaradığını gösterir. Makine boş şeritte başlıyor, ilk adımda sola yazıyor, sonra sağa dönüyor ve dört hücreye 1 yazdıktan sonra altıncı adımda duruyor. Aynı hücreye iki kez uğradığı üçüncü ve beşinci adımlara dikkat edilmelidir: makine önceki yazdığını okuyup kararını ona göre veriyor. Sonlu otomatta bunun karşılığı yoktur.

Aynı Yordam Bütün Makineleri Koşturuyor

Yukarıdaki koşumların hepsini yapan tek bir yordam var: kos. Makine, bu yordamın içine gömülmüş değil; argüman olarak veriliyor. 20.736 makinenin her biri bir geçiş tablosudur, yani bir veridir, ve tek bir yordam bu verilerin tümünü yürütüyor. Modelin ayırt edici özelliği budur: bir makinenin betimi başka bir makinenin girdisi olabilir. Bu yüzden bu model evrensel sayılır — programı veri gibi taşıyabildiği için.

Buradan kuramın en çok anılan önermesi çıkar. Church–Turing tezi, sezgisel anlamda “yordamla hesaplanabilir” denen her şeyin bu modelle hesaplanabildiğini söyler. Tezin adında tez sözcüğü rastlantı değildir: bu bir kanıtlanmış önerme değil, biçimsel model ile biçimsel olmayan “yordam” kavramı arasında kurulmuş bir eşleştirmedir. Kanıtlanamaz, çünkü iki yanından biri tanımsızdır; sınanabilir, çünkü önerilen her yeni model şimdiye kadar bu modelle aynı kümeyi hesapladı.

Evrenselliğin ölçülebilir yanı da var. Önceki derste bir ayrım kurulmuştu: otomatta girdiyle büyüyen şey betim, üretim kuralında koşumdu. Şeritli modelde betim hiç büyümez: iki durumlu bir makinenin geçiş tablosu dört satırdır ve şeride kaç hücre yazılırsa yazılsın dört satır kalır. Büyüyen tek şey koşumdur — adım sayısı ve kullanılan hücre sayısı. Bu, gücün nereden geldiğini açıkça gösterir: sonlu bir betim, sınırsız bir çalışma alanı.

Tezin bu derse getirdiği pratik sonuç şudur: bir soruya bu model karar veremiyorsa, o soruya karar verecek bir yordam aramak da boşunadır. Bir sonraki bölümün ölçtüğü şey tam olarak bu sınırın kıyısındadır.

Bütçenin Söylemediğini Kanıt Söyleyebilir mi

“Bu bütçede durmadı” ile “hiç durmaz” aynı cümle değildir ve bu kursta ikincisi bir koşumla yazılmaz. Ama bazen koşumun içinden bir kanıt çıkarılabilir. Şerit iki yönde de boş olduğu için, makinenin görüntüsü yalnız duruma ve şeritteki 1’lerin kafaya göre konumuna bağlıdır. Aynı görüntü ikinci kez oluşursa makine aradaki hareketi sonsuza dek yineler; ilk turda durmadıysa hiçbir turda durmaz. Bu bir gözlem değil, çıkarımdır.

• HM22 — Görüntü, (durum, kafaya göre 1 taşıyan hücrelerin kümesi) ikilisidir. 0 yazılan hücre boş hücreden ayırt edilmez.
• HM23 — Görüntü tekrarı döngü kanıtıdır; makine o koşumda hiç durmaz.
• HM24 — Kanıt bulunamaması bir şey söylemez. Sonuç üç kümeye ayrılır: durdu, dongu ve bilinmiyor.
• HM25 — Döngü taraması da süpürülür: bütçe 10, 50 ve 200’de tekrarlanır.
• HM26 — Çizgede döngü tespiti Veri Yapıları kursunda kuruldu ve burada yeniden anlatılmaz; buradaki tek fark, düğümlerin önceden verilmemesi ve koşum sırasında üretilmesidir.

"""Butcenin yanitlayamadigi makinelerin kaci KANITLA karara baglaniyor."""
from itertools import product

YAZ = (0, 1)
YON = (-1, 1)


def makineler(k):
    hucre = [(y, o, d) for y in YAZ for o in YON for d in range(k + 1)]
    yerler = [(durum, simge) for durum in range(k) for simge in (0, 1)]
    for secim in product(hucre, repeat=len(yerler)):
        yield dict(zip(yerler, secim))


def cozumle(makine, k, butce):
    """Doner: ('durdu' | 'dongu' | 'bilinmiyor', adim).

    Serit iki yonde de bostur; bu yuzden konuma gore otelenmis ayni goruntu
    ikinci kez olusursa makine ayni hareketi sonsuza dek yineler.
    """
    serit = {}
    konum, durum, adim = 0, 0, 0
    gorulen = {(0, frozenset())}
    while adim < butce:
        simge = serit.get(konum, 0)
        yaz, yon, yeni = makine[(durum, simge)]
        serit[konum] = yaz
        konum += yon
        adim += 1
        if yeni == k:
            return "durdu", adim
        durum = yeni
        imza = (durum, frozenset(p - konum for p, v in serit.items() if v))
        if imza in gorulen:
            return "dongu", adim
        gorulen.add(imza)
    return "bilinmiyor", adim


for k in (1, 2):
    tum = list(makineler(k))
    print(f"k = {k} durumlu aile , makine sayisi {len(tum)}")
    en_gec = 0
    for butce in (10, 50, 200):
        sayim = {"durdu": 0, "dongu": 0, "bilinmiyor": 0}
        for m in tum:
            sonuc, adim = cozumle(m, k, butce)
            sayim[sonuc] += 1
            if sonuc == "dongu":
                en_gec = max(en_gec, adim)
        print(f"  butce {butce:4d}  durdu {sayim['durdu']:6d}"
              f"  dongu kanitlandi {sayim['dongu']:6d}"
              f"  bilinmiyor {sayim['bilinmiyor']:6d}")
    print(f"  dongunun en gec yakalandigi adim: {en_gec}")

k = 1 durumlu aile , makine sayisi 64
  butce   10  durdu     32  dongu kanitlandi     16  bilinmiyor     16
  butce   50  durdu     32  dongu kanitlandi     16  bilinmiyor     16
  butce  200  durdu     32  dongu kanitlandi     16  bilinmiyor     16
  dongunun en gec yakalandigi adim: 1
k = 2 durumlu aile , makine sayisi 20736
  butce   10  durdu   9784  dongu kanitlandi   5040  bilinmiyor   5912
  butce   50  durdu   9784  dongu kanitlandi   5040  bilinmiyor   5912
  butce  200  durdu   9784  dongu kanitlandi   5040  bilinmiyor   5912
  dongunun en gec yakalandigi adim: 8

İki durumlu ailede bütçenin karara bağladığı 9784 makinenin yanına, kanıtın karara bağladığı 5040 makine ekleniyor. Geriye 5912 makine kalıyor ve bu ders bunlar için bir şey söylemez. Kalanların çoğu şeritte bir yöne doğru sürüklenen makinelerdir: her adımda yeni bir hücreye yazdıkları için görüntüleri hiç tekrarlanmaz, oysa durmadıkları bir insan gözüyle bakıldığında görülebilir. Kanıt aracının kapsamı, aradığı örüntü kadardır.

Üç kümeye ayırmanın kendisi bu kursun yöntemidir. İki kümeli bir rapor, yani yalnız “durdu” ile “durmadı”, ölçümü bir yargıya çevirirdi; üçüncü küme yargının nerede bittiğini yazılı tutuyor. Tek durumlu ailede de aynı yapı görülüyor: 32 durdu, 16 kanıtlandı, 16 bilinmiyor. Aile 324 kat büyüdüğünde oranlar değişti ama üçüncü küme hiç boşalmadı.

Üç bütçede de aynı sayılar çıkıyor ve nedeni son satırda: döngü en geç 8. adımda yakalanıyor. Yani bütçe 10 ile bütçe 200 arasında bu ölçü için hiçbir fark yok. Aynı derste iki ayrı bütçe süpürmesi iki ayrı sonuç verdi: durma taraması 6’da doydu, döngü taraması 8’de. Doyum noktası bütçenin değil, sorunun özelliğidir.

Özet

• Şeritli makine okuduğu hücreye yazabilir ve iki yönde gezebilir; belleği koşum boyunca büyür, betimi ise sonlu kalır.
• İki simgeli ailelerde bütün makineler sayılabilir: bir durumlu ailede 64, iki durumlu ailede 20.736 makine.
• Adım bütçesi süpürüldüğünde duran makine sayısı 6912, 9600, 9784 diye ilerleyip 6. adımda doyuyor; bütçenin 200’e çıkarılması bu sayıyı hiç değiştirmiyor.
• En uzun duran koşum 6 adım sürüyor ve şeride dört adet 1 yazıyor; bu ailedeki üst sınırın 6 olduğu kuramın sonucudur, ölçüm yalnız onunla uyuşur.
• Tek bir koşum yordamı 20.736 makinenin tümünü yürütüyor; makinenin betimi veridir ve bu, modelin evrensel sayılmasının nedenidir.
• Bütçede durmayan 10.952 makinenin 5040’ı, görüntü tekrarına dayanan bir döngü kanıtıyla karara bağlanıyor; kalan 5912 makine için ölçüm bir şey söylemez.

Sonraki Adım

Bu derste “durdu” sayısı bir bütçeyle, “hiç durmaz” sayısı bir kanıtla geldi ve ikisinin toplamı aileyi kapatmadı. Sonraki ders bu boşluğun rastlantı olup olmadığını sorar. Tek satırlık bir kural üzerinde bütçe 5’ten 200’e süpürülecek, bin başlangıcın hepsinin durduğu görülecek ve tam o noktada dersin en önemli cümlesi yazılacak: gözlem kanıt değildir.