Mesin Turing

Lukisan Mesin Turing.

Mesin Turing adalah model komputasi teoritis yang ditemukan oleh Alan Turing, 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 terkenal dengan ungkapan " Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh komputer.

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.

Lihat juga

• Langton's ant, a simple two-dimensional analogue of the Turing machine.
• Probabilistic Turing machine
• Church-Turing thesis, which says Turing machines can perform any computation that can be performed.
• Busy Beaver
• Computability logic
• Turing completeness
• Turing tarpit, any computing system or language which, like the Turing machine, is not only Turing-complete but also useless for practical computing.
• Neal Stephenson's Cryptonomicon

Referensi

• Rolf Herken: The Universal Turing Machine - A Half-Century Survey, Springer Verlag, ISBN 3-211-82637-8
• Paul Strathern: Turing and the Computer - The big idea, Anchor Books/Doubleday, ISBN 0-385-49243-X
• 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.
• Rogozhin, Yurii, "A Universal Turing Machine with 22 States and 2 Symbols", Romanian Journal Of Information Science and Technology, 1(3), 259-265, 1998. (surveys known results about small universal Turing machines)
• Wolfram, Stephen, A New Kind of Science, Wolfram Media, ISBN 1-57955-008-8

Pranala luar

• Turing Machine on Stanford Encyclopedia of Philosophy
• Detailed info on the Church-Turing Hypothesis (Stanford Encyclopedia of Philosophy)

Simulator

• Visual Turing Machine, a visual designer and simulator, (free software, platform independent).
• Visual Turing, a Turing machine interactive simulator/IDE (free software for Windows).
• Suzanne Britton's Turing Machine Simulator (java applet).
• C++ Simulator of a Nondeterministic and Deterministic Multitape Turing Machine (free software).
• C++ Simulator of a Universal Turing Machine (which accepts Multitape Turing Machine) (free software).
• Turing Train Terminal - A working Turing machine built out of scale trains.
• TMML - Describing a Turing Machine with XML