Turing Makinesi

Turing Makinesi, karmaşık bir makineyi tanımlayan  hesaplamalı matematiksel modeldir. Bu makine belirli ve sayılı kurallar dahilinde kaset şeridi üzerindeki sembolleri manipüle eder.

Turing Makinesi sonsuz hafıza kaset şeridi üzerinde bulunan kesitli hücreler üzerinde işlem yapar. Makinenin baş kısmı (bir çeşit merkezi işlemci => CPU) o anda hücre üzerinde bulunan sembolü okur (veya tarar). Daha sonra o sembolu sınırlı sayıdaki kurala göre manipüle eder. Makine, önce hücreye sembol (ör. rakam veya harf) yazar. (NOT. bazı modeller sadece hücrelere yazabilirken bazılariı ek olarak silme işlemi yapabilir.) Daha sonra kaset seridi sola veya saga doğru hareket eder ( NOT . bazı modellerde şerit hareket etmez ve makinenin baş kısmı hareket edebilir.). Sonra, gözlenen sembol ve makinenin durum tablosundaki (state table) o anda sahip oldugu duruma göre sembol manipülasyonu yapılır veya işlem sonlandırılır.

Basitleştirmek gerekirse, Turing Makinesi, veri (data) manipülasyonunun bir bilgisayar tarafından yapıldıgı ve verinin depolandığı seri hafıza modelinin kullanıldığı bir CPU genel örnegi sayılabilir.

Turing Makinesinin fiziksel yapısını betimlemek için Alan Turing’in 1948 yılında yayınladığı “Computing Machinery and Intelligence” isimli makalesine göz atabiliriz. Bu makalede, Turing Makinesinin fiziksel yapısı ile ilgili şu betimleme yapılmıştır. Sınırsız hafıza kapasitesine sahip bir sınırsız kaset şeridi karelere (hücrelere) ayrılmıştır. Her bir kareye bir sembol yazılabilir. Her bir an için makinede bir sembol bulunur, bu sembol makine tarafından taranmıştır. Makine taranan sembolü değiştirebilir ve karelerdeki sembol değişimi makinenin davranışını (çıktı->output) etkileyecektir; ancak taranmayan semboller makinenin davranışını etkilemez. Makinedeki kaset şeridi ileri veya geriye doğru hareket ettirilebilir. Bu, makinenin yapabildiği temel işlemlerden birisidir. Kaset şeridindeki herhangi bir sembol için bir işlem sırası olacaktır (seri işlemleme).

Daha detaylı olarak Turing Makinesinin bileşenleri ve özellikleri aşağıda verilmiştir:

• Kaset Şeridi: Hücrelere ayrılmış bir şeritler birbiri ardınadır. Her bir hücre, alfabede bulunan (sınırlı sayıda sembol) bir harf bulundurur. Şeridin isteğe baglı olarak sağa veya sola hareket ettirilebileceği varsayılır. Turing Makinesine her zaman işlemleme için gerekli şerit saglanır (Yani teorik olarak sınırsız bant şeridi vardır).
• Makinenin baş kısmı: Makinenin baş kısmı şeritteki sembolleri okuyabilir veya şeride sembol yazabilir ve şeridi saga veya sola doğru her seferinde bir hücre olacak şekilde hareket ettirebilir. Bazı modellerde baş kısmı hareket ederken şerit sabit kalır. Baş kısmının gerçekleştireceği işlem 2 duruma bağlıdır: İlki hangi sembolün mevcut hafıza kısmında  kayıtlı olduğu ve tarayıcının (baş kısmının) o anki bulunduğu makine durumu. 
• Bir makine tablosu (machine table) makinenin mevcut durumu ve o anda eriştiği sembole bağlı olarak makinenin baş kısmının (merkezi işlemcinin (CPU) ) hangi temel işlemi gerçekleştireceğini belirtir. Ayrıca, makine tablosu merkezi işlemcinin maknine durumunun aynı faktörler içerisinde nasıl çıktı verebileceğini belirtir. Yani, makine tablosu hesaplama işlemini yönlendiren sınırlı sayıda mekanik talimat bulundurur.
• Durum kaydedicisi: Bir durum kaydedicisi, bir çok makine durumundan (machine state) bir tanesini kaydeder. Bu durumlar içerisinde durumun kaydedilmesini belirten bir özel başlama durumu vardır. Turing’e göre bu durumlar, hesaplama yapan bir kişinin günlük yaşamda sahip olabileceği “zihin durumuna (mind state)” benzerdir.
• Makinenin her bir bölümü (durumlar, sembol listeleri ve kullanılan kaset şeritleri vs.) ve makinenin her bir işlemi (silme, yazma, şerit hareketi vs.) sınırlı sayıdadır, ayrıktır (discrete) ve benzersizdir. Makine, sınırsız sayıda kaset şeridi, yürütme zamanı ve sınırsız saklama alanına sahiptir (Yani elimizdeki PC’leri zorlayan işlemlere sokunca gerçekleşen yüksek CPU kullanımı ve yetersiz hafıza sorunu (Memory exhaustion ) olmadığı varsayılır).

