Turing makinesi

Açılış sahnesi

Kerem, Öklid'in yöntemini bir kez daha kâğıt üzerinde uyguluyor, ama bu kez her hareketini not ediyor. Bir sayıyı okudu. Onun altına bir sayı yazdı. Bir rakamı sildi. Bir satır aşağı indi. Her an kâğıdın yalnızca küçük bir bölümüne bakıyordu, birkaç rakama, bir satıra. Kafasında da yalnızca birkaç şey tutuyordu: şu an hangi adımdaydı, bir sonraki adımda ne yapacaktı. Kerem, bütün hesabın bu birkaç basit hareketin art arda gelmesinden oluştuğunu fark ediyor.

Tolga, bu hareketlerin bir makineye verilip verilemeyeceğini soruyor. Makine, bir şerit üzerindeki kareleri tek tek okuyabilir, bir kareye bir işaret yazabilir ya da silebilir, bir kare sağa ya da sola gidebilirdi. Selin, bu kadar yoksul bir makinenin Öklid'in yöntemini, hatta her algoritmayı yapıp yapamayacağını merak ediyor. Lina, makinenin yalnızca iki işaret tanısa bile, bütün alfabeleri bu iki işaretle yazmanın mümkün olup olmadığını düşünüyor. Barış, bir yargıcın, önüne konan her usul yasasını okuyup uygulayabildiğini, tek bir makinenin de başka makinelerin talimatlarını okuyup uygulayıp uygulayamayacağını soruyor. Defne ise hastanenin bilgisayarlarının belleği sınırlıyken, sonsuz bir şeridi olan bir makinenin neyi betimlediğini soruyor. Bu ders, Mantık ve Akıl Yürütme programının Metalojik ve Hesaplanabilirlik kursunda, Turing'in kalem ve kâğıtla hesap yapan bir insanın ne yaptığını hangi en basit işlemlere indirgediğini, bu işlemlerle kurulan soyut makinenin nasıl çalıştığını ve bütün öteki makineleri taklit edebilen evrensel bir makinenin varlığının ne anlama geldiğini soruyor.

Bu derste ne olacak

Önce bu dersin yerini belirleyelim. Algoritma dersi, bir algoritmanın sezgisel kavramını, sonluluk, belirlilik, etkinlik ve genellik özellikleriyle betimledi ve Markov'un yeniden yazma kurallarını, algoritmayı kesinleştirmenin bir yolu olarak tanıttı. Metateori modülünün Karar verilebilirlik dersi ise Turing'in 1936 tarihli makalesini, karar probleminin çözümsüzlüğünü gösteren sonucu açısından ele almış, durma problemini tanımlamıştı. Bu ders, aynı makalenin öteki yanına bakıyor: Turing'in makineyi hangi çözümlemeyle kurduğunu, makinenin nasıl çalıştığını ve evrensel makine düşüncesini inceliyor.

Sonra üç kaynağa bakacağız. Alan Turing, 1936'da yayımladığı Hesaplanabilir Sayılar makalesinin dokuzuncu bölümünde, bir insanın hesap yaparken yaptıklarını adım adım çözümler ve bu çözümlemeden makinesinin tanımına ulaşır. Emil Post, aynı yıl yayımladığı Sonlu Birleşimsel Süreçler makalesinde, Turing'den bağımsız olarak, bir dizi kutu üzerinde çalışan bir işçinin yapabileceklerini betimleyen çok benzer bir model önerir. Claude Shannon ise 1956'da yayımladığı İki İç Durumlu Evrensel Bir Turing Makinesi makalesinde, evrensel bir makinenin ne kadar küçük olabileceğini inceler.

Ardından üç itirazı tartacağız: sonsuz şeridin gerçekçi olmadığı, Turing'in çözümlemesinin insan zihnini fazla dar bir biçimde betimlediği ve Turing makinesinin gerçek hesaplamayı modellemek için fazla ilkel olduğu itirazları.

Sonda, bir hesaplamayı bir Turing makinesi olarak yazmanın dört adımını göstereceğiz: şeridin başlangıçtaki içeriğini ve alfabeyi belirlemek, makinenin iç durumlarını ve her durumun ne anlama geldiğini yazmak, her durum ve okunan her işaret için ne yapılacağını söyleyen bir tablo kurmak ve makinenin bir girdiyle adım adım çalışmasını izlemek.

