En ünlü matematikçilerden biri sayılan Alan Turing‘in ismi, 1980’lere kadar neredeyse hiç bilinmiyordu. Bunun nedenlerinden biri, çalışmalarından bazılarının 1970’Iere kadar gizli tutulmasıydı. Günümüzde biliyoruz ki pek çok önemli katkısının yanında kendisi bir de matematiksel problem çözme makinesi icat etmiştir. Bugün böyle makinelere onun anısına Turing makinesi diyoruz.
Birçoğumuzun bilgisayarları var ve bilgisayarların karmaşık donanım ve yazılımlardan oluştuğu konusunda kabaca bir fikre sahibiz. Ama belki de pek azımız bilgisayar kavramının bu makineler evlerimizde, ofislerimizde ve hatta ceplerimizde her yerde bulunan öğeler haline gelmeden çok önce tasavvur edildiğini biliyoruz.
İlk elektronik bilgisayar, İkinci dünya savaşı sırasında Bletchley Park’ta Alman Enigma kodunu kırmak için inşa edildi. Bu, yukarıda bahsedilen teorik makineyi geliştiren Alan Turing sayesinde oldu. Alan Turing 1936’da hesaplamanın matematiksel modelini kurdu. Bu modelde, günümüzde Turing makinesi olarak adlandırılan soyut bir makine vardı.
Turing günümüzde bilgisayarın mucidi olarak kabul edilmektedir. Ardından yapay zeka çalışma alanını icat eden de yine çok büyük ölçüde o olmuştur.
Turing Makinesi Nedir?
1930’larda Cambridge Üniversitesi’nde matematik öğrencisi olan Turing, dönemin belli başlı matematik problemlerinden “Entscheidungsproblem”i çözmek gibi zamanın ötesinde bir hedef koymuştu. (Bu terim Almancada “karar problemi” anlamına gelir)
Matematikçi David Hilbert’in 1928’de ortaya attığı bu problemde, belli bir tarife uyarak cevaplanamayacak soruların olup olmadığı sorulur. Bu karar problemleri evet veya hayır şeklinde bir cevabı olan matematiksel sorulardır. “2 + 2 = 4 müdür?”, “7919 asal sayı mıdır?” soruları cevabı evet olan karar problemlerine örnektir. Karar problemi “cevabını nasıl bulacağınızın hiçbir tarifi olmayan sorular da var mıdır?” diye sorar.
Turing’in bu probleme yaklaşım biçimi ise oldukça garipti. Bunu için matematiksel bir problem çözme makinesi icat edecekti. Turing makinesi aritmetik hesaplamalarının kağıt kalem ile yapılma sürecini taklit eden hayali bir cihazdı. Tam olarak nasıl çalıştığını anlamak için öncelikle fonksiyon kavramını düşünmelisiniz.
Sonuçta fonksiyonlar da bir nevi makinelerdir. Bu makineye bazı girdiler verir ve çıktılar elde edersiniz. Peki aynı fikri algoritmalar aracılığı ile bilgisayarlara uygulamak mümkün mü? Turing’in yaptığı da tam olarak buydu.
Soyut Turing makinelerinin çalışma ilkesi gayet basittir. Makine sonsuz uzunlukta olduğu varsayılan bir şeridin üzerindeki girdileri okur ve işler. Sonrasında da çıktıları yine bu şeridin üzerine yazar. Şerit, her biri sadece tek bir sembol içeren ya da boş olan karelere bölünmüştür. Makinede, her seferinde bandın bir sembolünü okuyan bir okuyucu yer alır.
Makine okuduğu veriyi işledikten sonra o karedeki sembolü silerek yeniden yazar ya da hiçbir şey yapmaz. Ayrıca makinenin okuma ve yazma işlemlerini yapan kafa kısmı işlemi tamamladıktan sonra bir birim sağa ya da sola hareket eder.
Bu eylemlerden hangisini gerçekleştirdiği ve gerçekten yaparsa hangi yeni sembolü yazdığı, içinde bulunduğu duruma bağlıdır. Daha sonra solda veya sağda bir sonraki sembolle karşılaştığında, yine içinde bulunduğu duruma göre tepki verir. Temsili bir Turing makinesini aşağıda görüyorsunuz.
Turing Makinesi Nasıl Çalışır?
Bir Turing makinesini doğru programlayarak, her türlü hesaplamayı yapmasını sağlayabilirsiniz. Ayrıca, gerçek bir bilgisayar tarafından yapılabilecek herhangi bir hesap Turing makineleriyle de yapılabilir. En temel fark, gerçek bilgisayarların aksine, Turing makinelerinin okuyabileceği, işleyebileceği ve yazabileceği veri miktarının sınırsız olmasıdır. Hilbert’ın problemini çözmek için yapılması gereken tek şey, herhangi bir Turing makinesinin cevaplayamayacağı bir karar problemi olduğunu göstermekti.
Şimdi Bir Turing makinesi yaptığımızı ve bu makineden toplama işlemi yapmasını istediğimizi düşünelim. Bunun için öncelikle giriş bandınızı 110111100000…..biçiminde hazırlamanız gerekecektir. Bunun anlamı ise şudur.
- Durum 0: Mevcut konum 1’e sahipse, bir adım sağa hareket edin;
- Durum 0: Mevcut konum 0’a sahipse, 1 ile değiştirin, bir hücre sağa hareket ettirin. Durumu, durum1 olarak değiştirin;
- Durum 1: Mevcut konumda 1 varsa, bir hücre sağa hareket ettirin;
- Durum 1: Mevcut konumda 0 varsa, bir hücre sola hareket ettirin. Durumu, durum 2 olarak değiştirin.
- Durum 2: Mevcut konumda 1 varsa, 0 ile değiştirin ve durun.
Bu döngü ile sonunda istenen sonucu temsil eden arka arkaya altı tane 1 elde ederiz. Ancak elbette bir program kendi içinde sonsuz döngüye de girebilir. Belirli bir programın durup durmayacağını belirleme sorunu, kendi başına matematiksel mantıkta çok ilginç gelişmelere yol açtı.
Bilgisayarların Sınırı Nedir?
Turing’in bir sonraki numarası, makinelerinin genel amaçlı problem çözme makineleri haline getirilebileceğini göstermekti. Verdiğiniz her tarife uyan bir Turing makinesi tasarladı. Bugün bu genel amaçlı Turing makinelerine Evrensel Turing Makinesi diyoruz. Aslında bilgisayar, çalışma biçimi göz önüne alındığında, Evrensel Turing Makinesi’dir.
Bir Turing makinesi kurduğunuzu ve girdiyi sonsuz uzunluktaki bandın üzerine yazıp makineye verdiğinizi düşünün. Verileri okuyup işlemeye başlayan makine bir süre sonra durup size cevabı mı verir, yoksa sonsuza kadar çalışmaya devam mı eder? Bu sorunun cevabını verecek genel bir algoritma var mıdır? Aslına bakarsanız bu da bir karar verme problemidir.
Durma Probleminin Karar Verilemez Olması Ne Anlama Gelir?
Alan Turing bu soruya cevap verebilen bir Turing makinesinin çelişki yaratacağını anlamıştı. Dolayısıyla bir Turing makinesinin durup durmadığını kontrol etmenin bir tarifi olamaz, bu yüzden de “Bir Turing makinesi durur mu?” sorusu bir karar verilemez problemdir.
Durma probleminin karar verilemez olması, bir Turing makinesinin durup durmayacağının hiçbir zaman bilinemeyeceği anlamına gelmez. Örneğin makineye verilen tek komut “Okuduğun veriyi sil ve dur” ise makinenin ilk okuduğu veriden sonra duracağı açıktır. Ya da makineye verilen tek komut “Sıfır yaz ve bir birim sağa kay” ise makinenin sonsuz uzunluktaki bant üzerinde hiç durmadan sürekli sıfır yazarak ilerleyeceği açıktır.
Makinenin durup durmayacağını belirlemenin tek yolu makineyi çalıştırıp beklemektir. Turing sadece bir tarife uyarak çözülemeyen karar problemleri olduğunu tespit etmişti. Böylece Hilbert’ın problemini de çözmüştü: Matematik sadece birtakım tariflere uymaya indirgenemez.
Bu sonuç 20. yüzyıl matematiğinin en büyük başarılarından biriydi. Tek başına bu bile Turing isminin matematikçiler arasında ölümsüzleşmesini garantilerken, ispatının bir de yan ürünü olmuştu. Bu da genel amaçlı bir problem çözme makinesinin, Evrensel Turing Makinesi’nin icadı idi.
Kaynaklar ve İleri Okumalar:
- Up and Atom/Why This Problem is IMPOSSIBLE for Computers to Solve (The Halting Problem): https://www.youtube.com/
- Computers, maths and minds; Yayınlanma tarihi: 4 Şubat 2014; Bağlantı: https://plus.maths.org/
- Lucas, Salvador. (2021). The origins of the halting problem. Journal of Logical and Algebraic Methods in Programming. 121. 100687. 10.1016/j.jlamp.2021.100687.
Matematiksel
