Alan Turing ve hesaplanabilirlik: Bir şerit, bir okuma kafası ve sınırlar

Bilgisayarınız her gün milyarlarca işlem yapar. Peki yeterince hızlı ve yeterince büyük bir bilgisayar her soruyu çözebilir mi? Şaşırtıcı biçimde cevap hayır. Hiçbir bilgisayarın, hiçbir programın, ne kadar zaman verilirse verilsin çözemeyeceği iyi tanımlanmış sorular vardır. Bu gerçek, ilk elektronik bilgisayarlar yapılmadan önce, 1936’da kâğıt üzerinde ispatlandı.

İspatı yapanlardan biri genç bir İngiliz matematikçi olan Alan Turing’di. Turing, bir hesap yapan insanın yaptıklarını en basit adımlarına ayırarak bugün “Turing makinesi” dediğimiz hayali bir aygıt tanımladı: Kare hücrelere bölünmüş bir şerit, bir hücreyi okuyan bir kafa ve birkaç kural. Bu yazıda böyle bir makinenin nasıl çalıştığını küçük bir örnekle görecek, evrensel makine fikrini ve hesaplanabilirliğin sınırlarını anlatacağız.

Bir soru: Mekanik bir karar yöntemi var mı?

20. yüzyılın başında David Hilbert ve çevresindeki matematikçiler, matematiği sağlam temellere oturtmak için iddialı bir program yürütüyordu. Bu programın sorularından biri Almanca adıyla Entscheidungsproblem, yani “karar problemi” idi: Verilen herhangi bir mantıksal önermenin ispatlanabilir olup olmadığına, adım adım uygulanan mekanik bir yöntemle karar verilebilir mi?

Bu soruyu cevaplamak için önce “mekanik yöntem” kavramının kesin olarak tanımlanması gerekiyordu. Sezgisel olarak herkes bir algoritmanın ne olduğunu bilir; ama “hiçbir yöntem yoktur” diyebilmek için bütün olası yöntemleri kapsayan bir tanıma ihtiyaç vardır.

Turing’in fikri: Hesap yapan bir insanı sadeleştirmek

Alan Turing 1912’de Londra’da doğdu ve Cambridge’deki King’s College’da matematik okudu. 1936’da “On Computable Numbers, with an Application to the Entscheidungsproblem” (Hesaplanabilir Sayılar Üzerine, Karar Problemine Bir Uygulamayla) başlıklı makalesini tamamladı. Makale London Mathematical Society’nin dergisinde 1936–1937’de yayımlandı.

Turing’in hareket noktası, kareli bir defterde hesap yapan bir insandı. Böyle bir insan:

• her an sayfanın yalnızca küçük bir bölümüne bakar,
• bir işareti okur, gerekirse siler ve yenisini yazar,
• dikkatini bir yan kareye kaydırır,
• ne yapacağına, o anki “zihin durumuna” ve gördüğü işarete bakarak karar verir.

Turing, kâğıdın iki boyutlu olmasının esas olmadığını, bu işlemlerin tek bir şerit üzerinde de yapılabileceğini düşündü. Böylece şu bileşenlerden oluşan bir makine tanımladı:

• Şerit: Kare hücrelere bölünmüş, gerektiği kadar uzatılabilen bir şerit. Her hücrede bir işaret ya da boşluk bulunur.
• Okuma-yazma kafası: Her an tek bir hücrenin üzerindedir. O hücredeki işareti okur, yeni bir işaret yazabilir, bir hücre sola ya da sağa gidebilir.
• Durumlar: Makine her an sonlu sayıdaki durumlardan birindedir.
• Kural tablosu: “Şu durumdaysan ve şu işareti okuyorsan, şunu yaz, şu yöne git, şu duruma geç” biçiminde kurallar.

Makinenin bütün davranışı bu tablo tarafından belirlenir. Hiçbir yaratıcılık, sezgi ya da tahmin yoktur.

Örnek: İkilik bir sayıya 1 eklemek

Şeritte ikilik tabanda 1011 sayısı (onluk tabanda 11) yazılı olsun. Kafa en sağdaki basamağın üzerinde, makine “ekle” durumunda başlasın. Kural tablosu:

Durum	Okunan	Yaz	Git	Yeni durum
ekle	1	0	sola	ekle
ekle	0	1	—	dur
ekle	boş	1	—	dur

Bu kurallar, elle toplama yaparken kullandığımız “eldeyi taşı” fikrinin makine diliyle yazılmış hâlidir. Adım adım izleyelim (köşeli parantez kafanın konumunu gösterir):

Adım	Şerit	Durum
0	1 0 1 [1]	ekle
1	1 0 [1] 0	ekle
2	1 [0] 0 0	ekle
3	1 [1] 0 0	dur

Sonuç 1100, yani onluk tabanda 12. Doğru.

Şeritte 111 (7) yazılı olsaydı kafa bütün 1’leri 0’a çevirerek sola ilerler, en solda boş bir hücreye ulaşır, oraya 1 yazardı: 1000, yani 8. Üç satırlık bir tablo, her uzunluktaki ikilik sayı için çalışır.

