MESIN TURING

Yo man.. .  kit katumu lae, , ,  ini kali bet mau bahas apa itu mesin turing, mesin turing itu apa ? mesin turing adalah sebuah mesin yang di temukan oleh Bapatua Alan Turing (23 Juni 1912 - 07 Juni 1954), yo untuk lebe jelas na mari baca eee, , 

Mesin terdiri dari sebuah finite control, yang dapat berada dalam sebuah himpunan berhingga dari state. Terdapat sebuah tape yang dibagi ke dalam kotak-kotak atau sel-sel. Setiap sel dapat menampung sebuah dari sejumlah berhingga dari simbol.
Pada awalnya, input yang merupakan string dari simbol dengan panjang berhingga dipilih dari input alphabet, ditempatkan pada tape.

• Sel-sel tape yang lain, perluasan secara infinite ke kiri dan ke kanan, pada awalnya menampung simbol khusus yang dinamakan blank.
• Blank bukan sebuah input symbol, dan mungkin terdapat simbol tape yang lain disamping input symbol dan blank.
• Terdapat sebuah tape head yang selalu ditempatkan pada salah satu dari sel-sel tape.
• Mesin turing dikatakan men-scan sel tersebut. Pada awalnya, tape head berada pada sel paling kiri yang menampung input.

Sebuah pergerakan mesin Turing adalah sebuah fungsi dari state dari finite control dan tape symbol yang di-scan.
Dalam satu pergerakan, mesin Turing akan:
 Merubah state.v Next state dapat sama dengan current state.
v Menulis sebuah tape symbol dalam sel yang di-scan. Tape symbol ini mengganti symbol apapun yang ada dalam sel tersebut. Secara opsional, simbol yang dituliskan dapat sama dengan simbol yang sekarang ada dalam tape.
 Memindahkan tape head ke kiri atau ke kanan.v 

Mesin Turing dijelaskan oleh 7-tuple:
M = (Q, S, G, d, q0, B, F)
Komponen-komponennya adalah:
• Q: Himpunan berhingga dari state dari finite control.
• S: himpunan berhingga dari 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 dari d(q, X), jika nilai tersebut didefinisikan, adalah triple (p, Y, D), dimana:
• p adalah next state dalam Q
• Y adalah simbol, dalam G, ditulis dalam sel yang sedang di-scan, menggantikan simbol apapun yang ada dalam sel tersebut.
• D adalah arah, berupa L atau R, berturut-turut menyatakan left atau right, dan menyatakan arah dimana head bergerak.
• q0: start state, sebuah anggota dari Q, dimana pada saat awal finite control ditemukan.
• B: simbol blank. Simbol ini ada dalam G tapi tidak dalam S, yaitu B bukan sebuah simbol input.
• F: himpunan dari final state, subset dari Q.

Sebuah mesin turing terdiri atas barisan sel tersusun berupa pita yang dapat bergerak maju mundur, komponen aktif baca/tulis pita yang memiliki status perhitungan serta dapat mengubah/menulisi sel aktif yang ada di pita tadi, dan suatu kumpulan instruksi bagaimana komponen baca/tulis ini harus melakukan modifikasi terhadap sel aktif pada pita, serta bagaimana menggerakkan pita tersebut. Pada setiap langkah dalam komputasi, mesin ini akan dapat mengubah isi dari sel yang aktif, mengubah status dari komponen baca/tulis, dan mengubah posisi pita kekiri atau kekanan.

Pembacaan fungsi transisi pada mesin turing

Misal :

 d (q1,a) = (q1,b,R) dibaca :

Pada state q1 yang menunjukkan karakter a pada pita, maka karakter pada state tersebut berubah menjadi b dan head bergerak ke kanan dengan menunjuk array sebagai  state q1

Prinsip Kerja mesin Turing

·         Lihat state semula dan simbol yang ditunjuk head

·         Berdasarkan fungsi transisinya,tentukan:

·          state berikutnya

·          Lakukan penulisan ke pita

·         Gerakkan head ke kanan dan ke kiri

·         Bila dari pasangan state dan simbol yang ditunjuk head tidak ada lagi fungsi transisinya,berarti mesin turing berhenti

·         Bila mesin turing berhenti di dalam state final (F) , berarti input diterima. Sebaliknya jika mesin berhenti tidak pada state akhir,maka berarti inputan tersebut ditolak.