--- title: 'Turing Makinesi' source: 'https://academia.sh/tr/kurslar/hesaplama-kurami/turing-makinesi' course: 'Hesaplama Kuramı' language: tr updated: '2026-08-17T18:08:32+00:00' license: 'CC BY-SA 4.0' --- # Turing Makinesi Şeritli modelin tam sayımla ölçülmesi: 2 durumlu 2 simgeli 20.736 makinenin 9784'ü duruyor, en uzun duran koşum 6 adım ve bütçe 6'dan 200'e çıkarıldığında sayı hiç değişmiyor; durmayan 10.952 makinenin 5040'ı döngü kanıtıyla karara bağlanıyor. Ö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. ```python """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. ```python """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.