Turing Makinesi Nedir?

Turing makinası matematiksel bir probleme yön verebilme düşüncesinden türemiştir. Fiziksel bir makina olarak değil, soyut, matematiksel bir makina olarak tasarlanmıştır. Tasarlanmasına yol açan problemi ortaya atan David Hilbert’tir.

Hilbert 1900 yılından Paris Uluslararası Matematikçiler Kongresinde matematikte çözülmesi gereken 23 problem belirler. Bu problemlerden 10.su “Entscheidungsproblem” (Karar verme problemi) adıyla anılan problemdir. Problem şudur:

“Genel bir matematik probleminin çözümü için algoritmik bir yöntem bulunur mu, bulunmaz mı? Hâlihazırda bulunmasa bile ilkesel olarak böyle bir yöntem bunabilir mi?”

Problemi başka türlü bir yorumu matematikte tüm problemleri birbiri ardı sıra çözebilecek bir mekanik yöntem mümkün müdür? İşte Turing makinası bu yöntemle ilgilidir.

Alan Turing kendi makinasına “a-machine” yani “automatic machine” adını verir. Bugünkü bilgisayarların atası bu tasarımsal cihazdır. Turing söz konusu tasarısı aracılığıyla hesaplayabilmenin (computation) sınırlarını anlamak ister. Makinanın sonlu sayıda içsel durumu olmasına karşın sınırsız bir girdiyle işlem yapabilme olanağı bulunur.

Turing, makinasını son derece basit bir düzenek biçiminde düzenler. Sınırsız bir şerit, bu şeridi okuyup-yazabilen bir kafa ve kafada sınırsız bellek kapasitesi tasarlar. Şerit bölünmüş karelerden oluşur. Karelerde yalnızca bir simge bulunur. Makina bir algoritmayı çalıştırır. Algoritma şeritlerde bulunan bölünmüş karelerdeki simgeleri(girdileri) okuma ve yazmayı düzenler. Aşağıda bir örneğini görebileceğiniz makina, her adımda okuma yazma kafasında bulunan simgeyi okur.

Her karenin üzerinde bir simge yer alır. Makina bu simgeye “taranmış simge”der. Makina bulduğu taranmış simgeyi belirli bir davranışla değerlendirir. Algoritmasına uygun olarak simgeyi değiştirilebilir ve bir sonraki taranmış simgeye geçer. Genel olarak bir Turing makinasında yapılan temel işlemleri şöyle sıralayabiliriz:

1. Kafanın altındaki simgeyi okuma
2. Kafanın altındaki kareye bir simge yazma
3. Bandı bir kare sola kaydırma
4. Bandı bir kare sağa kaydırma
5. Durumu değiştirme
6. Sonlanma (Halting)

Turing makinesinin nasıl çalıştığını basit bir örnek ile gösterelim. İşlemimiz herhangi bir sayıdan bir çıkarma olsun. İşlemi basit olarak göstermek için, sayıların şerit üzerinde birli sistem (unary system) ile gösterildiğini varsayalım. Birli sistemde herhangi bir sayı, ardışık birlerin toplam sayısı ile ifade edilir. Örneğin, 4, 00001111000 ile 6 ise 00000111111000 ile gösterilir.

Başlangıç durumunda kafanın 1’lerin solundaki herhangi bir 0 üzerinde olduğunu ve başlangıç durumununsa A olduğunu varsayalım. Amacımıza şu yöntemi izleyerek ulaşabiliriz. A durumunda, 0 okuduğumuz sürece, karelerin içeriğini değiştirmeden sağa doğru hareket edelim. A durumunda 1 okuduğumuz anda, durumu B’ye değiştirip, yine karelerin içeriğini değiştirmeden sağa doğru 1 okudukça hareket edelim. B durumunda ilk 0 okunduğunda, bir kare geriye gidip içeriğini 0 yapıp programı sonlandırırsak amacımıza ulaşmış oluruz. Bu işlemleri biçimsel bir dille yazmak gerekirse;

Eğer durum A ve okunan 0 ise A’da kal, 0 yaz ve sağa hareket et
Eğer durum A ve okunan 1 ise B’ye geç, 1 yaz ve sağa hareket et
Eğer durum B ve okunan 1 ise B’de kal, 1 yaz ve sağa hareket et
Eğer durum B ve okunan 0 ise B’de kal, sola geç ve 0 yaz ve sonlandır.

Turing makinası görülen basit örneğin yanı sıra milyonlarca karmaşık işlemi de yapabilir.

Hazırlayan: Sosyolog Ömer YILDIRIM