Merkez soru

Sorumuz şu: Turing, bir insanın hesap yaparken yaptıklarını hangi en basit işlemlere indirgedi ve bu işlemlerle kurulan makine ile onun evrensel biçimi, algoritma kavramı hakkında ne gösterir?

Ölçülü iddiam şu: Turing'in makinesi, bir soyutlama değil, bir çözümlemenin sonucudur. Turing, kalem ve kâğıtla hesap yapan bir insanın ne yaptığını sordu ve bu yapılanları, hesabın özünü bozmadan, en basit parçalarına ayırdı. İnsan her an kâğıdın sınırlı bir bölümünü görür. Aklında sınırlı sayıda durum tutar. Her adımda yalnızca bir işareti değiştirir ya da bakışını yakın bir yere kaydırır. Bu gözlemlerden, sonlu sayıda iç durumu olan, bir şerit üzerinde tek bir kareyi okuyup yazan ve bir kare sağa ya da sola giden bir makine çıkar. Makinenin bütün davranışı, her durum ve her işaret için ne yapılacağını söyleyen sonlu bir tabloyla verilir. Post'un aynı yıl, bağımsız olarak, çok benzer bir modele ulaşması, bu çözümlemenin keyfi olmadığını düşündürür. Turing'in makalesinin en derin buluşu ise evrensel makinedir. Bir makinenin tablosu da şeride yazılabilecek bir işaret dizisidir. Evrensel makine, bu diziyi okur ve betimlenen makinenin yapacağı her şeyi adım adım yapar. Böylece tek bir sabit makine, her algoritmayı, ona verilen bir betimlemeyle yürütebilir. Shannon, böyle bir makinenin yalnızca iki iç durumla kurulabildiğini gösterdi. Turing makinesi, gerçek bilgisayarların bir tasarımı değil, bir hesabın ilke olarak ne gerektirdiğinin ölçüsüdür. Sonsuz şerit, belleğin sonsuz olduğunu değil, hesap için ne kadar bellek gerekeceğinin önceden sınırlanmadığını söyler.

Sıfır noktası

Bir öğrenci Turing makinesinin tanımını ilk kez gördüğünde, onun ne kadar yoksul olduğuna şaşırır. Bir şerit, bir okuma başlığı, birkaç durum ve bir tablo. Toplama, çarpma, karşılaştırma gibi işlemler bile makinenin temel işlemleri arasında değildir; hepsi, işaretleri tek tek okuyup yazan adımlardan kurulmalıdır.

Bu yoksulluk bilinçlidir. Turing'in amacı, pratik bir hesap makinesi tasarlamak değil, hesap yapmanın en az neyi gerektirdiğini göstermekti. Bir hesabın her adımı, anlayış ya da sezgi gerektirmeyen, yalnızca kurala uyarak yapılabilen bir işlem olmalıydı. Turing'in makinesi, bu sıkılığın sınırına kadar götürülmüş bir ölçüttür.

Bu yüzden Turing makinesinin neyi yapabildiği sorusu, sezgisel algoritma kavramının neyi kapsadığı sorusuna çok yakındır. Makinenin yapamadığı bir şey, eğer Turing'in çözümlemesi doğruysa, hiçbir algoritmanın da yapamadığı bir şeydir. Bu yakınlığın tam olarak ne kadar olduğu, modülün sonraki dersinin konusudur.

Görüşler ve pozisyonlar

Turing makinesinin algoritma kavramıyla ilişkisi konusunda üç görüş var.

Birinci görüş, model görüşüdür. Buna göre Turing makinesi, algoritma kavramının kullanışlı bir matematiksel modelidir. Başka modeller de mümkündür ve Turing makinesinin ayrıcalıklı bir yeri yoktur. Onu seçmek bir kolaylık meselesidir.

İkinci görüş, çözümleme görüşüdür. Buna göre Turing makinesi, kurala uyarak hesap yapan bir insanın ne yaptığının kavramsal bir çözümlemesidir. Onun ayrıcalığı, öteki modellerden farklı olarak, sezgisel kavramdan doğrudan, bir dizi makul gözlemle türetilmesidir.

