Mühendislik ve Teknoloji

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.

alan turing
Alan Mathison Turing, (1912-1954) İngiliz matematikçi, bilgisayar bilimcisi ve kriptolog. Alan Turing 1936-1938 yılları arasında Princeton Üniversitesi’nde doktora yaptı. Burada matematik ve kriptoloji üzerine çalıştı. 1938 yılında II. Dünya Savaşının göbeğindeki İngiltere’ye geri döndü ve hükümetin kod ve şifreleme bölümünde çalışmaya başladı. Enigma kodunu inceleyen Turing ve matematikçi Gordon Welchman “Bombe” adını verdikleri bir elektromekanik makine icat etti. Turing’in bu icadı sayesinde Dünya savaşının iki yıl kısaldığı kabul edilmektedir. Detayları bu yazıda inceleyebilirsiniz: Alan Turing Matematik Yardımıyla Enigma Kodunu Nasıl Kırdı?

Turing Makinesi Nedir?

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.

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

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.

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. 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 Nedir? Bu Makinenin Durma Sorunu Neden Çözülemez?
Sonsuz bir bantta görünen sıfırlar ve birler semboller olarak adlandırılmaktadır. Bu semboller 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 Makinesi Nedir? Bu Makinenin Durma Sorunu Neden Çözülemez?
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:


Size Bir Mesajımız Var!

Matematiksel, 2015 yılından beri yayında olan ve Türkiye’de matematiğe karşı duyulan önyargıyı azaltmak ve ilgiyi arttırmak amacıyla kurulmuş bir platformdur. Sitemizde, öncelikli olarak matematik ile ilgili yazılar yer almaktadır. Ancak bilimin bütünsel yapısı itibari ile diğer bilim dalları ile ilgili konular da ilerleyen yıllarda sitemize dahil edilmiştir. Bu sitenin tek kazancı sizlere göstermek zorunda kaldığımız reklamlardır. Yüksek okunurluk düzeyine sahip bir web sitesi barındırmak ne yazık ki günümüzde oldukça masraflıdır. Bu konuda bizi anlayacağınızı umuyoruz. Ayrıca yazımızı paylaşarak veya Patreon üzerinden ufak bir bağış yaparak da büyümemize destek olabilirsiniz. Matematik ile kalalım, bilim ile kalalım.

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.

Bir yanıt yazın

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Başa dön tuşu