Turing Makinesi Nedir? Bu Makinenin Durma Sorunu Neden Çözülemez?

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ır.

Aslında bunu nasıl gerçekleştirdiğini anlamak için öncelikle matematikteki 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. Günümüzde Turing makinesi olarak adlandırılan teorik bir bilgisayar modeli ile bunu gerçekleştirdi.

Turing Makinesi Nedir?

Alan Turing’in bilgisayar biliminin temellerini atarken tanımladığı soyut Turing makinelerinin çalışma ilkesi gayet basittir. Makine sonsuz uzunlukta olduğu varsayılan bir şeridin üzerindeki girdileri okur ve işler, çıktıları da 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 bulunur. Ve bu okumaya verilen tepki, makinenin içinde bulunduğu duruma göre belirlenir.

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.

Sonsuz genişletilebilir bantta görünen sıfırlar ve birler 
semboller olarak adlandırılır ve makinenin kullandığı  alfabeyi oluşturur.

Turing Makinesi Nasıl Çalışır?

Bir Turing makinesinin programını anlamanın ilginç bir yolu, beşli sembol kullanmaktır. Örneğin aşağıda gördüğünüz sembolün anlamı 0 okuyorsanız ve q durumundaysanız, 0’ı 1 ile değiştirin, bir adım sağa gidin ve durumunuzu q’ olarak değiştirin biçimindedir.

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.

Ş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 ve 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 ve 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 kuramsal aygıtı 5 yıl içinde hayata geçirildi ve Z3, Berlin’de 1941’de yapıldı. Alman hükumeti bilgisayarın askeri alandaki potansiyelini fark edemedi ama İngilizler aynı hataya düşmedi. Turing savaş esnasında şifrelerin kırılmasında büyük rol oynayan Colossus bilgisayarları ile çalışmaya başladı. https://en.wikipedia.org/wiki/Z3_(computer)

Bilgisayar bilimindeki temel kavramlardan biri hesaplanabilirliktir. En genel anlamıyla bir soruyu çözebilme yetisini ifade eder. Alan Turing, 1936 yılında hesaplanabilirlikle ilgili temel bir sorunun “karar verilemez” olduğunu ispatladı. “Durma problemi” olarak adlandırılan bu problem, herhangi bir girdiyi işleyen herhangi bir bilgisayar programının eninde sorunda durup durmayacağını söyleyecek genel bir algoritma olup olmadığını sorar.

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? Alan Turing durma probleminin karar verilemez olduğunu, yani herhangi bir iş için üretilmiş bir Turing makinesine herhangi bir girdi verildiğinde makinenin eninde sonunda durup durmayacağını söyleyebilecek genel bir algoritma olmadığını ispatladı.

Durma Probleminin Karar Verilemez Olması Ne Anlama Gelir?

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.

Ancak Turing’in ispatı makinenin durup durmayacağına karar verebilecek genel bir algoritma olmadığını söyler. Başka bir deyişle makinenin durup durmayacağını belirlemenin tek yolu makineyi çalıştırıp beklemektir. Eğer makine bir noktada durup size cevabı verirse durduğunu bilirsiniz. Ancak bir süre önce çalıştırdığınız makine hâlâ verileri işleyip çalışmaya devam ediyorsa bir süre sonra durup durmayacağını kesin olarak söyleyemezsiniz. Dolayısıyla durma problemi “karar verilemez” ya da “hesaplanamaz”dır.



Kaynaklar ve İleri Okumalar:

Matematiksel

Sibel Çağlar

Merhabalar. Matematik öğretmeni olarak başladığım hayatıma 2016 yılında kurduğum matematiksel.org web sitesinde içerikler üreterek devam ediyorum. Matematiğin aydınlık yüzünü paylaşıyorum. Amacım matematiğin hayattan kopuk olmadığını kanıtlamaktı. Devamında ekip arkadaşlarımın da dahil olması ile kocaman bir aile olduk. Amacımıza da kısmen ulaştık. Yolumuz daha uzun ama kesinlikle çok keyifli.

Bu Yazılarımıza da Bakmanızı Öneririz