Üçüncü görüş, fiziksel görüştür. Buna göre Turing makinesi, fiziksel bir aygıtın, bir bilgisayarın ya da bir beynin yapabileceklerinin bir ölçüsüdür. Makinenin yapamadığını hiçbir fiziksel sistem yapamaz.

Bu ders ikinci görüşü temel alır ve birinci görüşün, başka modellerin de bulunduğu gözlemini kabul eder. Birinci görüş, Markov'un kurallarının ve Post'un işçisinin de algoritma kavramını modellediğini doğru görür. Ama Turing'in modelinin, sezgisel kavramdan bir çözümlemeyle türetildiği için, öteki modellerin neden aynı kapsama sahip çıktığını açıklamaya en yakın model olduğunu hesaba katmaz. Üçüncü görüş, Turing makinesini insan hesabından fiziksel sistemlere genişletir. Ama Turing'in çözümlemesi bir insanın kurala uyarak yaptığı hesap hakkındaydı. Fiziksel sistemlerin neyi hesaplayabildiği ayrı bir sorudur.

Argümanın yapısı

Bir hesaplamayı bir Turing makinesi olarak yazmak için dört adım izlenebilir.

Birinci adım, şeridin başlangıçtaki içeriğini ve alfabeyi belirlemektir. Yazan, girdinin şeride hangi işaretlerle ve nasıl yazılacağını ve makinenin hangi işaretleri tanıyacağını belirtir.

İkinci adım, makinenin iç durumlarını ve her durumun ne anlama geldiğini yazmaktır. Yazan, makinenin hesap sırasında aklında tutması gereken her bilgiyi, örneğin bir elde ya da bir aşama, ayrı bir durum olarak tanımlar.

Üçüncü adım, her durum ve okunan her işaret için ne yapılacağını söyleyen bir tablo kurmaktır. Yazan, her satırda, hangi işaretin yazılacağını, başlığın hangi yöne gideceğini ve hangi duruma geçileceğini belirtir.

Dördüncü adım, makinenin bir girdiyle adım adım çalışmasını izlemektir. Yazan, makineyi somut bir girdiyle çalıştırır, her adımda şeridin, başlığın yerinin ve iç durumun ne olduğunu yazar ve sonucun beklenen sonuç olup olmadığını denetler.

En güçlü itiraz

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

Turing makinesini ciddiye alan düşünce şu cevabı verebilir. Turing'in makinesi, kurala uyarak hesap yapan bir insanın ne yaptığının çözümlemesinden türetildi. Selin'in insan hesapçısında görüldüğü gibi, hesap yapan kişi her an sınırlı sayıda işaret görür, aklında sınırlı sayıda durum tutar ve her adımda yalnızca bir işareti değiştirir ya da bakışını kaydırır. Bu gözlemlerden, sonlu sayıda iç durumu olan, bir şerit üzerinde tek bir kareyi okuyup yazan bir makine çıkar ve onun bütün davranışı sonlu bir durum tablosuyla verilir. Kerem'in bir ekleyen makinesinde ve Tolga'nın ikilik sayacında görüldüğü gibi, en basit hesaplar bile bu tabloyla yazılabilir. İç durumlar, hesap yapanın aklında tuttuğu şeylerin karşılığıdır. Post'un aynı yıl bağımsız olarak çok benzer bir modele ulaşması, çözümlemenin keyfi olmadığını düşündürür. Lina'nın iki işaretinde görüldüğü gibi, alfabenin küçüklüğü makinenin yapabileceklerini değiştirmez. Turing'in en derin buluşu ise evrensel makinedir. Bir makinenin tablosu da şeride yazılabildiği için, tek bir sabit makine her algoritmayı yürütebilir. Shannon, böyle bir makinenin yalnızca iki iç durumla kurulabildiğini gösterdi. Barış'ın usul yargıcında görüldüğü gibi, bu evrensellik anlamaya değil, okumaya dayanır. Defne'nin sınırlı belleğinde görüldüğü gibi, sonsuz şerit, belleğin sonsuz olduğunu değil, önceden sınırlanmadığını söyler.

Açık kalan sorular

Kerem'in bir ekleyen makinesi, hesabın anlamının makinenin içinde değil, işaretleri sayı olarak okuyan kişinin yorumunda olduğunu gösterdi. Bir makinenin bir hesap yaptığını söylemek, onun işaretlerini yorumlayan birinin varlığını mı gerektirir? Yorumlayan kimse yoksa, bir fiziksel süreç bir hesap mıdır?

