Sabtu, 26 Mei 2012

Mesin Turing

Jauh sebelum lahirnya program komputer, Alan Turing pada tahun 1936 telah mengeluarkan gagasannya berupa model mesin abstrak sebagai alat mekanik untuk mengerjakan prosedur yang efektif. Model ini disebut Mesin Turing.
Mesin turing dapat diadaptasi untuk mensimulasi logika dari setiap algoritma oleh karena itu cara kerja mesin turing adalah ekivalen dengan cara kerja komputer sekarang ini dan mesin turing juga ekivalen dengan problema komputasi matematika. Mesin turing tidak ditujukan sebagai teknologi komputasi praktis tetapi lebih sebagai eksperimen pemikiran yang mewakili sebuah mesin komputasi. Mesin turing membantu para ilmuan komputer memahami batas-batas komputasi mekanis.
            Sebagai input dari mesin turing adalah kata atau untai atas suatu alfabet T. Mesin turing berhenti dengan keadaan menerima atau menolak untai. Kadang-kadang terjadi pula perulangan atau looping tak terhingga.


Keterangan :
·        - Tape : Tempat diletakannya inputan yang berupa kata/untai.
·       -  Head: membaca dan menulisi sel pita mesin turing, bisa bergerak ke kiri atau ke kanan.
·       -  Finite StateControl (FSC) : otak dari TM, diimplementasikan dari algoritma pengenalan kalimat.

         
        Palindrome itu adalah berasal dari bahasa Yunani yaitu Palindromos A Palindrome. Palindromos A Palindrome adalah kata atau kalimat yang sama dieja maju atau mundur(bacaan yang sama dieja pada kedua arah). Sebagai contoh sederhana adalah beberapa kata yang sederhana yaitu rotor, rotator, civic, madam, racecar, level, dan lain-lain. Untuk contoh lain yaitu kalimat palindrome adalah No lemon no melon, No devil lived on, Swap God for a janitor  rot in a jar of dog paws, dll.







      Dibawah ini adalah graf dari palindrome detector , merupakan sebuah simulasi mesin turing yang berfungsi untuk mendeteksi kata palindrome yang diinputkan oleh user. Kata atau untai yang dibentuk masih terbatas pada penggunaan huruf “A” dan “B”. Contoh kata yang dibentuk adalah “ABAABBA” untuk kata yang tidak termasuk dalam palindrome, dan “BABBAB” untuk kata yang termasuk dalam palindrome.







        Pemrograman sederhana jenis mesin Turing ini tidak sesulit yang dibayangkan. Dimana sebenarnya pemrograman ini akan membentuk graph. Transisi state terdiridari5-tupel rangkaian pada setiap baris, dengan format seperti ini:
[state],[karakter],[state baru],[karakterbaru],[arah]
    1    ,      _        ,       2        ,         #             ,     >
   2    ,      A       ,       3        ,          A            ,     >
       Karakter '_' dapat digunakan untuk menunjukkan kosong(blank), 'H' untuk menunjukkan sebagai state berhenti/Halt (hanya berlaku pada sisi kanan transisi), dan '<' dan '>' untuk menunjukkan arah  masing-masing bergerak kekiri atau kanan.



3 komentar:

  1. kk gambar pertama aku gak ngerti... bisa di jelasin lebih ringkas lagi gak...

    mksh

    BalasHapus
  2. kk bedanya gmbar representasi mesin turing di atas dengan fa dan pda apa ya??

    http://cobacoba-tutorial.blogspot.com/

    BalasHapus