Mesin Turing: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k Perubahan kosmetik tanda baca |
Fitur saranan suntingan: 3 pranala ditambahkan. Tag: VisualEditor Suntingan perangkat seluler Suntingan peramban seluler Tugas pengguna baru Disarankan: tambahkan pranala |
||
| (10 revisi perantara oleh 7 pengguna tidak ditampilkan) | |||
Baris 8:
Jauh sebelum lahirnya program komputer, Alan Turing pada tahun 1936 telah mengeluarkan gagasannya berupa model mesin abstrak sebagai alat mekanik untuk mengerjakan prosedur yang efektif. Model ini disebut Mesin Turing.
Mesin turing dapat diadaptasi untuk mensimulasi logika dari setiap algoritma oleh karena itu cara kerja mesin turing adalah ekivalen dengan cara kerja komputer sekarang ini dan mesin turing juga ekivalen dengan problema komputasi matematika. Mesin turing tidak ditujukan sebagai teknologi komputasi praktis tetapi lebih sebagai [[Eksperimen pikiran|eksperimen pemikiran]] yang mewakili sebuah mesin komputasi. Mesin turing membantu para ilmuan komputer memahami batas-batas komputasi mekanis.
Sebagai input dari mesin turing adalah kata atau untai atas suatu alfabet T. Mesin turing berhenti dengan keadaan menerima atau menolak untai. Kadang-kadang terjadi pula perulangan atau looping tak terhingga.
[[Berkas:Representasi_mesin_turing.jpg|
Keterangan:
Baris 38:
F: state akhir, F Î Q
== Gerakan Mesin Turing ==
Baris 47 ⟶ 46:
gerakan: mesin berubah ke status qj, menulis b dan posisi baca /tulis bergerak X (berupa R=gerak kekanan atau L=gerak kekiri).
<br />
[[Berkas:Gerakan_Mesin_Turing-1.png|al=|kiri|nirbing|615x615px|Gerakan Mesin Turing-1]]
<br />
[[Berkas:Gerakan_Mesin_Turing-2.png|al=|kiri|nirbing|562x562px|Gerakan Mesin Turing-2]]
II. Dimiliki mesin turing dengan definisi M ={ Q, S, G, S, F, Ь, ∆}
II. Dimiliki mesin turing dengan definisi M ={ Q, S, G, S, F, Ь, ∆}
Baris 80 ⟶ 68:
∆: ∆ (q1,a)= (q1,a,R)
Jika di inputkan string “abbba”, maka gerakan mesin turing akan menjadi seperti apa ?
[[Berkas:Abbba.png|al=|kiri|jmpl|520x520px|Abbba]]
<br />
Baris 112 ⟶ 92:
-Jika mesin Turing berada pada status Even, dan membaca simbol 1 pada Tape, lakukan hal berikut: Pindah status menjadi status Odd, Ganti simbol 1 pada Tape dengan Blank, dan Bergerak ke kanan satu sel.
[[
-Jika mesin Turing berada pada status Odd, dan membaca simbol 1 pada Tape, lakukan hal berikut: Pindah status menjadi Even, Ganti simbol 1 pada Tape dengan Blank, dan Bergerak ke kanan satu sel.
Baris 119 ⟶ 99:
-Jika mesin Turing berada pada status Odd, dan membaca simbol 0 pada Tape, lakukan hal berikut: Pindah status menjadi Halt, Ganti simbol 0 pada Tape dengan 1, dan tetap pada sel tersebut.
Palindrome itu adalah berasal dari [[bahasa Yunani]] yaitu Palindromos A Palindrome. Palindromos A Palindrome adalah kata atau kalimat yang sama dieja maju atau mundur(bacaan yang sama dieja pada kedua arah). Sebagai contoh sederhana adalah beberapa kata yang sederhana yaitu rotor, rotator, civic, madam, racecar, level, dan lain-lain. Untuk contoh lain yaitu kalimat palindrome adalah No lemon no melon, No devil lived on, Swap God for a janitor rot in a jar of dog paws, dll.
Dibawah ini adalah graf dari palindrome detector, merupakan sebuah simulasi mesin turing yang berfungsi untuk mendeteksi kata palindrome yang diinputkan oleh user. Kata atau untai yang dibentuk masih terbatas pada penggunaan huruf “A” dan “B”. Contoh kata yang dibentuk adalah “ABAABBA” untuk kata yang tidak termasuk dalam palindrome, dan “BABBAB” untuk kata yang termasuk dalam palindrome.
[[
Pemrograman sederhana jenis mesin Turing ini tidak sesulit yang dibayangkan. Dimana sebenarnya pemrograman ini akan membentuk graph. Transisi state terdiri dari 5-tupel rangkaian pada setiap baris, dengan format seperti ini:
Baris 149 ⟶ 128:
* [[Paul Strathern]]: ''Turing and the Computer - The big idea'', Anchor Books/Doubleday, ISBN 0-385-49243-X
* [http://www.abelard.org/turpap2/tp2-ie.asp Turing, A., ''On Computable Numbers, With an Application to the Entscheidungsproblem''], Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reprinted in M. David (ed.), ''The Undecidable'', Hewlett, NY: Raven Press, 1965;
* Boolos, G. and Jeffrey, R., ''Computability and Logic'', 2nd ed., Cambridge: [[Cambridge University Press]], 1980.
* [http://www.imt.ro/Romjist/Volum1/Vol1_3/turing.htm Rogozhin, Yurii, "A Universal Turing Machine with 22 States and 2 Symbols"] {{Webarchive|url=https://web.archive.org/web/20050308141040/http://www.imt.ro/Romjist/Volum1/Vol1_3/turing.htm |date=2005-03-08 }}, ''Romanian Journal Of Information Science and Technology'', 1(3), 259-265, 1998. (surveys known results about small universal Turing machines)
* [http://www.wolframscience.com/nksonline/page-707 Wolfram, Stephen, ''A New Kind of Science''], Wolfram Media, ISBN 1-57955-008-8
Baris 161 ⟶ 140:
=== Simulator ===
* [http://sourceforge.net/projects/visualturing/ Visual Turing Machine], a visual designer and simulator, (free software, platform independent).
* [http://www.cheransoft.com/vturing/ Visual Turing, a Turing machine interactive simulator/IDE] {{Webarchive|url=https://web.archive.org/web/20040407193325/http://www.cheransoft.com/vturing/ |date=2004-04-07 }} (free software for Windows).
* [http://ironphoenix.org/tril/tm/ Suzanne Britton's Turing Machine Simulator] (java applet).
* [http://semillon.wpi.edu/~aofa/AofA/msg00020.html C++ Simulator of a Nondeterministic and Deterministic Multitape Turing Machine] {{Webarchive|url=https://web.archive.org/web/20080515023814/http://semillon.wpi.edu/~aofa/AofA/msg00020.html |date=2008-05-15 }} (free software).
* [http://semillon.wpi.edu/~aofa/AofA/msg00024.html C++ Simulator of a Universal Turing Machine (which accepts Multitape Turing Machine)] {{Webarchive|url=https://web.archive.org/web/20050913091517/http://semillon.wpi.edu/~aofa/AofA/msg00024.html |date=2005-09-13 }} (free software).
* [http://www.monochrom.at/turingtrainterminal/ Turing Train Terminal] - A working Turing machine built out of scale trains.
* [http://www.unidex.com/turing/ TMML] - Describing a Turing Machine with XML
{{Formal languages and grammars}}
[[Kategori:Alan Turing]]
| |||