Mesin Turing

Pengertian Mesin Turing

Mesin turing (Turing Machine) adalah model komputasi teoritis yang ditemukan oleh Alan Turing pada tahun 1936, berfungsi sebagai model ideal untuk melakukan perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum komputer nyata dibangun, model ini tetap diterima kalangan ilmu komputer sebagai model komputer yang sesuai untuk menentukan apakah suatu fungsi dapat selesaikan oleh komputer atau tidak. Mesin Turing terkenal dengan ungkapan: “Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh komputer.”.


Perkembangan komputer yang sangat luar biasa tidak luput dari peran penting seorang Alan. Berbagai processor dengan kemampuan tinggi lahir. Kemampuan komputasi yang meningkat secara pesat tersebut memiliki konsep yang tetap sama yaitu mesin turing sebagai “ibu”-nya.
Mesin turing mewujudkan prinsip esensial komputer. Mesin ini memperkenalkan sebuah konsep signifikansi praktis yang sangat besar. Komputasi sendiri pertama kali dianggap sebagai model kognisi sejak ditemukannya arsitektur standar komputer yang dipakai sampai sekarang. Bahkan, dalam buku The History of Psychology yang ditulis oleh George Boerre, Alan mampu menciptakan konsep-konsep ilmu komputer di luar imajinasinya.
Sebagian besar literatur menyebutkan, mesin turing adalah sebuah alat pengubah dan manipulasi basic simbol abstract. Karena kesederhanaanya, mesin turing dapat diadaptasikan untuk melakukan simulasi logika yang dapat dibangun oleh berbagai komputer modern.
Mesin turing dapat mengkomputasi apapun yang bisa dikomputasi. Mesin ini adalah definisi dari komputasi itu sendiri atau alat yang sangat fundamental ketika bersoal tentang komputer. Jika Charles Babbage, penemu komputer lainnya, menciptakan mesin yang ditujukan untuk melakukan hal yang bersifat praktis, lain hal dengan mesin turing. Alan menciptakan mesin turing sebagai mesin pikiran. Mesin itu tidak diciptakan untuk mengkomputasi banyak angka, melainkan ditujukan untuk memecahkan perkara logis dan menggali limitasi dari komputasi dan pemikiran manusia.
Mesin turing terdiri dari pita yang dapat digunakan untuk membaca dan menulis simbol pada pita di dalamnya. Seperti layaknya finite machine yang lain, mesin turing memiliki mekanisme kontrol yang berada pada salah satu finite states. Salah satu state ini kita kenal dengan initial state ketika mesin melakukan awal inisialisasi. Lainnya kita kenal dengan halt state. Ketika mesin mencapai state ini, mesin berhenti melakukan komputasi. Oleh karena itu, mesin turing dapat menjadikan pita tersebut sebagai tempat penyimpanan. Akan tetapi, mesin turing tidak terbatas pada operasi push dan pop ketika mengakses media penyimpanannya. Sejak saat itu, mesin turing merupakan ibu dari semua komputer yang ada saat ini.

   B. Cara Kerja

Mesin Turing adalah model yang sangat sederhana dari komputer.  Secara esensial, mesin turing adalah sebuah finite automata yang miliki sebuah tape tunggal dengan panjang tak terhingga yang dapat membaca dan menulis data.  Mesin turing menggunakan notasi seperti ID-ID pada PDA untuk menyatakan konfigurasi dari komputasinya. Stack pada PDA memiliki keterbatasan akses. Elemen yang dapat diakses hanya elemen yang ada pada top of stack. Pada mesin turing, memori akan berupa suatu tape yang pada dasarnya merupakan array dari sel-sel penyimpanan.
Sebuah mesin Turing secara formal dinyatakan dalam 7-tuple, yaitu M = (Q, Σ, Γ, δ, S, F, b) di mana :
Q = Himpunan state
Σ = Himpunan simbol input
Γ = Simbol pada pita (meliputi pula blank)
δ = Fungsi transisi
S = State awal, S ∈ Q
F = Himpunan state akhir, F ⊆ Q
Ь = Simbol kosong (blank), bukan bagian dari Σ, b .Σ
Bagian dari pita yang belum ditulisi dianggap berisi simbol Ь (blank).

   C. Deskripsi Instantaneous (ID) untuk Mesin Turing

