Mesin Turing

Mesin Turing merupakan model yg sangat sederhana dari komputer.  Secara esensial, mesin Turing merupakan sebuah finite automaton yg miliki sebuah tape tunggal menggunakan panjang tidak terhingga yg dapat membaca & menulis data.  Mesin Turing memakai notasi seperti ID-ID pada PDA buat menyatakan konfigurasi dari komputasinya. Stack pada PDA memiliki keterbatasan akses.  Elemen yang dapat diakses hanya elemen yang terdapat dalam top stack. Pada Mesin Turing, memori akan berupa suatu tape yg pada dasarnya merupakan array berdasarkan sel-sel penyimpanan.

Visualisasi menurut sebuah mesin Turing diberikan oleh gambar berikut:

Mesin terdiri menurut sebuah finite control, yang bisa berada dalam sebuah himpunan berhingga menurut state.  Terdapat sebuah tape yg dibagi ke dalam kotak-kotak atau sel-sel.  Setiap sel dapat menampung sebuah berdasarkan sejumlah berhingga berdasarkan simbol.  Pada awalnya, input yg merupakan string berdasarkan simbol menggunakan panjang berhingga dipilih berdasarkan input alphabet, ditempatkan pada tape. Sel-sel tape yg lain, perluasan secara infinite ke kiri & ke kanan, pada awalnya menampung simbol spesifik yang dinamakan blank. Blank bukan sebuah input symbol, & mungkin terdapat simbol tape yg lain disamping input symbol dan blank.  Terdapat sebuah tape head yg selalu ditempatkan pada salahsatu menurut sel-sel tape.  Mesin turing dikatakan men-scan sel tersebut. Pada awalnya, tape head berada dalam sel paling kiri yang menampung input. Sebuah konvoi mesin Turing adalah sebuah fungsi berdasarkan state menurut finite control & tape symbol yang pada-scan.

Dalam satu pergerakan, mesin Turing akan:Merubah state.  Next state bisa sama dengan current state.Menulis sebuah tape symbol dalam sel yang pada-scan.  Tape symbol ini mengubah symbol apapun yg terdapat dalam sel tersebut.  Secara opsional, simbol yang dituliskan dapat sama menggunakan simbol yg sekarang terdapat dalam tape.Memindahkan tape head ke arah kiri atau ke kanan.

Notasi formal Mesin Turing

Mesin Turing dijelaskan oleh 7-tuple:

Komponen-komponennya merupakan:Q:  Himpunan berhingga berdasarkan state berdasarkan finite control.S: himpunan berhingga berdasarkan simbol-simbol input.G: Himpunan dari tape symbol.  S merupakan subset dari G.

d:  Fungsi transisi.  Argumen d(q, X) adalah sebuah state q dan sebuah tape symbol X.  Nilai menurut d(q, X), bila nilai tersebut didefinisikan, adalah triple (p, Y, D), dimana:p merupakan next state dalam QY adalah simbol, pada G, ditulis dalam sel yang sedang di-scan, menggantikan simbol apapun yang terdapat dalam sel tadi.D merupakan arah, berupa L atau R, berturut-turut menyatakan left atau right, & menyatakan arah dimana head berkiprah.

q0: start state, sebuah anggota dari Q, dimana pada saat awal finite control ditemukan.

B: simbol blank.  Simbol ini ada dalam G akan tetapi tidak dalam S, yaitu B bukan sebuah simbol input.

F: himpunan dari final state, subset berdasarkan Q.

Deskripsi Instantaneous (ID) buat Mesin Turing

ID dipakai untuk mengetahui apa yg mesin Turing kerjakan.  ID direpresentasikan oleh string X1X2X3… Xi-1qXiXi+1 … Xn, dimana:

–        q merupakan state dari TM

–        Tape head men-scan simbol ke-i menurut kiri.

–        X1X2 …Xn adalah bagian dari tape di antara nonblank pada sel paling kiri dan paling kanan.

Pergerakan TM M = (Q, S, G, d, q0, B, F) dinyatakan oleh notasi ├ atau ├. ├*M atau ├* digunakan buat menunjukkan nol, satu atau lebih pergerakan dari TM.

Anggap d(q, Xi) = (p, Y, L), yaitu pergerakan selanjutnya adalah ke arah kiri.  Maka

├ X1X2… Xi-2pXi-1 YXi+1 … Xn

Pergerakan ini menyatakan perubahan ke state p. Tape head kinidiposisikan di sel i-1.

apabila i = n dan Y = B maka simbol B yg ditulis dalam Xn herbi urutan tak sampai berdasarkan blank–blank yang mengikuti dan tidak timbul dalam ID selanjutnya.  Dengan demikian

X1X2 …Xn-1 q Xn├ X1X2… Xn-2p Xn-1

–          apabila i=1, maka M beranjak ke blank ke bagian kiri menurut X1.  Dalam perkara ini,

–          Jika i = n & Y = B maka simbol B yg ditulis pada Xn herbi urutan tak hingga berdasarkan blank–blank yang mengikuti & tidak ada dalam ID selanjutnya.  Dengan demikian

X1X2 …Xn-1 q Xn├ X1X2… Xn-2p Xn-1

Anggap d(q, Xi) = (p, Y, R), yaitu konvoi selanjutnya adalah ke kanan.  Maka

X1X2… Xi-1qXiXi+1 … Xn ├ X1X2… Xi-1 YpXi+1 … Xn

Tape head sudah berkecimpung ke sel i+1.  Terdapat 2 pengecualian:

–               apabila i = n, maka sel ke-i+1 menampung sebuah blank, & sel tadi bukan bagian menurut ID sebelumnya.  Dengan demikian

X1X2 … Xn-1 qXn├ X1 X2… Xn-1YpB

–               apabila i = 1 & Y = B maka simbol B yg ditulis dalam X1 berhubungan dengan urutan tak hingga dari blank–blank & nir muncul dalam ID selanjutnya.  Dengan demikian

Diagram Transisi buat Mesin Turing

Diagram transisi terdiri berdasarkan sebuah himpunan menurut node–node yg menyatakan state–state berdasarkan Mesin Turing .sebuah arc dari state q ke state p diberi label sang satu atau lebih item dengan bentuk X/Y D, dimana X dan Y merupakan 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 menurut q ke p. Dalam diagram arah D dinyatakan dengan tanda ¬ buat “left” dan ® buat “right”.  Start state ditandai dengan istilah “start” dan sebuah panah yg masuk ke pada state tersebut.  Final state ditandai menggunakan putaran ganda.

Mesin Turing berikut menghitungan fungsi   , yg dinamakan monus atau proper substraction.  Fungsi ini didefinisikan sang  m   n = max(m – n, 0).  Bahwa, m   n = m – n apabila m ³ n & 0 jika m < n.  Mesin Turing yg melakukan operasi ini merupakan

M = (q0, q1, … , q6, 0, 1, 0, 1, B, d, q0, B)

Aturan buat fungsi transisi d:

Diagram transisi menurut mesin Turing M:

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. 2001. Introduction to Automata Theory, Languange, and Computation. Edisi ke-dua.  Addison-Wesley