Turing’in iddiası çok daha güçlüdür: Bir insanın kurallara uyarak mekanik biçimde yapabileceği her hesap, uygun bir kural tablosu olan böyle bir makineyle de yapılabilir. Bu bir teorem değil, “mekanik hesap” kavramının bir tanımı önerisidir ve bugün hesaplanabilirlik kuramının temel kabullerinden biridir.

Evrensel makine

Makalenin en ileri görüşlü fikirlerinden biri şudur: Bir makinenin kural tablosu da şeride işaretler olarak yazılabilir. Turing, şeritte başka bir makinenin kural tablosunu ve o makinenin girdisini okuyup, o makinenin yapacağı her şeyi adım adım taklit eden tek bir makine kurulabileceğini gösterdi. Buna evrensel Turing makinesi denir.

Bugünkü dille: Program da bir veridir. Aynı donanım, belleğine hangi program yüklenirse onu çalıştırır. Telefonunuzun hesap makinesini, haritayı ve oyunu aynı işlemciyle çalıştırabilmesinin arkasındaki kavramsal fikir budur.

Sınır: Karar verilemeyen sorular

Turing, kural tablolarının sayılabilir olduğunu fark etti: Her tablo sonlu bir metin olarak yazılabilir, bu metinler de bir sıraya dizilebilir. Bu, Cantor’un sonsuzluklar üzerine çalışmasındaki sayılabilirlik fikriyle doğrudan bağlantılıdır. Makineler sayılabilir olduğu hâlde gerçek sayılar sayılamaz olduğundan, hiçbir makinenin hesaplayamayacağı gerçek sayılar vardır.

Daha da önemlisi, Turing makineler hakkındaki bazı genel soruların hiçbir makineyle cevaplanamayacağını köşegen fikrine dayanan bir akıl yürütmeyle gösterdi. Bugün bu tür sonuçlar genellikle “durma problemi” üzerinden anlatılır: Verilen herhangi bir programın verilen bir girdiyle sonunda durup durmayacağına her zaman doğru karar veren bir program yoktur. Turing’in makalesindeki özgün soruların biçimi biraz farklıdır; ama fikir aynıdır. Bugünkü biçimin ana hatları şöyledir:

1. Her program ve girdi için “durur” ya da “durmaz” cevabını her zaman doğru veren bir K programı olduğunu varsayalım.
2. K’yi kullanarak yeni bir Z programı yazalım: Z, kendisine verilen bir P programı için K’ye “P, kendi metni girdi olarak verilince durur mu?” diye sorar. Cevap “durur” ise Z sonsuz döngüye girer; “durmaz” ise Z hemen durur.
3. Şimdi Z’ye kendi metnini verelim. Z duruyorsa, K “durur” demiştir ve Z sonsuz döngüye girmiştir; yani durmaz. Z durmuyorsa, K “durmaz” demiştir ve Z hemen durmuştur; yani durur.
4. İki durumda da çelişki çıkar. Demek ki böyle bir K programı yoktur.

Turing bu tür bir sonuçtan hareketle karar probleminin cevabının olumsuz olduğunu gösterdi: Bütün mantıksal önermeler için ispatlanabilirliğe karar veren mekanik bir yöntem yoktur. Aynı yıl Amerikalı mantıkçı Alonzo Church, farklı bir biçimsel sistemle bağımsız olarak aynı sonuca ulaştı. İki yaklaşımın hesaplama gücü bakımından eşdeğer olduğu da gösterildi.

Makaleden sonra

Turing 1936–1938 yıllarında Princeton’da doktora yaptı. İkinci Dünya Savaşı sırasında Bletchley Park’ta şifre çözme çalışmalarında yer aldı ve Enigma mesajlarının çözülmesinde kullanılan makinelerin tasarımına katkı sağladı. 1945’ten sonra Ulusal Fizik Laboratuvarı’nda program saklayan bir elektronik bilgisayarın ayrıntılı tasarımını hazırladı. 1950’de makinelerin düşünüp düşünemeyeceği sorusunu ele alan ünlü makalesini yayımladı. 1954’te öldü.

Bugün nerede karşımıza çıkar?

• Algoritma düşüncesi: Bir problemi açık, sıralı ve belirsizlik içermeyen adımlara ayırmak, hem matematik problemlerinde hem de programlamada temel beceridir.
• Sayı tabanları: İkilik tabanda toplama, örnekteki makinenin yaptığı işin ta kendisidir.
• Olmayana ergi ile ispat: Durma problemi, çelişkiye ulaşarak ispatın en güçlü örneklerinden biridir.
• Yazılım güvenliği: Bir programın her durumda doğru çalıştığını otomatik olarak doğrulamanın genel olarak mümkün olmaması, yazılım testlerinin ve doğrulama araçlarının neden sınırları olduğunu açıklar.

Bir fikri adım adım kurarak öğretme yaklaşımımızı nasıl öğretiyoruz sayfasında anlatıyoruz.

Kapanış

Turing makinesi hiçbir zaman bir fabrikada üretilmedi; bir düşünce aracıydı. Ama bu basit araç, “hesaplamak” kelimesine kesin bir anlam verdi, her programı çalıştırabilen evrensel bir makine fikrini ortaya koydu ve hesaplamanın aşılamaz sınırları olduğunu gösterdi. Bugün kullandığımız her bilgisayar, 1936’da bir şerit ve bir okuma kafasıyla anlatılan bu fikirlerin mirasını taşır.