turing makinesi

Bilgisayar kavramı, 19. yüzyılda, Charles Babbageın ortaya attığı programlanabilir makine fikriyle doğdu. Babbageın analitik makine adını verdiği, delikli kartlarla programlanabilen tasarımı ilk bilgisayar tasarımı sayılmalıdır. Çünkü bu tasarım ilk kez, makine denilen kavramın sabit bir işlevle sınırlı kalmayıp, programlanabilir olmasını öngörüyordu. Ancak halen teorik ve pratik bazı problemler vardı. Makinenin yapabileceği işlemler fiziksel yapısıyla sınırlıydı. Veriler ve programlar aynı düzeyde işlenemiyordu. Matematikçilerin bu işe de el atıp, mühendislerin sınırlı ufkunu genişletmeleri için bir süre daha geçmesi gerekiyordu. 20. yüzyılda, ikinci Dünya Savaşında Almanların Enigmasını çözen ingiliz matematikçi Alan Turing bu işe girişti. Turing yayınladığı makalelerle bize kuramsal bilgisayarları tanıtıyordu. Bu, Hesaplama (Computing) diye bir alanın doğduğunun, hatta bilgisayarın, henüz ortada tam anlamıyla bir örneği olmasa da, bilimdeki yerini aldığının da göstergesiydi.

Turing, kendi adıyla anılan Turing Makinesi(TM) kavramıyla, hesaplanabilir olan her şeyin programlanmasına izin veren soyut bir mekanizma üretmişti. Hesaplanabilirlik meselesi, Kurt Gödelin şaşırtıcı ispatıyla matematikçilerin aklını karıştıran, derinliği olan bir konudur. Özetle Gödel, matematikteki bütün problemlerin programlanamayacağını yani hesaplanabilir olmadığını kanıtlamıştır.

Peki bu makine nasıl bir şeydi? Öncelikle makine desek de, yani aklımızda somut bir prototip canlansa da, sözü edilenin tümüyle matematiksel ve teorik bir kurgu olduğunu bilmemiz gerekir. Fakat bu durum, TMnin somut olarak gerçekleştirilemeyeceği anlamına da gelmez. Bir TM, teorik olarak sonsuz uzunlukta olduğu kabul edilen bir bant, bandın üstünde sağa ve sola kayabilen bir okuma-yazma kafası ve bir de karar ünitesinden oluşur. Karar ünitesi TMnin programlandığı kısımdır. Ünite, bant üzerinde hareket eden okuma-yazma kafasının okuduğu sembole göre, kafanın bant üzerine belli bir sembolü yazmasını sağlayabilir, okuma-yazma kafasını sağa veya sola kaydırabilir ve içsel duruma herhangi bir değeri atayabilir. Ünitenin hangi sembolü okuduğunda neyi yapması gerektiğini söyleyen komut listesine program denir. Aslında ünite daima aynı, ilkel işlemleri yapmaktadır: Sağa veya sola hareket, banttan sembol okuma ya da banda sembol yazma ve içsel durumu değiştirme.

TM, sembollerle ifade edilebilen ve hesaplanabilen her şeyi, uygun bir programla gerçekleştirebilir. Peki, toplam beş basit işlemle bu kadar sınırsız bir hesaplama kabiliyetine nasıl ulaşılmıştır? işte programlamanın sırrı da tam bu sorunun cevabında gizlidir. Programlama, karmaşık, üst düzey işlemlerin, çoğu kez birbirini tekrar eden, çok sayıda basit adımla gerçekleştirilmesidir.