Turing makineleri açıklandı
1936'da, elektronik bilgisayarlar henüz yokken, 24 yaşındaki matematikçi Alan Turing bir hesaplamanın mekanik olmasının ne anlama geldiğini sordu. Yanıtı, bundan azını yapması neredeyse imkânsız olacak kadar basit, hayali bir makineydi: sabit bir kural tablosuna göre, bir bant üzerinde her seferinde bir hücre olmak üzere semboller okur ve yazar. Bu makinenin hesaplamanın kendisini tanımladığı ortaya çıktı ve bazı soruların hiçbir bilgisayar tarafından asla yanıtlanamayacağını gösterdi.
Turing'in sorusu
1928'de David Hilbert, matematiğin her önermesi için kanıtlanıp kanıtlanamayacağına karar veren mekanik bir yöntem olup olmadığını sordu: Entscheidungsproblem. Bunu yanıtlamak için birinin mekanik bir yöntemin tam olarak ne olduğunu söylemesi gerekiyordu. Turing 1936 tarihli On Computable Numbers makalesinde kalem ve kâğıtla çalışan bir memur hayal etti ve işi en küçük adımlarına indirdi: bir sembole bak, onu değiştir, komşu bir sembole geç ve ne yaptığına dair biraz şey hatırla. Sonuç Turing makinesiydi.
Makine
Bir Turing makinesinin hücrelere bölünmüş, her iki yönde sonsuz bir bandı vardır; her hücre, genellikle boş olan bir sembol taşır. Bir kafa bir hücre üzerinde durur ve makine sonlu sayıdaki durumdan birindedir. Bir kural tablosu, her durum ve kafanın okuyabileceği her sembol için yazılacak sembolü, hareket yönünü ve sonraki durumu verir. Makine her adımda bir kural uygular. Bir durma durumuna girdiğinde durur ve bantta kalan her şey onun yanıtıdır.
Kural tabloları olarak programlar
Her kural tablosu bir programdır. İkili bir sayıya 1 eklemek için makine sayının sağ ucuna yürür, ardından bir 0 ya da boşluk bulana kadar 1'leri 0'a çevirerek sola gider ve bulduğunu 1'e çevirir. Bir kelimenin palindrom olup olmadığını denetlemek için ilk sembolü siler, onu durumunda hatırlar, öbür uca koşar ve son sembolün eşleştiğini denetler, sonra tekrarlar. Çarpma ya da sıralama yapan programlar gibi uzun programlar da aynı birkaç kural türünden kurulur.
Evrensel makine
Turing'in en önemli fikri, kural tablosunun kendisinin de banda yazılabileceğiydi. Evrensel bir Turing makinesi herhangi başka bir makinenin tanımını ve girdisini okur, sonra onu adım adım taklit eder. Böylece tek bir sabit makine her programı çalıştırabilir: yazılımın bellekteki veriden ibaret olduğu her depolanmış program bilgisayarının ardındaki ilke budur. Evrensel bir Turing makinesini taklit edebilen her sisteme Turing-tam denir; her programlama dili, Conway'in Hayat Oyunu ve Kural 110 hücresel otomatı da bunlara dahildir.
Church–Turing tezi
Aynı yıl Alonzo Church hesaplamayı lambda kalkülüsüyle tanımladı ve iki tanımın tam olarak aynı fonksiyonları hesapladığı ortaya çıktı. Yazmaç makinelerinden modern işlemcilere kadar sonraki her model de öyle. Church–Turing tezi, adım adım bir yöntemle hesaplanabilen her şeyin bir Turing makinesiyle hesaplanabileceğini söyler. Kanıtlanamaz, çünkü “adım adım yöntem” resmî olmayan bir kavramdır, ama bugüne kadar hiçbir karşı örnek bulunamadı.
Durma problemi
Turing ardından bazı soruların mekanik bir yanıtı olmadığını gösterdi. Bir makinenin, her program ve girdi için, o programın sonunda durup durmayacağına karar verebildiğini varsayalım. Bu karar vericiye kendisini soran ve sonra tersini yapan yeni bir program kurun: duracağı söylenirse sonsuza dek döngüde kalır, döngüde kalacağı söylenirse durur. Her iki yanıt da yanlıştır, dolayısıyla karar verici var olamaz. Durma problemi karar verilemezdir ve onunla birlikte Entscheidungsproblem de: hiçbir algoritma her matematiksel soruyu çözüme kavuşturamaz.
Meşgul kunduzlar
1962'de Tibor Radó durma problemini bir oyuna dönüştürdü: n durumlu ve 0 ile 1 sembollerini kullanan, boş bir bantta başlatıldığında duran tüm makineler arasında hangisi en çok 1 yazar ve böyle bir makine kaç adım atabilir? Meşgul kunduz değerleri denen bu sayılar hesaplanabilir her fonksiyondan daha hızlı büyür, çünkü onları hesaplamanın bir yolu durma problemini çözerdi. Bilinen değerler iki, üç ve dört durum için 6, 21 ve 107 adımdır; beş durum için Heiner Marxen ve Jürgen Buntrock'un şampiyonu 47.176.870 adım atar; bu değer 2024'te çevrimiçi bbchallenge işbirliği tarafından bilgisayarla doğrulanmış bir ispatla kanıtlandı. Altı durum için, sıradan gösterimle yazılabilecek olandan daha fazla adım çalışan makineler bilinmektedir.
Keşfedin
Sekiz hazır programı çalıştırmak ya da kendinizinkini yazmak için Turing makinesi simülatörünü açın. Kafayı adım adım izleyip hangi kuralın uygulandığını görün, hiç durmayan sayacı izleyin, palindromları denetleyin ve meşgul kunduzları çalıştırın: dört durumlu şampiyonun 107 adımı diyagrama sığar, beş durumlu şampiyonun 47 milyon adımı ise en yüksek hızda birkaç saniye sürer.
Sık sorulan sorular
Turing makinesi hiç inşa edildi mi?
Turing'in tarif ettiği biçimde değil, çünkü bandı sonsuzdur; ama fikri kısa süre sonra gerçek depolanmış program bilgisayarları izledi ve Turing İkinci Dünya Savaşı'ndan sonra bunların tasarımına bizzat yardım etti. O zamandan beri hobiciler ahşaptan, LEGO'dan ve hatta Hayat Oyunu'nda çalışan modeller yaptı; hepsinin bandı sonludur, bu da sona eren her hesaplama için yeterlidir.
Üç durum için 14 ve 21 adım sayıları arasındaki fark nedir?
İki meşgul kunduz sorusu vardır: en çok yazılan 1 ve en çok atılan adım. Üç durum için simülatördeki makine en fazla olan altı tane 1'i 14 adımda yazarken, başka bir üç durumlu makine en fazla olan 21 adımı atar ama yalnızca beş tane 1 bırakır. İki, dört ve beş durum için ikisini de tek bir makine kazanır.
Turing-tam güçlü demek mi?
Yeterli zaman ve bellek verildiğinde hesaplanabilir her şeyi hesaplayabilmek demektir; bu, hız hakkında hiçbir şey söylemez. Bir Turing makinesi basit aritmetik için çok sayıda adıma ihtiyaç duyar ve bazı sistemler neredeyse kazara Turing-tamdır; örneğin kart oyunları, elektronik tablo formülleri ve Minecraft redstone.
Bir bilgisayar, programın durup durmadığını görmek için onu neden çalıştırıp bakamaz?
Çalıştırmak, bir program duruyorsa durduğunu gösterir; ama henüz durmadıysa hiç durmayacak mı yoksa yalnızca daha fazla zamana mı ihtiyacı var, bunu anlayamazsınız. Turing'in ispatı, daha akıllıca hiçbir yöntemin her program için işe yaramadığını gösterir, ancak birçok belirli program için soru yanıtlanabilir.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Turing makinesi simülatörünü açın