Turing makinesi
Turing makinesi (İngilizce: Turing machine) 1936 yılında Alan Turing tarafından ortaya atılan bir hesaplama modeli. Hipotetik olarak üzerinde yazma/okuma yapılabilen sonsuz uzunlukta hayali bir banttan, bandın üzerinde bu işlemleri gerçekleştiren bir kafadan ve kafanın hareketlerini mantıksal önermelerle kontrol eden bir durum makinesinden oluşur. Bulunuşundan itibaren hesaplama ve biçimsel dil teorisinde geniş bir yer kaplamış, hesaplama problemleri ve biçimsel gramerler bir Turing makinesi tarafından tanınma ve karar verilme durumlarına göre sınıflandırılmaya başlanmıştır.
Tarihçe
[değiştir | kaynağı değiştir]Karmaşık hesapların belirli bir düzenek tarafından yapılıp yapılamayacağı, 20. yüzyılın başlarında büyük bir tartışma konusu olmuştu. Tüm bu tartışmalar sürerken, 1936 yılında, ünlü matematikçi Alan M. Turing "Entscheidungsproblem Hakkında Bir Uygulamayla Birlikte Hesaplanabilir Sayılar" (İngilizce On computable numbers, with an application to the Entscheidungsproblem) isimli makalesini yayınladı. Makalesinde teorik ve matematiksel temellere dayalı sanal bir makineden bahseden Turing, hesaplanması mümkün olan tüm matematiksel hesapların bu sanal makineyle yapılabileceğini iddia ediyordu. Turing'in 1950 yılında yayınlanan "Hesaplama Mekanizması ve Zeka"[1] (İ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ı bu adla isimlendirildi.
Çalışma prensibi
[değiştir | kaynağı değiştir]Bu tablo, 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.
Örnek
[değiştir | kaynağı değiştir]Örneğimizdeki Turing makinesi sembol havuzu (yani alfabe) olarak {'B', '1'} kullanmaktadır.[2] 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:
| Güncel durum | Okunan simge | İşlem | Yeni durum |
|---|---|---|---|
| d0 | 1 | Sağa git | d0 |
| d0 | B | 1 yaz | d1 |
| d1 | 1 | Sola git | d1 |
| d1 | B | Sağa git | d0 |
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
[değiştir | kaynağı değiştir]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.
- Kâhinli Turing makinesi (İngilizce Oracle Turing machine), anlatılan 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.
Kaynakça
[değiştir | kaynağı değiştir]- ↑ TURING, A. M. (1 Ekim 1950). "I.—COMPUTING MACHINERY AND INTELLIGENCE". Mind. LIX (236): 433-460. doi:10.1093/mind/lix.236.433. ISSN 1460-2113.
- ↑ "Turing Makineleri". Stanford Felsefe Ansiklopedisi. 24 Eylül 2018. 3 Mayıs 1998 tarihinde kaynağından arşivlendi. Erişim tarihi: 20 Şubat 2021.