Barış'ın usul yargıcı, yargıcın evrenselliğinin anlamaya, makinenin evrenselliğinin ise okumaya dayandığını gösterdi. Anlamak, yeterince ayrıntılı bir okumadan başka bir şey midir? Bir evrensel makine, yeterince karmaşık bir tabloyla, bir yasanın belirsiz maddesini yorumlamayı taklit edebilir mi?

Gödel'in itirazı, insan zihninin sınırlı bir durumlar kümesine hapsolmadığını öne sürdü. Zihnin gelişmesi, yeni durumlar kazanması, bir Turing makinesinin şeridine yeni işaretler yazmasından temelde farklı mıdır? Zihin, kendi durum tablosunu değiştirebilen bir makine olabilir mi?

Yaygın hatalar

Kendin dene

Aklında kalsın

Beş cümlede dersin iskeleti.

Turing makinesi, sonlu sayıda iç durumu olan, bir şerit üzerinde tek bir kareyi okuyup yazan ve bir kare sağa ya da sola giden bir makinedir; davranışı sonlu bir durum tablosuyla belirlenir ve bu tanım, kurala uyarak hesap yapan bir insanın ne yaptığının çözümlemesinden türetilmiştir.

Turing'in Hesaplanabilir Sayılar makalesinin dokuzuncu bölümü insan hesapçıyı en basit işlemlere indirgedi, Post'un Sonlu Birleşimsel Süreçler makalesi aynı yıl bağımsız olarak çok benzer bir modele ulaştı, Shannon'ın 1956 tarihli makalesi ise evrensel bir makinenin yalnızca iki iç durumla kurulabildiğini gösterdi.

Bir hesaplama dört adımla bir Turing makinesi olarak yazılır: şeridin içeriğini ve alfabeyi belirlemek, iç durumları ve anlamlarını yazmak, her durum ve işaret için ne yapılacağını söyleyen bir tablo kurmak ve makinenin bir girdiyle adım adım çalışmasını izlemek.

Sonsuz şeridin gerçekçi olmadığı, Turing'in çözümlemesinin insan zihnini dar betimlediği ve makinenin fazla ilkel olduğu itirazları, şeridin yalnızca belleğin önceden sınırlanmadığını ifade ettiğini, çözümlemenin zihnin tamamı değil kurala uyarak hesap yapma hakkında olduğunu ve makinenin sorusunun hız değil yapılabilirlik olduğunu gördüğümüzde cevaplanabilir.

Bu yüzden evrensel Turing makinesinin varlığı, her algoritmanın tek bir sabit makinede, ona verilen bir betimlemeyle yürütülebildiğini gösterir ve bu evrensellik anlamaya değil, okumaya dayanır.

Sonraki derse köprü

Post'un işçisi ile Turing'in makinesi, iki farklı insan tarafından aynı yıl birbirinden bağımsız olarak kurulmuştu ve neredeyse aynı şeyleri yapabiliyordu. Algoritma dersinde görülen Markov'un yeniden yazma kuralları da aynı hesapları yapabiliyordu. Selin, bu örtüşmenin bir rastlantı olup olmadığını soruyor.

Kerem, Church'ün ve Gödel ile Herbrand'ın da, bambaşka yollardan, hesaplanabilir işlevlerin tanımlarını verdiğini ve bu tanımların hepsinin aynı işlevleri kapsadığının kanıtlandığını hatırlıyor. Tolga, bütün bu tanımların, sezgisel algoritma kavramının tam olarak kapsadığı şeyi kapsayıp kapsamadığını, bunun kanıtlanıp kanıtlanamayacağını merak ediyor. Defne, bir gün Turing makinesinin yapamadığı bir hesabı yapan bir aygıtın bulunup bulunamayacağını soruyor.

Bir sonraki ders bu soruya dönüyor. Church–Turing tezi dersi, sezgisel olarak hesaplanabilir olan her şeyin bir Turing makinesiyle hesaplanabildiğini söyleyen tezin ne tür bir iddia olduğunu, birbirinden bağımsız tanımların örtüşmesinin onu nasıl desteklediğini ve tezin kanıtlanabilir bir teorem mi, bir tanım mı, yoksa bir doğa yasası mı olduğunu soruyor.