Tam bir Turing Kahve Makinasını Oluşturmak

Erkeklerin erkek olduğu ve kendi kahve makinalarını yaptıkları eski günlerin özlemini duyar mısınız?

Bu bölüm akıllı, zeki bir kahve makinası oluşturmakla ilgili olucaktır. von Neuman mimarisinde bir bilgisayar tasarımı olucak, CPU, ROM/RAM ve I/O'dan oluşacak, genel kullanıma açık olacaktır, ki bunlar Turing Makinası olarak da bilinmektedir.

Uygun bir assembly dili

CISC veya RISC gibi diğer popüler sistemlerin tersine, bizim makinamız MISC olacaktır: Mono-Instruction Set Computer!

Ne yazık ki, bizim işlemcimiz sadece bir komut algılayabilecek ve sizin 3GHz Pentium 4 işlemcinizin gerçekleştirdiği herhangi bir eylemi yeterli zaman ve bellek verilirse gerçekleştirebilecek, ya da simüle edecektir; hesaplanabilir bir problemi aşağıdaki gibi kodlar çalıştırarak çözebilecektir:

    SBN     $mem1, $addr1
    SBN     $mem2, $addr2
    SBN     $mem3, $addr3
    SBN     $mem4, $addr4
    SBN     $mem5, $addr5
    SBN     $mem6, $addr6
    [...]

Sihirli SBN $mem, $addr (Subtract and Branch if Negative) komutu, $mem bellek gözündeki veriyi almakta, sayiların tutulduğu akümülatörden bu değeri çıkarmakta (A, bu mimarideki tek yazmaçtır), daha sonra bunu $mem bellek gözünde ve akümülatörde saklamaktadır: [mem] <= A <= A-[mem]. Eğer sonuç negatifse, sadece o zaman, $addr ile belirtilen tasarım adresine dallanmaktadır. Eğer $addr bir sonraki komutu işaret ediyorsa o zaman koşullu bir dallanma yapılmamış olur. Şimdi, elinizdeki bu komutla, çıkarma, toplama, bellek adresini sıfırlama, baytları çevirme, çarpma, kıyaslama ve benzerlerini gerçekleyebilirsiniz. En güzeli ise, optimize edecek bir derleyici tasarlayabilirsiniz.

Bu gerçek bir Turing Makinası problemi için harika bir sistemdir, artı orjinal Turing Makinası'na göre de kodlaması daha kolaydır!

Donanım ve arayüz

Yenilikçi MIPS işlemcinizin en iyi tarafı, komutlarınızın opkod kısımlarını saklamak için 0 bite ihtiyaç duymanızdır. Bu da işlemcinizi çok çok daha basit hale getirir: Her seferinde bir iki değişkeni okumanız gerekecektir. İşlemcinizin yapabildiklerini, SBN komutunun işlediği değişken sayısını 3 veya 4'e çıkararak geliştirmek isteyebilirsiniz, böylece artık doğrudan bellekten veri okuyup, belleğe yazabilecektir. Bu, okuyucuya bırakılan bir denemedir, yüce google'a bir sorun.

İşlemci diyagramı şu şekilde gözükür:

    <========= ADDRESS BUS ==============>
            =                =
            =  +---------+   =
            =  | CONTROL |   =
        +---------+  +-----------------+
        | ALU & A |  | Program Counter |
        +---------+  +-----------------+
            =  |  LOGIC  |   =
            =  +---------+   =
            =                =
    <=========== DATA BUS ===============>

Şimdi tek yapmanız gereken bir kaç bellek çipini bir araya getirmek, mesela eski 386 bilgisayarınızın RAM'ini ve ALU birimini ve biraz da yapıştırıcı kullanabilirsiniz. Anahtar (latch) ve mantık devreleri için TTL veya CMOS kullanabilirsiniz; ben bir CMOS adamıyım, tabii bu tamamen sizin zevkinize kalmıştır. 8, 16, 32, 64 bit veya herhangi bir bitlikte sistemi ihtiyacınıza göre tasarlayabilirsiniz. Çok büyük kelime genişliklerinin olması durumuna karşı, önceden programlanmış bir 27128 EPROMS'u bir ALU ile beraber kullanmayı, bulunması daha zor olan 74x181s'a tercih ederim. Elde bitini (carry propogation bit) de kontrol etmeyi unutmayın.

