Turing makinesi ve evrensellik fikri, ortaya konuluşundan yıllar sonra, günümüz bilgisayarlarında kullanılan mimarinin temelini oluşturmakla kalmadı. Giderek, hesaplamanın doğanın temel süreçlerinden biri olduğu, evreni büyük bir bilgisayar olarak düşünmemiz gerektiği söylenir oldu. Bunları Alan Turing’in çocukken annesinin masasında görüp hayran olduğu daktilodan esinlenerek 24 yaşında kurguladığı bir modele borçluyuz.
Alan Turing dünyayı değiştiren bir dahiydi. İnsanlığa katkısını özetlemek bile bu yazı için hedeflediğimden uzun sürer. Büyük buluşlarından sadece birini ortaya çıkışından bugüne kadarki gelişimiyle anlatmaya çalışacağım.
Karar Problemi
17. yüzyılın büyük bilginlerinden Gottfried Leibniz, dört aritmetik işlemi de doğrudan yapabilen ilk makineyi gerçekleştirmek için yıllarını vermişti. “En basit fikirli kişinin bile makine kullanarak kesinlikle yapabileceği hesaplar için mükemmel insanların saatlerce köleler gibi uğraşmasına değmez!” diyen Leibniz, hedefini sadece dört işlemle sınırlı tutmuyordu. Verilen bir matematiksel önermenin doğru mu yanlış mı olduğunu belirleyecek bir makinenin de yapılabileceğini düşündü ve bunun için ilk adım olarak önermelerin ifade edilebileceği net bir dil tasarlamaya girişti.
Asırlar geçti. 1928’de David Hilbert ve Wilhelm Ackermann, Leibniz’in hayaline benzer bir proje için zamanın geldiğini düşündüler. Matematik dünyasına, artık yeterince geliştirilmiş olan biçimsel dille yazılmış herhangi bir mantıksal önermenin verilen öncüller kullanılarak kanıtlanabilir olup olmadığını saptayabilen bir yöntemin (şimdi kullandığımız terimle, bir “algoritma”nın) bulunması için çağrıda bulundular. Böyle bir algoritmanın var olduğundan hiç kuşkuları yoktu, sadece birisinin onu keşfetmesi gerekiyordu, sonrasında artık matematikçiler ispat işlerini bu algoritmaya göre çalışan makinelere bırakabilir, ilgilendikleri herhangi bir önermenin doğru mu yanlış mı olduğunu otomatik olarak öğrenebilirlerdi! Hilbert’in radyo kaydı da olan ünlü “Bilmeliyiz. Bileceğiz!” sözü bu kesin güveni yansıtır.
Yıllar Hilbert’i haksız çıkardı. Genç İngiliz matematikçi Alan Turing bu “Karar Problemi” üzerinde çalıştı ve 1936’da şaşırtıcı bir çözüme ulaştı: Böyle bir algoritma yoktu! Dolayısıyla, her derde deva bir “mantık makinesi” yapmak da mümkün değildi. Ama Turing bu önemli buluşun tadını çıkarabildi mi dersiniz?
Okyanusun diğer yanında, Princeton’da matematikçi Alonzo Church de aynı konuda yıllarca çalışmış ve Turing’inkinden farklı bir yöntemle aynı sonuca ulaşarak birkaç ay önce yayımlamıştı. Bu nedenle Church’den habersiz çalışan Turing’in makalesini gönderdiği dergi özgün olmadığı gerekçesiyle yayımlamaya yanaşmıyordu. Sorunu iki makaleyi de okuyan Cambridge hocası Max Newman çözdü. Newman, Turing’in ispatında kullandığı yöntemin kendi başına önemli bir katkı olduğunu fark etti ve yayıncıları ikna etmeyi başardı. Böylece bilgisayar biliminin kurucu metni yayımlanabilmiş oldu.
“Makine”
Peki Church’ün çalışmasında olmayıp Turing’inkinde olan, bu nedenle işin uzmanlarına, sözgelimi efsanevi Kurt Gödel’e “Hah, işte Karar Problemi şimdi çözülmüş oldu” dedirten bu ikna edici yöntem neydi? Bunu anlamak için Karar Problemini tanıtırken değindiğimiz bir noktayı tekrar vurgulamak gerekli: Problem bir algoritmanın ortaya konulmasını istiyordu, ama o zamanlar “algoritma” dediğimiz şeyin net matematiksel bir tanımı yoktu. Akıllara “bir hesaplamayı gerçekleştirmek için kullanılabilen, muğlak olmayan, basit adımlardan oluşan bir yordam” gibi bir tarif geliyordu, ama bir şeyin böyle bir yöntem olup olmadığını kesinkes ayırt etmeye yarayan bir tanım mevcut değildi. Gödel, Church’ün çalışmasında esas aldığı oldukça soyut çerçevenin bu anlamda her “yapılabilir hesap işi”ni gerçekleştirebileceğine ikna olmamıştı örneğin.
Turing ise makalesine matematiksel işlemler yapan (ve yorulma, uyuma, acıkma, yaşlanma, dikkat dağınıklığı, kâğıt/kalem eksikliği vs. pratik sorunları hiç yaşamayan) bir insanı temsil eden bir “makine” türünü gerekli netlikte tanımlayarak başlıyordu. Bu bağlantıyı, aşağıda göreceğiniz gibi, o kadar basit şekilde anlatıyordu ki, okuru insanların yapabileceği her cins hesap işinin bu türden bir makinece de gerçekleştirilebileceğine ikna ediyor, böylece nihayet “algoritma” kavramına bir tanım getirmiş oluyordu. Bu noktadan sonra ispatın geri kalanı, doğru mu yanlış mı olduğunu bu türden makinelerin hiçbirinin saptayamayacağı bir mantıksal önermenin sunulmasından, dolayısıyla Hilbert’in istediği “her derde deva” algoritmanın var olmadığının gösterilmesinden ibaretti.
Daha sonra Church’ün taktığı adla, bir “Turing makinesi” (TM) şu iki bileşenden oluşur:
– Kareli bir defterin ilk satırını (ya da eğer isterseniz bir tuvalet kâğıdını) sonsuza dek uzatarak gözünüzde canlandırabileceğiniz, her karesine bir sembol yazılabilen, ve istenen karesine erişilip oradaki sembolün okunmasına ve istenirse silinip yerine bir başkasının yazılmasına imkân veren bir teyp. (Modellediğimiz insanın sınırsız miktarda kâğıt/kalem/silgi kullanabilmesi bu şekilde temsil ediliyor. Bu insanın belli bir anda kâğıdın sadece bir noktasına bakabileceği gerçeğine de, bu okuma/yazma işlemlerinin sadece teyp üzerinde sağa sola gezdirilebilen tek bir “teyp kafası”nın o anda üstünde olduğu karede yapılabilmesiyle sadık kalınıyor.)
– (Modellediğimiz insanın belleği gibi) sınırlı bir miktarda bilgi tutabilen bir kontrol birimi. Uygulanacak yordamın adımları da bu bilgilere dahildir. Günümüzün terminolojisini kullanırsak, bu “program” makinenin bir sonraki adımında ne yapması gerektiğini belirler. Her program sonlu sayıda (“şimdi üstünde olduğun karede Y harfini görüyorsan onu silip yerine Z harfini yaz, sonra kafayı bir soldaki kareye getir”, “8 numaralı komuta atlayıp oradan devam et”, “çalışmayı durdur” vb.) basit “komut”lardan oluşur.Her komut birim zamanda icra edilebilir.
Belli bir işlev için hazırlanmış bir TM’nin yanıtlamasını istediğimiz soruyu teybine yan yana gerekli sayıda kareye birer sembol kondurarak yazabiliriz. Bu noktadan sonra makine çalıştırılır ve her adımda programında sıradaki komutu gerçekleştirir. Programın makineye “girdi” olarak verilen sorunun yanıtını, gerekli işlemlerle hesaplatıp teybe yazdırması, sonra da çalışmayı durdurması beklenir. (Kimi programlar kimi girdilerle başlatıldıklarında sonsuz bir döngüye girip hiç durmayabilirler, örneğin sürekli “teyp kafasını bir sağdaki kareye getir” komutunu tekrarlayan bir makine sonsuza dek çalışacaktır. Her girdi için sonlu sayıda adım sonucunda bir yanıt verip duran yordamları tercih ederiz elbet.)
Hepsi bu! Turing ne kadar karışık ve uzun olursa olsun her belirli hesap yordamının yukarıda anlatılan komutların basitliğinde parçalara bölünebileceğini,bu yordamı uygulayan bir insanın yaptıklarının da bu cinsten bir makine tarafından taklit edilebileceğini iddia ediyordu. Düşünün, sözü edilen türden bir işi yaparken (örneğin iki büyük sayıyı çarparken) kafanıza ilkokuldayken yerleştirdiğiniz bir programın adımlarını sırayla icra eder, kâğıtta yazılı sayılara bakıp beyninizdeki çarpım tablosundan bu kurallara göre getirdiğiniz yeni bir şeyler yazar, en sondaki toplamayı da benzer şekilde halleder, sonunda da kendinizi aranan yanıtı yazmış bulursunuz, değil mi?
Church ve Turing kısa sürede birbirlerinin yöntemlerinin eş güçte olduğunu, yani Church’ün modeline uyan her hesap yöntemi için aynı işi yapabilen bir TM kurulabileceğini gösterdiler. Yıllar boyunca “algoritma” kavramı için önerilen çok sayıda diğer farklı görünüşlü model de incelendikten sonra, bunların her birini taklit edebildiği görülen TM modelinin kavramın “resmi” tanımı olarak kabul edilmesi konusunda bir kuşku kalmadı.
Evrensellik
Buraya kadarı bile büyük başarıydı, ama Turing’in makalesinin çağ değiştiren bulgusundan daha söz etmedik. Aklınıza gelen her algoritma için ayrı bir TM inşa edilebilir, örneğin yukarıda sözünü ettiğimiz ilkokul tipi çarpma yordamını gerçekleştiren, girdi olarak verilen iki sayının çarpımını hesaplayan bir TM tasarlayabilirsiniz. Ama Turing o gün için çok şaşırtıcı olan bir uygulama gösterdi: Başka TM’leri taklit etme işi!
Turing “evrensel” bir TM tasarlamıştı. Bu makineye E diyelim. E’ye girdi olarak canınızın istediği (diyelim ki adı T olan) bir başka TM’nin tarifini ve yanına da T’ye girdi olarak verilecek soruyu verebilirsiniz. Bu durumda E, T’nin o soru üzerindeki çalışmasını baştan sona birebir taklit eder ve eğer T bu çalışmanın sonunda duracaksa da, T ne yanıt veriyorsa aynısını verir. Turing TM’lerin başka her sistemin benzetimini (simülasyon) yapabilme özelliğini, tek bir fiziksel makineye sonsuz sayıda değişik iş yaptırabilmek için kullanabileceğimizi keşfetmişti.
O güne dek insanlar her makineyi sadece tek bir iş için tasarlarlardı. Otomobiller ulaşım, buzdolapları soğutma, radyolar da iletişim içindi. Oysa Turing bize tek bir makine alıp ona birçok farklı makineyi taklit ettirebileceğimizi söylüyordu.
Bilgisayarlardan söz ettiğimizi anladınız, değil mi? Çağımızda bu “hesaplama evrenselliği” kavramını anlamak kolay, çünkü tek bir cihaz satın alıp onun üzerinde muhasebe programı, oyun programı, kelime işleme programı, resim yapma programı vs. bin türlü farklı program çalıştırarak bin değişik makinenin keyfini çıkartmak bize doğal geliyor. Ama Turing makalesini yazdığında tüm bu farklı işleri yapabilen tek bir makine bilimkurgudan ibaretti. Akıllı telefonlarımızı bize o hediye etti.
Doğa yasaları
Albert Einstein aklını kullanarak evrende bir hız sınırı olduğunu keşfetmişti; ne kadar güç harcarsanız harcayın, asla ışık hızına erişemezsiniz. Turing Karar Problemini tuzla buz ederken benzer bir doğa yasasının da bilgisayarları (ve aslına bakarsanız TM’lerin taklit edebileceği her şeyi, yani insanları da) bağladığını ve ne kadar uğraşırsak uğraşalım asla çözemeyeceğimiz kimi problemlerin var olduğunu kanıtlamış oldu. Bu fikri gözden geçirelim:
Benzetim yetenekleri sayesinde TM’ler günümüzün (ve geleceğin) bilgisayarlarını taklit edebilir, herhangi bir bilgisayar ne yaparsa bir TM de onun“gibi yapabilir”. Bu nedenle TM bilgisayar biliminin temel modelidir: İşlemci hızı, ekranın kaç renk gösterdiği, fare mi klavye mi kullanıldığı vb. güncel teknolojik ayrıntıları göz ardı edip şimdi ve gelecekte her bilgi işlem aygıtında olması gereken ortak unsurları (girdi, bellek, sonlu kaynaklar kullanan adımlardan oluşan belirli bir program ve çıktı) temsil ettiği için, eğer belli bir işi hiçbir TM’nin yapamayacağını kanıtlarsak o işin hiçbir bilgisayarca yapılamayacağını da kanıtlamış oluruz. Ve Turing de bunu başardı.
Şu problemi düşünün: Ben size bir bilgisayar programının metnini vereceğim. Siz de bu programı inceleyip sonlu bir zaman içinde bana bu programın çalıştırılması halinde sonsuz bir döngüye girip girmeyeceğini söyleyeceksiniz. Bu işi size verebileceğim her girdi (yani her farklı program) için doğru yanıtı vererek bitirmenizi sağlayacak bir algoritma var mıdır? Dikkat edin, “Verilen programı çalıştırıp bakarım, cevabı ona göre veririm” diyemezsiniz, çünkü bunu yaparsanız ve programın çalışması uzun süre beklemenize karşı bitmezse onun sonsuz bir döngüye mi girdiğini, yoksa sadece uzun süre çalışmış ve artık durmasına az kalmış bir program mı olduğunu bilemezsiniz. Karara benzetim yoluyla değil, “inceleme” yoluyla varmanız gerekmekte.
(Laf aramızda, böyle bir algoritma bulsanız çok iyi olurdu, çünkü yazılım geliştiren insanlar bu kontrolü yapabilmeyi gerçekten çok isterler. Yani bu işi yapan bir programı çok iyi fiyata satabilirdiniz. Ama maalesef…)
Turing Karar Problemiyle ilgili kanıtının içinde göz kamaştırıcı basitlikte bir yöntemle işte bu “Durma Problemi”nin de hiçbir TM (ve dolayısıyla hiçbir bilgisayar programı, hiçbir insan, vs.) tarafından yukarıda istenen genellikte çözülemeyeceğini gösterdi. Evrende hiçbir uygarlık ne denli uğraşırsa uğraşsın, bu işi yapan bir program yazamaz. Bu türden soruları bu ölçütlere göre yanıtlayan hiçbir makine hiçbir zaman inşa edilemez. Sizi bilmem ama, bana bu çok net bir doğa yasası gibi geliyor. Sonraki yıllarda bu “kararlaştırılamazlık” özelliğine sahip birçok problem daha keşfedildi.
Karmaşıklık
Turing şifre çözme alanındaki çalışmalarıyla başını 2. Dünya Savaşı gibi bir beladan kurtardığı kendi devletinin hoyratlığı sonucu genç yaşta öldü. O saçma sapan muameleye maruz kalmasaydı, daha neler yaratırdı kim bilir. Ama TM’lerin hikâyesi bitmedi.
Çözüm yöntemini bildiğiniz iki problem düşünün, örneğin ikisini de ilkokulda öğrendiğiniz toplama ve çarpmayı. 12345 ve 67890 sayılarını birbiriyle toplamak mı daha çok vaktinizi alır, yoksa çarpmak mı? Daha uzun, sözgelimi onar rakamlı iki sayı verseydim peki?
Algoritmalar birbirleriyle bu fikir esas alınarak karşılaştırılabilir. Her algoritma için yatay eksenin verilen girdinin uzunluğunu, dikey eksenin de bu algoritmanın bu uzunluktaki olası girdilerden en zoru için kaç adım çalışacağını gösterdiği bir “adım sayısı grafiği” çizdiğimizi düşünelim. Kuşkusuz girdilerin uzunluğu arttıkça adım sayıları da artacaktır, ama bu artışı gösteren grafiğin şekli problemden probleme farklı olacaktır. Sözgelimi toplama algoritmamız için bu iş yapıldığında adım sayısının kabaca doğrusal olarak arttığını, yani grafiği sonsuza doğru uzattığımızda şeklinin soldan sağa yükselen bir doğruya benzeyeceğini göreceğiz.
İlkokulda öğrendiğimiz çarpma algoritması için benzer bir grafikse uzatıldıkça doğrusal değil, karesel olarak (türevi giderek artarak) yükselir. Bir algoritmanın girdisi uzadıkça adım sayısı ne kadar hızlı yükseliyorsa, bu o algoritmanın genelde o denli yavaş olduğu anlamına gelir. Öyle ki toplamayı yavaş, çarpmayı ise çok daha hızlı işlemcileri olan iki farklı bilgisayarda yapsanız ve ikisini aynı anda başlatsanız bile, yeterince çok rakamlı sayılar için toplama işlemi çarpmadan daha önce bitecektir.
A problemini çözen en hızlı algoritmanın adım sayısı grafiği yukarıdaki anlamda B problemininkinden daha hızlı yükseliyorsa A’nın B’den daha “zor” olduğunu (teknik terimle, “zaman karmaşıklığının daha yüksek” olduğunu) söyleriz. Elbette bu karşılaştırmaları adil şekilde yapabilmek için tüm algoritmaları aynı dilde yazmamız gerekir. Doğru tahmin ettiniz, burada yine algoritma kavramının resmi tanımı olarak TM’ler devreye girer.
Halihazırda kullandığımız bilgisayarlar, ve az sonra değineceğimiz tek bir istisna dışında, TM tanımının fiziksel gerçekliğe dayanan tüm güncel sürümleri, yukarıda anlatılan TM modelince hem zaman, hem de benzer şekilde tanımlanan bellek miktarı karmaşıklığı açısından verimli şekilde taklit edilebilir. (Yani yeni türden her makinenin yaptığı her işi, genel resmi değiştirmeyen ufak bir yavaşlama ve dış bellek ihtiyacında ufak bir artış ile bir TM’ye de yaptırabilirsiniz.) Bu nedenle problemlerin sınıflandırılması için TM’ler arasında yapılan bir zaman karmaşıklığı karşılaştırmasının gerçek dünyadaki cihazlarımız için de geçerli olacağından eminiz.
Kanıtlamayı başarabildiklerimiz bir yana, hâlâ kesin zorluk derecesini bilemediğimiz problemlerin çokluğu ve ilginçliği, hesaplama karmaşıklığı kuramını, halen kuramsal bilgisayar biliminin ve hatta tüm matematiğin en heyecanlı konularından biri haline getirmiştir. Kesin olarak söyleyebildiğimiz bir sonuca örnek olarak iki problem tanımlayayım:
Komşu kentler arasındaki karayolu bağlantılarının anlatıldığı bir listeye bakarak adı verilen iki kentten birinden diğerine karayolundan gitmenin mümkün olup olmadığını saptama işine Yol Bulma Problemi diyelim. (Anadolu gibi her yerden her yere karayoluyla ulaşılabilen değil, muhtemelen kopuklukların olduğu bir coğrafya ve kentlerin adının alfabetik sırada verildiği bir liste düşünün.)
İki kişinin 3’e 3’lük kareli bir alana sırayla X ve O harflerini koyup bir doğru üzerine aynı harften 3 tanesini getirmeye çalıştığı ünlü XOX oyununun istenen bir boyuta genişletilip kuralların da buna uyumlu olarak genelleştirildiği bir oyun tarif edilmiştir. Bu oyunun verilen “m”, “n” ve “k” sayıları için m’ye n’lik alanda bir doğruya k sembol yerleştirme hedeflenen sürümünde bir oyuncuya diğer oyuncu ne yaparsa yapsın oyunu kazandıracak bir stratejinin var olup olmadığını saptama işine de XOX Problemi diyelim.
Evet, Yol Bulma Probleminin XOX Probleminden çok ama çok daha kolay olduğu bilimsel olarak kanıtlanmıştır! Sağduyuya uygun görünen bu sonucun güç yanı, bir problem (bu durumda XOX Problemi) için ilk aklınıza gelen algoritmadan çok daha verimli bir başka algoritmanın var olmadığını kanıtlamakta yatar. Örneğin çarpma için ilkokulda öğrendiğimizden çok daha hızlı (ama hâlâ toplamanınkinden yavaş) bir algoritmanın 2007 yılında keşfedildiğini biliyor muydunuz?
Modelin yeni sürümleri
Turing’in modeli sağduyuya uygun olarak tasarlandığı için kabul edilmesi kolay oldu. Fakat fizik bilimi modelin doğanın işleyişi hakkında barındırdığı kimi sağduyusal varsayımların doğru olmadığını söylüyor. Sözgelimi, TM modeli belirlenimcidir (deterministik), belli bir TM’ye belli bir girdi sunulduğunda tüm davranışı kesinlikle belirlenmiş olur; aynı işlem kaç kez yapılırsa yapılsın tıpatıp aynı sonuç çıkar; sapmalara, hatalara yer yoktur. Gerçek dünya pek böyle değildir! Benzer şekilde, sınırsız miktarda ikincil bellek (“hard disk”) kullanma imkânı, sonlu miktarda madde içeren evrenimizde gerçekçi görünmemektedir. Turing’den sonraki yıllarda tüm bu varsayımlar sorgulandı ve modelin gerçeği daha iyi yansıtan sürümleri tanımlandı. Bu modellerden ikisini inceleyeceğiz.
Daha önce tanımladığımız temel TM modeline bir “para atışı”nın sonuçlarına göre kontrol akışını belirleyebilme hakkı verelim. Bu özellik makinenin icra edebileceği komut türlerine “1/2 olasılıkla 5 numaralı komuta, 1/2 olasılıkla da 9 numaralı komuta atla” gibisinden bir “olasılıksal dallanma” komutu eklenerek hayata geçirilebilir. Bu yeni makine türüne “Olasılıksal TM” (OTM) denir.
TM’lerin aksine OTM’ler belirlenimci olmadıklarından her soruya her zaman aynı yanıtı vermeyebilirler. Elbette biz her zaman doğru yanıtı isteriz, ama hata olasılığı daima sıfır olan bir OTM’nin hiçbir işi standart bir TM’den daha hızlı yapamayacağı kolayca kanıtlanabilir. Az da olsa bir miktar, diyelim trilyonda bir hata olasılığını sineye çekersek OTM’lerin kimi işleri (örneğin verilen bir sayının asal olup olmadığını saptama işini) bilinen en iyi TM’den daha hızlı yaptığını gösterebiliriz. OTM’ler gerçekten TM’lerden üstün müdür? Henüz bilmiyoruz, ama uzmanların çoğunluğu bir gün her problem için az hata yapan bir OTM’ninkine denk hızda bir TM bulunduğunun gösterilebileceğine inanıyor.
Kuantum
Yukarıda TM’lerin bir istisna hariç önerilen tüm ciddi alternatif modelleri az bir yavaşlamayla taklit edebildiklerinden söz etmiştik. Şimdi o istisnayı anlatma zamanı geldi.
20. yüzyılın başlarında fizikte bir devrim yaşandı. Artık doğanın çok, ama çok tuhaf kuralları olduğunu biliyoruz. Temel parçacıklar aynı anda iki ayrı yerde, iki farklı durumda olabiliyorlar sözgelimi. İnanması zor, ama kuşku bırakmayacak kesinlikte saptanmış bir doğa yasası bu.
Turing’in modeli ve yerleşik programlama yaklaşımları, Newton fiziğine göre işleyen bir dünyayı esas almaktadır. Acaba kuantum fiziğinin bu yeni ilginç özelliklerinden daha hızlı hesaplama yapmak için yararlanılabilir mi? Aşılması güç kimi teknik engeller söz konusu olsa da çoğu uzman “kuantum bilgisayarları”nın günün birinde inşa edilebileceğini düşünüyor. Henüz ortada olmamalarına karşın bu bilgisayarlara özgü algoritmaların nasıl kurulabileceğini düşünebilmemiz için ise yine bir biçimsel modele, yani TM’lerin kuantum fiziğine uygun bir sürümüne ihtiyacımız var.
Kuantum Turing makinesi (KTM) modeli bu amaçla tanımlanmıştır. Standart TM tanımında tüm bileşenlerin (teybin ve kontrol biriminin) şu aynı anda birden fazla durumda olabilen parçacıklardan inşa edildiğini düşünün. Bu makine artık aynı anda birçok paralel koldan işlem yapabilir. Fizik yasalarının getirdiği kısıtlara uyarak komut repertuarımıza biraz yukarıda OTM’ler için sözünü ettiğimizi andıran “3/5 genlikle 7 numaralı komuta, -4/5 genlikle de 10 numaralı komuta atla” türünden “kuantum dallanma” komutları eklememiz gerekir. (“Genlik”, kabaca “olasılığın karekökü” olarak düşünebileceğimiz ve söz konusu paralel işlem kollarının ağırlıklarını belirleyen bir kuantum kavramıdır.) KTM’lerin de OTM’ler gibi az olasılıkla yanlış yanıt vermelerine göz yumalım.
Genliklerin eksi değerler de alabilmesi nedeniyle dikkatle düzenlenmiş bir KTM hesaplaması sırasında kimi paralel kollar birbirlerini “götürebilir” ve yanlış sonuca giden yoldaki kolların birbirini götürmesi sağlanarak yüksek olasılıkla doğru sonucu veren algoritmalar yazılabilir. Klasik programlamada dengi olmayan bu yöntemle, bilinen hiçbir TM’nin hızla çözemediği, verilen bir tamsayıyı çarpanlarına ayırma problemi için çok hızlı bir KTM tasarlanabilmiştir. İnternet üzerinden şifreli iletişim protokollerinin çoğu bu problemin hızla çözülemeyeceği varsayımına dayandığından, bu algoritmanın bulunmasından sonra kuantum bilgisayarlarının inşası öncelikli bir proje haline gelmiştir. Hatta kim bilir, belki de birisi çoktan büyük ölçekli bir kuantum bilgisayarını inşa etmiştir ama habersizce başkalarının iletişimini dinlemek daha çok işine geldiğinden bunu ilan etmiyordur?
Büyülü TM’ler
Karmaşıklık kuramının merkezî sorusuna, yani çözene Clay Matematik Enstitüsü’nce bir milyon ABD dolarlık ödül vaat edilmiş olan ünlü “P ve NP Problemi”ne bir bakalım.
Verilen bir metnin bir problemin kurallara uygun yazılmış doğru bir çözümü olup olmadığını denetlemek, görece kolay bir iştir. Ama eğer söz konusu metin çok uzunsa, sırf bu nedenden ötürü, denetlemeye zamanımız yetmeyebilir. Problemler kümesi bu bağlamda dörde ayrılır:
1) Çözümsüz problemler (Durma Problemi ve hatta daha beterleri).
2) Çözümü olan, ama çözümün uzunluğunun sorunun uzunluğuna oranla artış hızının yüksekliği nedeniyle çözüm olduğu iddia edilen metinleri genelde yukarıdaki anlamda denetleyemeyeceğimiz problemler (Sözgelimi yukarıda XOX oyunu için anlattığımıza benzer şekilde genelleştirilmiş bir satranç oyununda verilen bir tahta ebadı için kimin kazanan stratejisinin olduğunun hesaplanması böyle bir problemdir).
3) Çözümü soru uzunluğuna oranla görece kısa metinlerle ifade edilebilen, yani verilen bir metnin gerçekten o sorunun çözümü olup olmadığını pratikte denetleyebileceklerimiz (Örneğin verilen bir karayolları haritasında her kente sadece bir kez uğrayarak tüm kentleri dolaşabilecek bir güzergâh varsa, saptama problemi bunlardandır, böyle bir güzergâhın mevcut olduğunu iddia eden birisinden size kentleri o sırayla listelemesini isteyip verdiği listeyi haritayla karşılaştırırsınız, olur biter).
4) Çözümünü başkasından istemeye gerek kalmadan kendi imkânlarımızla makul sürede bulabileceğimiz problemler (Yol Bulma Problemi bunlardandır).
Yukarıdaki listede 3. maddede tanımlanan problemlerin tümünün kümesine NP, 4. maddedekilere de P denir. Bu iki kümenin eşit olup olmadığı bilinmemektedir ve yanıt her neyse kanıtlayacak kişiyi bir milyon dolar beklemektedir. (Sözgelimi 3. maddedeki örnekteki Güzergâh Problemini kimse size güzergâhı vermeden ve olası tüm yol seçimlerini denemeden hızla çözebilen bir algoritma bulursanız milyon sizindir; yalnız uyarayım, böyle bir algoritmanın var olmadığını sanıyorum.)
P ve NP arasındaki ilişkiyi incelemek için yine TM’lere başvurulur tabii. P “TM’lerce hızla çözülebilen problemler kümesi” olarak tanımlanır. NP içinse standart TM tanımına bu kez “İstersen 3 numaralı komuta, istersen 5 numaralı komuta atla” gibisinden “belirlenimci olmayan dallanma”lara el veren “büyülü” bir komut türü ekleyerek oluşturulan “Belirlenimci Olmayan TM” (BOTM) modeli kullanılır. Bir BOTM çalışması sırasında böyle bir komuta gelirse, eğer iki seçenekten birisi onu çözüme götürecek ise, muhakkak o doğru seçeneği seçer! Örneğin Güzergâh Probleminde verilen harita gerçekten aranan özelliğe sahip bir güzergâh barındırıyorsa, bir BOTM belli bir kentten hangi komşu kente gitmek gerektiğini doğru olarak seçecektir. (Bunun gerçek hayatta olamayacağını söylemeye gerek yok elbet.) NP de bu büyülü yeteneğe sahip “BOTM’lerce hızla çözülebilen problemler kümesi” olarak tanımlanır. Standart TM’ler BOTM’lerin yaptığı her işi yapabilir, sözgelimi Güzergâh Problemini biz de oturup çözebiliriz, ama bunu bir BOTM kadar az adımda yapmayı bilemiyoruz. Eğer sanıldığı gibi P NP’ye eşit değilse bu TM’lerin BOTM’leri istenen hızda taklit edemeyeceği anlamına gelir zaten.
“P=NP” ifadesinin doğru mu yanlış mı olduğunu neden mi bunca merak ediyoruz? Çünkü bilgisayarların hem şimdi, hem de gelecekte hangi problemleri makul sürede çözebilip hangilerinde havlu atacağını bilmek istiyoruz. Yine doğanın çizdiği bir sınırı, bu kez pratikte hesaplayabileceklerimizle hesaplayamayacaklarımız arasındakini, keşfetmenin peşindeyiz.
Daktilo
Turing makinesi ve evrensellik fikri, ortaya konuluşundan yıllar sonra, günümüz bilgisayarlarında kullanılan mimarinin temelini oluşturmakla kalmadı. Çok basit bir altyapı ile başka sistemlerin “zihinleri” de dahil çevrelerindeki her şeyi modelleyip benzetimini yapabilecek sistemlerin mümkün olduğunun anlaşılması, bilişsel bilimcilerin zihnin yapısı ve evrimi hakkındaki düşüncelerini şekillendirdi. Bugün hem canlıların evrilmesinde, hem de beynimizin yeni kavramları öğrenmesindeki sınırlar, bu süreçlere denk gelen ve P’nin altkümesi olan özel bir algoritma türü çalışılarak inceleniyor. Kara deliklerin bilgi sızdırmasına ilişkin önemli bir problemin bize hesaplama karmaşıklığını bir fizik yasası olarak görmeyi dayattığını savlayan kuramsal fizikçiler var. Giderek, hesaplamanın doğanın temel süreçlerinden biri olduğu, evreni büyük bir bilgisayar olarak düşünmemiz gerektiği söylenir oldu. Bunları Alan Turing’in çocukken annesinin masasında görüp hayran olduğu daktilodan esinlenerek 24 yaşında kurguladığı bir modele borçluyuz.
Kaynaklar
1) David Hilbert ve Wilhelm Ackermann (1928), Grundzüge der theoretischen Logik, Springer-Verlag.
2) Alonzo Church, “A note on the Entscheidungsproblem”, Journal of Symbolic Logic, 1 (1936), 40-41.
3) Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society, Series 2, 42 (1936-7), 230-265.
4) Michael Sipser (2013), Introduction to the Theory of Computation (3 ed.), Cengage Learning.
5) Stefan Reisch,“Gobang ist PSPACE-vollständig”, Acta Informatica, 13 (1980), 59-66.
6) Leonard M. Adleman, Jonathan DeMarrais ve Ming-Deh A. Huang“Quantum Computability”,SIAM Journal on Computing, 26:5(1997), 1524-1540.
7) Peter Shor, “Polynomial-time algorithms for prime factorization and discrete logarithm problems”, SIAM Journal on Computing, 26:5 (1997), 1484-1509.
8) Aviezri S. Fraenkel ve David Lichtenstein, “Computing a perfect strategy for n x n chess requires time exponential in n”, Journal of Combinatorial Theory, Series A, 31 (1981), 199-214.
9) Leslie Valiant (2013), Probably Approximately Correct, Basic Books.
10) Amanda Gefter, “Theoretical physics: Complexity on the horizon”, Nature,509 (2014), 552-553.
11) Seth Lloyd (2007), Programming the Universe, Vintage Publishing.
12) Sara Turing (2012), Alan M. Turing, Cambridge University Press.
