Turing makinesi

Karmaşık matematiksel hesapların belirli bir düzenek tarafından yapılıp yapılamayacağı 20.yy’ın başlarında büyük bir tartışma konusu olmuştu. Öteden beri el ile veya zihinden yapılan hesaplamalar çok zaman almakla birlikte, birçok hatayı da beraberinde getiriyordu. Tüm bu tartışmalar sürerken, 1936 yılında, ünlü matematikçi Alan M. Turing "Saptama Problemi Hakkında Bir Uygulamayla Birlikte Hesaplanabilir Sayılar" (İngilizce On computable numbers, with an application to the Entscheidungsproblem) isimli bir makalesini yayınladı. Makalesinde teorik ve matematiksel temellere dayalı sanal bir makineden bahseden Turing, her türlü matematiksel hesabın bu sanal makineyle yapılabileceğini iddia ediyordu. Turing’in 1950 yılında yayınlanan "Hesaplama Mekanizması ve Zeka" (İngilizce Computing Machinery and Intelligence) isimli ikinci makalesi ise, makineler ve zekayla ilgili birçok tartışmalı konuya cevap niteliğindeydi. İşte bu makalelerde sözü geçen sanal makine daha sonraları Turing Makinesi (İngilizce The Turing Machine) olarak isimlendirildi.

Konu başlıkları

1 Organizasyonu 2 Örnek 3 Değişik Turing makineleri 4 İlgili Bağlantılar

Organizasyonu

Bir Turing makinesi, "fiziksel" olarak ÅŸu bileÅŸenlerden oluÅŸur:

• Ä°ki yöne doÄŸru sonsuz uzunlukta bir ÅŸerit
• Åžeridi okumak için bir kafa
• GeçiÅŸ tablosunu ve Turing makinesinin o anki durumunu içeren bir iç mantık

Şeridin üzerindeki hücrelerde muhtelif semboller bulunur:

• B (Ä°ngilizce Blank, yani BoÅŸ) sembolü, o hücrenin boÅŸ olduÄŸunu belirtir. Åžeridin iÅŸimize yaramayacak tüm kısımları bu harfle doldurulmuÅŸtur.
• Turing makinesinin ÅŸeridi okuyup anlayabilmesi için gerekli diÄŸer semboller. ÖrneÄŸin, alfabedeki harfler.

Kafa, dört adet işlem yapabilir:

• O anda ÅŸeridin o hücresindeki sembolü okuyabilir
• OlduÄŸu yere yeni bir sembol yazabilir
• SaÄŸa gidebilir
• Sola gidebilir

Son olarak, en önemli kısım: geçiş tablosu. Bu tablodaki her girdi dört elemanlıdır:

• O anki durum
• O anda kafanın okuduÄŸu sembol
• Yazılacak sembol veya yapılacak kafa hareketi
• Yeni durum

Bu tablo, o Turing makinesinin çalıştırdığı algoritmadır. Turing makinesi, her adımda:

• O anda kafanın görmekte olduÄŸu sembolü okur.
• GeçiÅŸ tablosunda okuduÄŸu sembol ve o anki durumunu içeren bir girdi arar:
  • EÄŸer öyle bir girdi bulursa, yazılacak sembolü yazar veya kafasını hareket ettirir ve yeni duruma geçer. Makine, yeni durum ve kafanın okuduÄŸu yeni sembol ile çalışmaya devam edecektir.
  • EÄŸer öyle bir girdi bulamaz ise, durur.

Şeritte ilk başta yazılı olan sembol dizisi Turing makinesine verilen giriş (sorulan soru), Turing makinesi durduğunda şeritte yazılan sembol dizisi ise Turing makinesinin çıktısıdır (yani sorunun cevabı). Bazı Turing makineleri hiçbir zaman durmayabilirler.

Örnek

Örneğimizdeki Turing makinesi sembol havuzu (yani alfabe) olarak {'B', '1'} kullanmaktadır. Bu makineni amacı, verilen girdinin en sağına 1 ekleyip girdinin en soluna geri dönmektir.

Bu amaca ulaşabilmek için, {'d0', 'd1', 'd2'} şeklinde üç durum kullanacağız. Bu durumların geçiş tablosu ise şu şekilde olacak:

Makine, ilk başta d0 durumunda olacak. Bu tabloya bakarak görebiliriz ki, d2 son durum olacak ve makinenin kafası şu işlemi yapacak:

• 1 sembolünü gördükçe saÄŸa doÄŸru gidecek.
• B sembolünü gördüğü an (yani girdinin en sağına ulaÅŸtığında) o sembol yerine 1 yazacak.
• Yazma iÅŸlemi bitince 1 sembolü gördükçe sola gidecek.
• B sembolünü gördüğü an (yani girdinin en soluna ulaÅŸtığında) bir adım saÄŸa gidecek ki girdinin ilk harfine doÄŸru bakıyor olsun.

Birkaç denemeyle bu makinenin istediğimiz işlemi yaptığını görebiliriz.

DeÄŸiÅŸik Turing makineleri

Anlatılan Turing makinesi, yapılabilecek en basit makinedir. Bunu şu şekilde geliştirebiliriz:

• BeÅŸ girdili geçiÅŸ tablolu Turing makinesi: bu makine, bir sembol okuyup gerekli iÅŸlemi yaptıktan sonra hem yeni bir sembol yazıp hem de aynı anda kafasının yerini deÄŸiÅŸtirebilir.
• Birkaç ÅŸerit okuyuculu Turing makinesi: bu makine, birkaç ÅŸeride aynı anda okuyup yazabildiÄŸi için paralel iÅŸlem yapabilir.

Buna ek olarak, anlatılan Turing makinesi belirlenimci (determinist) bir makinedir, başka bir deyişle aynı girdi için her zaman aynı çıktıyı üretir:

• Belirlenimsiz Turing makinesi (Ä°ngilizce Non Deterministic Turing machine), çalışmaya baÅŸlamadan önce ÅŸeride rastgele bir sembol dizisi yazar, bu aÅŸamaya tahmin etme aÅŸaması (Ä°ngilizce guessing stage) denir. NP problem grubunun tanımı bu makine ile yapılabilir.
• Kahinli Turing makinesi (Ä°ngilizce Oracle Turing machine), deminki donanımlara ek olarak bir kahin içerir. Turing makinesi, bu kahine bir soru sorabilir, kahin de bu soruyu cevaplayacaktır. NP complete problem indirgemesi bu makine ile yapılabilir.

İlgili Bağlantılar

• Turing'in adı geçen makalesinin taranmış orijinali