Apa Itu Mesin Turing??
Bisa di bilang mesin turing ini adalah model yang sangat sederhana dari komputer, Mesin turing ini juga bisa dibilang sebuah model matematika untuk komputasi yang diberikan dalam bentuk Mesin. mesin turing ini ditemukan oleh Alan Turing.
 |
| Alan Turing |
Seorang ahli matematika asal Inggris. Ia mengembangkan teori tentang "mesin universal" yang mampu memecahkan persamaan matematis. Selain merupakan peneliti komputer modern digital pertama, Alan juga yang pertama kali berpikir menggunakan komputer untuk berbagai keperluan. Bahkan saat menemukan mesin turing, ia belum lulus kuliah.
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 (menentukan computable function).
Mesin turing menggunakan pita (tape) sebagai memori yang berbentuk array . Hal ini menyebabkan data pada pita dapat diakses dari mana saja. Sebuah mesin Turing secara formal dinyatakan dalam 7 tupel, yaitu M = (Q, Σ, Γ, δ, S, F, b),
dimana :
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
b = simbol kosong (blank) bukan bagian dari Σ, b .Σ
Bagian dari pita yang belum ditulisi dianggap berisi simbol b (blank)
Mesin Turing terkenal dengan ungkapan "Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh komputer."
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 stack. Pada Mesin Turing, memori akan berupa suatu tape yang pada dasarnya merupakan array dari sel-sel penyimpanan.
A. 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
B. Prinsip Kerja mesin Turing
1. Lihat state semula dan simbol yang ditunjuk head
2. Berdasarkan fungsi transisinya,tentukan:
- State berikutnya
- Lakukan penulisan ke pita
- Gerakkan head ke kanan dan ke kiri
3. Bila dari pasangan state dan simbol yang ditunjuk head tidak ada lagi fungsi transisinya,berarti mesin turing berhenti
4. 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.
Representasi Mesin Turing :
Sumber :
Tidak ada komentar:
Posting Komentar