Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde özellikle özdevinirliler kuramında (automata theory) geçen bir makine modelidir. Yapı olarak Turing makinesine (Turing machine) çok benzer hatta ufak farklılıklar dışında neredeyse aynı olduğu söylenebilir. Turing makinesini geliştiren Alan Turing ile bağımsız olarak geliştirilmiştir. Bu anlamda Post makinesi bazı kaynaklarda Post-Turing makinesi (Post Turing Machine) olarak da geçmektedir.
Turing makinesinde kullanılan bant mantığına benzer bir şekilde, Post makinesinde de kutular bulunmaktadır. İki yöne doğru sonsuz sayıda kutunun bulunduğu bir üretim bandı gibi düşünülebilir. Yani kutulara erişim ardışıktır (sequential) ve kutular ileri veya geri olmak üzere iki yönde hareket edebilir. Post makinesi burada sanki bir çalışanın üretim bandındaki kutular üzerinden çalıştığı kabulü ile yola çıkar.
Post makinesinde, başlangıç durumunda sonsuz kutu bulunmakta ancak bunların sonlu bir kısmı işaretli, geri kalan sonsuz kısmı ise işaretsiz kabul edilmektedir. Yani başlangıç durumunda makinemizin hafızasında bir bilgi olmasını istiyorsak, bu bilgiyi kutulara işaretliyoruz. Geri kalan kutular ise işaretsiz oluyorlar.
Post makinesi, aynı anda tek bir kutuya erişim sağlayabilir. Buna göre kutulara aşağıdaki işlemler uygulanabilir:
- Boş olan bir kutu işaretlenebilir
- İşaretli olan bir kutu silinerek işaretsiz hale getirilebilir.
- Sağdaki kutuya geçilebilir
- Soldaki kutuya geçilebilir
- Şu anda bakılan kutunun işareti okunabilir.
Post makinesinin kendisine özel yazım kuralları bulunmaktadır (notation). Herhangi bir adımda ( bu adıma örnek için i diyelim), herhangi bir işlem (operation) yukarıdaki adımlardan birini parametre almaktadır. Örneğin Oi [3] şeklindeki yazım, i. adımda makinemizin sağdaki kutuya geçeceği şeklinde okunabilir. Ayrıca makinemizin yukarıdaki işlemlerden 5ncisini işletmesi durumunda sonraki adımlarda çatallanma olur. Yani okunan değerin işaretli veya işaretsiz oluşuna göre makinemiz farklı davranabilir. Bunun dışındaki işlemler bir akış şeklinde sonraki adıma geçer.
Yukarıdaki ilk modele ilave olarak zaman içinde yapılan ilaveler ile birlikte bugün Post-Turing makinesi olarak anılan makine aşağıdaki 7 işlemi yapabilmektedir.
PRINT 1 | 1 yaz
PRINT 0 | 0 yaz
GO RIGHT | sağa git
GO LEFT | sola git
GO TO STEP i IF 1 IS SCANNED | şayet 1 okursan i. adıma git
GO TO STEP i IF 0 IS SCANNED | şayet 2 okursan i. adıma git
STOP | bitir
Yukarıdaki son haliyle, post makinesi, Turing makinesinin yapabildiği işlemleri yapabilecek seviyeye ulaşmış olur. Yukarıdaki örnek ikilik tabanda (binary) bir makine olup, dilenirse sembol tablosu genişletilerek daha farklı işaretleri kutulara yerleştirmesi de sağlanabilir.