Turing makinesine ek olarak, Alan Turing 1936 yılında evrensel Turing makinesi (UTM) var olabileceğini ispatlamıştır. Kısaca, bir Turing makinesi çeşidi olan UTM, diğer Turing makinelerini taklit edebilir. UTM’ye uygun olacak şekilde başka bir Turing Makinesi (M) bir makine tablosunu kodlayan sembolik girdi girişi yaptıktan sonra (yani talimatları içeren bir program yazarsa ), UTM, M’in davranışını taklit eder yani, M tarafından kaydedilen makine tablosundaki talimatları yürütür. Bu anlamda, UTM bir programlanabilir Genel Amaçlı Bilgisayardır. Sezgisel olarak, tüm PC’lerin (kişisel bilgisayarların) UTM olduğunu söyleyebiliriz. PC’ler de UTM’ler gibi uygun programlandığı zaman başka Turing Makinelerinde kaydedilen makine tablolarını (programları) yürütebilir. Buradaki can alıcı nokta, fiziksel bilgisayarların limitli hafızası bulunurken bir Turing makinesinin sınırsız hafızası vardır. Daha doğrusu, bir PC herhangi bir Turing Makinesini (M) limitli hafıza deposu tükenene kadar taklit edebilir.  

Alan Turing’in Turing Makinesi modellemesindeki amacı, insanın gerçekleştirdiği zihinsel işlemleri (düşünme gibi) hesaplama araçlarına indirgenebileceğini göstermekti. İnsanın bilişsel ve algısal aygıtındaki sınırları göz önünde bulundurarak, insanların yapabilecegi zihinsel işlemlemenin uygun bir Turing Makinesi tarafından taklit edilebileceğini savunmuştu. Turing, Turing Makinelerinin aşırı basitleştirilmiş yapıya sahip olmasına rağmen semboller üzerinde mekaniksel işlemler uygulama benzetimiyle, insanların tüm zihinsel işlemlemelerini yansıtabilecek şekilde kadar güçlü bir model oldugunu savunmuştur.

Bir dönem yaygın olarak kullanılan “Turing Makinesi olarak zihin ya da zihnimiz de bir çeşit Turing Makinesidir” yaklaşımı aşağıdaki sebeplerden ötürü uygun bir benzetim değildir:

• Turing makineleri saf sembolik hesaplama, programlama işlemleri yürütür. Girdiler ve çıktılar hafıza bölgelerinde kayıtlı sembollerdir. Ancak bir insan zihni girdi olarak duyusal uyarımlar (ör. retinal uyarımlar) alır ve motor çıktılar (ör. motor aktivasyon) üretir. Eğer kapsayıcı bir teori üretilmek isteniyorsa duyusal girdiler ve motor çıktıları da dahil edecek zihinsel hesaplama formülasyonu olmalıdır.
• Bir Turing Makinesi sınırsız ve ayrık hafıza kapasitesine sahiptir. Herhangi bir biyolojik sistemin ise sınırlı hafıza kapasitesi vardır. Uygun bir psikolojik model oluşturulacaksa sınırsız hafıza yapısı, sınırlı hafıza ile yer değiştirmelidir.
• Modern bilgisayarlar RAM’e (rastgele erişim belleği) sahiptir. Bu sayede ilgili hafıza bölgelerine merkezi işlemci doğrudan erişebilir. Turing Makinesinde ise hafıza bölgelerine doğrudan erişim yoktur; çünkü merkezi işlemci bir bölgeye yalnızca ara bölgelere sırayla eriştikten sonra erişebilir. Tahmin edilebileceği üzere doğrudan erişilemeyen bellek verimli değildir. Bu sebeple C.R. Gallistel ve Adam King (2009) doğrudan erişilebilen belleğin doğrudan erişilemeyen belleğe göre daha iyi bir zihin modeli verebileceğini savunmuştur.
• Bir Turing makinesi seri olarak işlemleme yapan bir merkezi işlemciye sahiptir. Yani birim vakitte bir işlemleme gerçekleştirir. Paralel işlemlemede ise merkezi işlemci birim vakitte birden fazla işlem gerçekleştirir.
• Turing Makinesi işlemlemeleri deterministtir. Yani, bir makine durumundan bir sonraki makine durumu belirlenebilir. Ama stokastik (olasılık) hesaplama modelinde,  mevcut durum benzersiz olan bir sonraki durumu kesin bir şekilde belirlemez. Bunun yerine makinenin  bir durumdan diğerine geçmesi belli bir olasılık değeri dahil edilerek gerçekleşir.

Kaynaklar ve İleri Okumalar

• Turing Machine
• The Computational Theory of Mind
• Gödel, K., 1936/65. “On Formally Undecidable Propositions of Principia Mathematica and Related Systems”, Reprinted with a new Postscript in The Undecidable, M. Davis (ed.), New York: Raven Press Books.
• Turing, A., 1950, “Computing Machinery and Intelligence”, Mind, 49: 433–460.
• Marvin L. Minsky. 1967. Computation: finite and infinite machines. Prentice-Hall, Inc., USA.
• https://en.wikipedia.org/wiki/Turing_machine

BURAK BÜYÜKYAPRAK

CEO