Bütün bu sistemin doğası sadece girdi/çıktı için bellek adreslemesine izin verir, çift yönlü tasarım için daha özel koşullara ihtiyaç duyari, fakat bu ihtiyaçlar, eski nesil sistemlerden daha acayip değildir. AGC, Apollo 11'i aya gönderen bilgisayardı ve bu tür sistemler kullanmaktaydı, onun için böylesi bir durumda yeterli olmalıdır.

Veri yolunun tam olarak adres yolu kadar geniş olması gerektiğini unutmayınız, ki bu da byte kavramının 8 bitlik kahve makinalarına uygulanabilirliğini ortaya koyuyor ki, bir özellikten çok bir hata olarak anlayacaksınız. 8 veya 16 bitlik yollara sahip bir kahve makinasıyla nasıl kahveler yapabileceğinizi düşündükçe şaşıracaksınız. Bu, basit işler için tasarlanmış, gerçekten de genel amaçlı bir donanımdır.

Yazılım

Böylesi saf bir sistem, gömülü sistem kontrolünde çok ünlü olan FORTH ile çok iyi uyuşacaktır. En temel gereksiniminiz, bir yığın yapısının olmasıdır, bu da bir bellek havuzuna bağlı bir sayaç ile tasarlanabilir.

Eğer gerçekten de ciddi bir kahve geliştirme platformu tasarlamak istiyorsanız, C'nin taşınabilirliği gerçekten de bu zamanlarda bir zorunluluk olmuş durumdadır. Yapabileceklerinizden birisi, gcc, lcc veya sdcc'yi kırarak, özel olarak tasarlanmış MISC kodunda ince ayar yapmaktır. Belki ilerde siz de C diline benzer bir dil yazmak isteyebilirsiniz, D yi kullanmayı düşünmeyin - zaten alındı - bunun için de derleyicinizle aynı hatayı yapmayın ve lütfen şu adrese gidip bilgileri okuyunuz: http://www.gnu.org/software/gcc/projects/beginner.html

Kendi derleyicinizi yazmayı düşünmeniz halinde, flex, yacc ve ilgili konuları okuyunuz. Özellikle, Noam Chomsky'nin diller üzerindeki sınıflandırmasına hayran olacaksınız:

  • Düzenli gramerler (Düzenli ifadelerin (regular expression) soyutlanması)
  • İçerikten bağımsız grameler (BNF açıklamalı herhangi bir dil buna girer)

Şimdilik bu kadar. Hesaplanbilirlik Teorisini okuyarak devam edebilirsiniz.

Turing Makinası üzerine küçük bir eleştiri

Turing Makinası, çalışma şeklinden dolayı (şu linke bakınız bunu için: http://plato.stanford.edu/entries/turing-machine/), programlanması ve gün sonunda da hataların bulunması konusunda oldukça zor bir cihazdır. Bunun sebebi aşağıdaki parametrelere bağımlı, sıralı bir işlem yapısına sahip olmasındandır:

  1. Makinanın bulunduğu durum
  2. Bulunduğu daire içerisinde aradığı sembol ya da sayı, ve
  3. Komut tablosu

Turing Makinasının (TM) en temel çağdaş sorunlarından biri, ardışıl yapısıdır, kendi yapısıyla yalnızca belli tipteki problemleri çözebilirsiniz. TM'ler seri depolama aygıtları (teypler) ve veri referansları için indeksler kullanmayan problemlerin çözümü için uygundur. Bu Kahve Makinası (KM) için bir tezattır, çünkü rastgele erişimli isteklere de cevap verebilmektedir (basitlikten çok da uzaklaşmayarak).

Buna ek olarak, TM'ler 3. maddenin çok yüksek ve gereksiz karmaşıklığını, 1. ve 2. maddeleri basit tutarak lehlerine sağlamaktadır. Ve eğer, komut (instruction) tablosundakilerin karman çorman olduğunu düşünüyorsanız, Turing Makinası için bir derleyici yazmaya ne dersiniz? Kolay programlanamayan ve de hataları ayıklanmayan bir sistem, en azından bir bilgisayar mühendisi için sorgulanması gereken bir sistemdir. Mesela kahve makinasını Turing Makinası olarak simüle etmeye çalışın ya da tam tersi. Hey, eğer hala kabul etmiyorsanız, bana kodu gösterin.

Alt Satır: Kahve Makinası (KM), von Neuman mimarisinin iyi bir modelidir, O(1) karmaşıklığına sahiptir.