Alan Turing, 1936 yılında Turing makinelerini icat ettiğinde, modern bilgi işlemin de mucidi olmuştur.
Hesaplama, çoğumuzun sezgisel olarak anladığı tanıdık bir kavramdır. f(x) = x + 3 fonksiyonunu ele alalım. x üç olduğunda, f(3) = 3 + 3. Altı. Çok kolay. Bu fonksiyonun hesaplanabilir olduğu çok açık görünüyor. Ancak bazı fonksiyonlar o kadar basit değildir ve hesaplanıp hesaplanamayacaklarını belirlemek o kadar kolay değildir, yani bize hiçbir zaman nihai bir cevap vermeyebilirler.
1928 yılında Alman matematikçiler David Hilbert ve Wilhelm Ackermann Entscheidungsproblem ("karar problemi") adı verilen bir soru ortaya attılar. Zamanla bu soru, matematikçilerin bir dizi yeni problemi yanıtlamasına olanak tanıyan ve teorik bilgisayar biliminin temelini atan hesaplanabilirliğin resmi bir tanımına yol açacaktı.
Tanım, 1936 yılında sadece hesaplama kavramını resmileştirmekle kalmayıp aynı zamanda matematikteki temel bir soruyu kanıtlayan ve elektronik bilgisayarın icadı için entelektüel bir temel oluşturan ufuk açıcı bir makale yazan Alan Turing adlı 23 yaşındaki bir yüksek lisans öğrencisinden geldi. Turing'in büyük öngörüsü, hesaplama sorusuna, daha sonra doktora danışmanı Alonzo Church tarafından Turing makinesi olarak adlandırılan soyut bir makine biçiminde somut bir yanıt sağlamaktı. Soyuttur, çünkü fiziksel olarak elle tutulur bir aygıt olarak var değildir (ve var olamaz). Bunun yerine, kavramsal bir hesaplama modelidir: Eğer makine bir işlevi hesaplayabiliyorsa, o işlev hesaplanabilir demektir.
Şöyle çalışıyor. Bir Turing makinesi, sonsuz uzunluktaki bir bant üzerindeki sembolleri, bir kurallar tablosunda belirtildiği şekilde okuyabilir ve değiştirebilir. Bant, her biri tam olarak bir sembol saklayabilen "hücrelerden" oluşur ve makine hücrelerin içeriğini bir bant kafası ile okur ve yeniden yazar. Tablodaki her kural, makinenin hem mevcut durumuna hem de okuduğu sembole bağlı olarak ne yapması gerektiğini belirler. Makine son bir duruma ("kabul durumu" ya da "reddetme durumu") girebilir ve bunun üzerine girdiyi kabul ederek ya da reddederek durur. Ya da sonsuz bir döngüye girer ve bandı sonsuza kadar okumaya devam eder.
Bir Turing makinesini anlamanın en iyi yolu basit bir örnek üzerinde düşünmektir. Bize verilen bir girdinin sıfır sayısı olup olmadığını söylemek için tasarlanmış bir makine hayal edelim. Boş sembollerle (#) birlikte 0001 giriş numarasını kullanacağız, bu nedenle "#0001#" kasetimizin ilgili kısmıdır.
Makine q0 olarak adlandıracağımız başlangıç durumunda başlar. Kasetimizdeki en soldaki hücreyi okur ve boş bir alan bulur. Kurallar şöyle der: "q0 durumundayken, sembol # ise, değişiklik yapmadan olduğu gibi bırakın, bir hücreyi sağa taşıyın ve makinenin durumunu q1 olarak değiştirin." Bu adımdan sonra makine q1 durumundadır ve kafası ikinci sembol olan 0'ı okumaktadır.
Şimdi bu koşullar için geçerli bir kural arıyoruz. "q1 durumunda kalın ve kafayı bir hücre sağa kaydırın" diyen bir kural buluyoruz. Bu bizi aynı konumda bırakıyor (q1 durumunda, "0" okunuyor), bu yüzden kafa sonunda farklı bir sayı, 1 okuyana kadar sağa hareket etmeye devam ediyoruz.
Tabloya tekrar baktığımızda yeni bir kural buluyoruz: "Eğer 1 ile karşılaşırsak, 'reddet' durumu olan q2'ye geç." Makine durur ve orijinal soruya "Hayır" yanıtını verir: "'0001' sıfır mı?"
Bunun yerine girdi "#0000#" ise, makine tüm bu sıfırlardan sonra bir # ile karşılaşır. Tabloya baktığımızda, bunun makinenin q3 durumuna, bir "kabul" durumuna girdiği anlamına geldiğini söyleyen bir kural buluruz. Şimdi makine "'0000' sıfır mı?" sorusuna "Evet" yanıtını veriyor.
Soyut makinesi ile Turing, resmi olarak şu soruyu soran Entscheidungsproblem'i yanıtlamak için bir hesaplama modeli oluşturdu: Bir dizi matematiksel aksiyom göz önüne alındığında, verilen bir ifadenin doğru olup olmadığını her zaman belirleyebilecek mekanik bir süreç - bugün algoritma olarak adlandırdığımız bir dizi talimat - var mıdır?
Belirli bir satranç pozisyonunun mümkün olup olmadığını bize söyleyebilecek bir algoritma bulmak istediğimizi varsayalım. Burada aksiyomlar, yasal hamleleri yöneten satranç kurallarıdır. Bu pozisyona ulaşmak için sonlu bir adım adım prosedür dizisini takip edebilir miyiz? Bazı pozisyonları analiz etmek ömrümüzden daha uzun sürse de - bir algoritma tüm olası pozisyonları üretebilir ve her birini girdiyle karşılaştırabilir - bu tür algoritmalar satranç oyununda mevcuttur. Sonuç olarak, satrancın "karar verilebilir" olduğunu söylüyoruz.
Ancak, 1936'da Church ve Turing - farklı yöntemler kullanarak - Entscheidung probleminin her örneğini çözmenin genel bir yolu olmadığını bağımsız olarak kanıtladılar. Örneğin, John Conway'in Hayat Oyunu gibi bazı oyunlar karar verilemezdir: Hiçbir algoritma, bir başlangıç örüntüsünden belirli bir örüntünün ortaya çıkıp çıkmayacağını belirleyemez.
Turing, istenen görevi yerine getirebilecek bir algoritma varsa bir işlevin hesaplanabilir olduğunu gösterdi. Aynı zamanda, bir algoritmanın bir Turing makinesi tarafından tanımlanabilen bir süreç olduğunu gösterdi. Dolayısıyla, hesaplanabilir bir fonksiyon, onu hesaplayacak bir Turing makinesine sahip olan bir fonksiyondur. Bu, hesaplanabilirliği tanımlamak için dolambaçlı bir yol gibi görünebilir, ancak elimizdeki en iyi yol bu. Massachusetts Teknoloji Enstitüsü'nde teorik bilgisayar bilimcisi olan Michael Sipser, "Bunu başka bir şekilde tanımlamak gibi bir seçeneğiniz yok" dedi. "Church-Turing tezinin, gayri resmi algoritma kavramının herhangi bir 'makul' hesaplama modelinin yapabileceklerine karşılık geldiğini söylediği genel olarak kabul görmektedir." Diğer matematikçiler, yüzeyde oldukça farklı görünen ama aslında eşdeğer olan farklı hesaplama modelleri geliştirdiler: Turing makinelerinin yapabildiği her türlü hesaplamayı yapabilirler ve bunun tersi de geçerlidir.
Kurt Gödel'in matematiğin eksik olduğunu kanıtlamasından sadece birkaç yıl sonra Church ve Turing bu çalışmalarıyla matematikteki bazı problemlerin karar verilemez olduğunu gösterdiler - ne kadar sofistike olursa olsun hiçbir algoritma bize cevabın evet mi yoksa hayır mı olduğunu söyleyemez. Her ikisi de matematiğin düzenli, idealize edilmiş yanıtlara sahip olmasını uman Hilbert için yıkıcı darbelerdi. Ama belki de böylesi daha iyidir: Entscheidung probleminin genel bir çözümü olsaydı, bu matematikteki tüm problemlerin basit mekanik hesaplamalara indirgenebileceği anlamına gelirdi.
Turing'in makinesi, bu temel soruları yanıtlamanın ötesinde, evrensel Turing makinesi olarak bilinen bir varyant aracılığıyla doğrudan modern bilgisayarların geliştirilmesine de öncülük etmiştir. Bu, herhangi bir girdi üzerinde başka herhangi bir Turing makinesini simüle edebilen özel bir Turing makinesi türüdür. Diğer Turing makinelerinin bir tanımını (kurallarını ve giriş bantlarını) okuyabilir ve davranışlarını kendi giriş bandında simüle ederek simüle edilen makinenin üreteceği çıktının aynısını üretebilir, tıpkı günümüz bilgisayarlarının herhangi bir programı okuyup çalıştırabilmesi gibi. 1945 yılında John von Neumann, von Neumann mimarisi olarak adlandırılan ve evrensel Turing makinesi kavramını gerçek hayattaki bir makinede mümkün kılan bir bilgisayar mimarisi önerdi.
Princeton Üniversitesi'nde teorik bilgisayar bilimcisi olan Sanjeev Arora, bu kavramı öğretirken daha geniş bir felsefi resme vurgu yapıyor. "İki tane 'evrensel' kavramı var," diyor. "Evrenselin bir kavramı, başka herhangi bir Turing makinesini çalıştırabilmesidir. Ancak 'evrensel'in diğer, daha büyük kavramı, evrende bulacağınız herhangi bir hesaplamayı çalıştırabileceğidir." Klasik fizik dünyasında, herhangi bir fiziksel süreç algoritmalar kullanılarak modellenebilir veya simüle edilebilir ve bunlar da bir Turing makinesi tarafından simüle edilebilir.
Dikkate değer ve giderek daha kullanışlı hale gelen bir diğer varyant ise olasılıksal Turing makinesidir. Her girdiye iyi tanımlanmış bir tepki veren normal bir Turing makinesinin aksine, olasılıklı bir Turing makinesi olasılıklara dayalı birden fazla tepkiye sahip olabilir. Bu, aynı girdi için farklı zamanlarda farklı sonuçlar verebileceği anlamına gelir. Şaşırtıcı bir şekilde, bu tür bir olasılıksal strateji, belirli problemler için tamamen deterministik bir yaklaşımdan daha verimli olabilir. Olasılıksal Turing makinelerinden elde edilen fikirlerin kriptografi, optimizasyon ve makine öğrenimi gibi alanlarda pratik olarak yararlı olduğu gösterilmiştir.
Bu soyut makineler, temel sorular sormanın bir bilim insanının yapabileceği en faydalı şeylerden biri olabileceğinin belki de en iyi kanıtıdır.
Hiç yorum yok:
Yorum Gönder