Pengertian, Sejarah, dan Model Mesin Turing

Foto oleh Artem Podrez dari Pexels - 

Pengertian Mesin Turing

Mesin Turing adalah sebuah automata yang memiliki kemampuan lebih tinggi dari pada FSA (Finite State Automata) dan PDA (Push Down Automata) yang bisa menerima bahasa-bahasa reguler, bahasa konteks dan bahasa lainnya, dari segi aksi dan komponennya.

Sejarah Mesin Turing

Mesin Turing ini diusulkan pada tahun 1936 oleh Alan Turing, seorang matematikawan Inggris sebagai model matematis sederhana sebuah komputer.

Meskipun sederhana, Mesin Turing memiliki kemampuan untuk menggambarkan perilaku komputer general-purpose.

Mesin Turing dapat digunakan untuk menghitung kelas fungsi bilangan bulat yang dikenal sebagai fungsi rekursif sebagian (partial recursive function).

Sama seperti Finite State Automata dan Push Down Automata yang dapat mengenali bahasa formal, maka mesin Turing juga dapat berperan sebagai mesin pengenal bahasa formal.

Bahasa yang dikenali oleh Mesin Turing adalah bahasa tanpa-pembatasan (non-restricted language), yang disebut juga himpunan terenumerasi rekursif (recursively enumerable set).

Model Mesin Turing

Sebuah mesin Turing terdiri dari komponen-komponen :

1. Pengendali berhingga (finite control).
2. Pita masukan dengan sifat :

• Panjangnya tidak berhingga (ujung kiri terbatas, ujung kanan tidak terbatas).

• Dapat dibaca maupun ditulis.

• Sel yang tidak berisi simbol masukan akan berisi simbol kosong (blank = B).

PERBEDAAN MESIN TURING DENGAN FSA DAN PDA

Penjelasan

Mesin Turing mengenal gerakan ke kanan (Right) dengan symbol R dan ke kiri (Left) dengan simbol L.

Mesin terdiri dari :

• Q : Himpunan Stata
• Σ : Himpunan Input
• δ : Stata Awal
• r : Himpunan Simbol Ditransisi
• S : Fungsi Transisi
• B/ѣ : Blank
• F : Stata akhir

Contoh Kasus

Diketahui :

• Q : {𝑞_0, 𝑞_1, 𝑞_2, 𝑞_3, 𝑞_4, 𝑞_5, 𝑞_6}
• Σ : {0,1}
• δ : 𝑞₀
• r : {0,1,B}
• F : 𝑞₆

Apakah bahasa ini diterima atau ditolak mesin ?

1. 𝑞₀, 0IB
2. 𝑞₀, 00IB

Pembahasan

1. 𝑞₀, 0IB

• 𝑞₀, 0IB
• 𝑞₁, BIB
• 𝑞₂, BIB
• 𝑞₄, BIB
• 𝑞₄, BBB
• 𝑞₆, 0BB 

Input Diterima

2. 𝑞₀, 00IB

• 𝑞₀, 00IB
• 𝑞₁, 0BIB
• 𝑞₂, 0BIB
• 𝑞₄, 0BIB
• 𝑞₄, 0BBB
• 𝑞₆, 00BB 

Input Diterima

Latihan

Diketahui :

Q : {𝑞₀, 𝑞₁, 𝑞₂, 𝑞₃, 𝑞₄, 𝑞₅, 𝑞₆}

Σ : {0,1}

δ : 𝑞₀

r : {0,1,B}

F : 𝑞₆

1. Buat Diagram State
2. Apakah bahasa ini diterima atau ditolak oleh mesin ?

•  Q, bacb

Baca Juga :

Artikel Terkait