Turing Machine

İlkel ve soyut bir bilgisayar olarak düşünülebilir. Matematiksel fonksiyonların hesaplanabilirliği üzerinde çalışan Alan Turing isimli bilim adamı tarafından icat edilmiş. İcat diyorum ama aslında yok böyle bir alet. Sadece hayali bir makine.

Hipotez şu: Turing makinesi ile hesaplanabilen bir fonksiyon hesaplanabilirdir. 🙂

Peki turing makinesi nasıl bir şey, nasıl çalışıyor? Bir teyp kasetinin şeridinin [a] [b] [c] .. [x] şeklinde hücrelerden oluştuğunu ve teyp kafasının bu hücrelerde x ile belirtilen sembolleri ileri ve geri giderek okuyabildiğini, değiştirebildiğini düşünün. Bu kafa ve şeritten oluşan bir makine tam olarak turing makinesine eşdeğerdir. Bu makine sınırlı sayıdaki sembol üzerinde çalışır ve sınırlı sayıda durum * oluşur. Bu durumları ve sembolleri bir sonraki durumla eşleştiren geçiş tabloları kullanılarak teyp kafasının bir sonraki konumu tesbit edilir.

Yani adım adım şöyle çalışır:

1. Makinemiz teyp kafasının altındaki sembolü okur.

2. Bir sonraki adım için şu anki durumu ve sembolü kullanarak geçiş tablosuna bakar. Ve şunları öğrenir: Sonraki durum, sonraki sembol ve bir sonraki hareket (ileri ya da geri). (Öğrenemezse patlar.)

3. Durumunu geçiş tablosundan öğrendiği yeni durum ile değiştirir.

4. Geçiş tablosundan öğrendiği sembolü bulunduğu konumuna yazar.

5. Geçiş tablosunun söylediği konuma (ileri yada geri) ilerler.

6. Eğer durumu bitiş durumu (halt state) ise durur. Aksi takdirde goto 1.

Burada önemli olan konu geçiş tablosunu (ya da fonksiyonunu) yazmaktır. Zor olan işin bu kısmıdır. Örneğin şerit üzerindeki sembolleri ters çevirmek ya da sembollerin palindrom olup olmadığını hesaplayan fonksiyon yazmak gibi problemler baya zordur.

Güzel bir simülasyon için : http://ironphoenix.org/tril/tm/