ID digunakan untuk mengetahui apa yang mesin turing kerjakan.  ID direpresentasikan oleh string X₁X₂X₃… X_i-1qX_iX_i+1 … X_n, di mana:

• q adalah state dari TM
• Tape head men-scan simbol ke-i dari kiri.
• X₁X₂ …X_n adalah bagian dari tape di antara nonblank pada sel paling kiri dan paling kanan.

Pergerakan TM M = (Q, S, G, d, q₀, B, F) dinyatakan oleh notasi ├ atau ├. ├^*_M atau ├^* digunakan untuk menunjukkan nol, satu atau lebih pergerakan dari TM.
Anggap d(q, X_i) = (p, Y, L), yaitu pergerakan selanjutnya adalah ke kiri.  Maka
X₁X₂… X_i-1qX_iX_i+1 … X_n
├ X₁X₂… X_i-2pX_i-1 YX_i+1 … X_n
Pergerakan ini menyatakan perubahan ke state p. Tape head sekarang diposisikan di sel i-1.
Jika i = n dan Y = B maka simbol B yang ditulis pada Xn berhubungan dengan urutan tak hingga dari blank–blank yang mengikuti dan tidak muncul dalam ID selanjutnya.  Dengan demikian
X1X2 …Xn-1 q Xn├ X1X2… Xn-2p Xn-1
Terdapat dua pengecualian:
–          Jika i=1, maka M bergerak ke blank ke bagian kiri dari X1.  Dalam kasus ini,
qX₁X₂ …X_n├ pBYX₂… X_n
–          Jika i = n dan Y = B maka simbol B yang ditulis pada Xn berhubungan dengan urutan tak hingga dari blank–blank yang mengikuti dan tidak muncul dalam ID selanjutnya.  Dengan demikian
X₁X₂ …X_n-1 q X_n├ X₁X₂… X_n-2p X_n-1
Anggap d(q, Xi) = (p, Y, R), yaitu pergerakan selanjutnya adalah ke kanan.  Maka
X₁X₂… X_i-1qX_iX_i+1 … X_n ├ X₁X₂… X_i-1 YpX_i+1 … X_n
Tape head telah bergerak ke sel i+1.  Terdapat dua pengecualian:
–               Jika i = n, maka sel ke-i+1 menampung sebuah blank, dan sel tersebut bukan bagian dari ID sebelumnya.  Dengan demikian
X₁X₂ … X_n-1 qX_n├ X₁ X₂… X_n-1YpB
–               Jika i = 1 dan Y = B maka simbol B yang ditulis pada X1 berhubungan dengan urutan tak hingga dari blank–blank dan tidak muncul dalam ID selanjutnya.  Dengan demikian
qX₁X₂ …X_n├ pX₂… X_n

   D. Diagram Transisi untuk Mesin Turing

Diagram transisi terdiri dari sebuah himpunan dari node–node yang menyatakan state–state dari Mesin Turing yaitu sebuah arc dari state q ke state p diberi label oleh satu atau lebih item dengan bentuk X/Y D, dimana X dan Y adalah tape symbol, dan D adalah arah, kiri (L) atau kanan (R).  Bahwa bila d(q, X) = (p, Y, D) diperoleh label X/Y D pada arc dari q ke p. Dalam diagram arah D dinyatakan dengan tanda ¬ untuk “left” dan ® untuk “right”.  Start state ditandai dengan kata “start” dan sebuah panah yang masuk ke dalam state tersebut.  Final state ditandai dengan putaran ganda.
Contoh:
Mesin Turing berikut menghitungan fungsi   , yang dinamakan monus atau proper substraction.  Fungsi ini didefinisikan oleh  m   n = max(m – n, 0).  Bahwa, m   n = m – n jika m ³ n dan 0 jika m < n.  Mesin Turing yang melakukan operasi ini adalah
M = ({q₀, q₁, … , q₆}, {0, 1}, {0, 1, B}, d, q₀, B)
Aturan untuk fungsi transisi d:

Diagram transisi dari mesin turing M: