ALGORITMA DAN MESIN KOMPUTASI

a.Prosedur dan algoritma

Untuk menyelesaikan suatu masalah, kita dapat mengupayakan dengan menyusun langkah-langkah berupa instruksi untuk dikerjakan. Sebuah PROSEDUR yang efektif didefinisikan sebagai deretan instruksi yang banyaknya hingga, diskrit dan jelas, serta dapat dikerjakan secara mekanik. Kalau masalah kita merupakan masalah komputasi maka pengertian dapat dikerjakan secara mekanik dapat membuat suatu program computer untuk mengerjakan instruksi tersebut. 

Sebagai contoh, berikut ini adalah prosedur yang dapat kita gunakan ketika ingin mengirim surat kepada teman yakni :

1.Tulis surat, pada secarik surat

2.Ambil sampul surat

3.Masukkan surat ke dalam sampul

4.Tutup sampul surat menggunakan perekat

5.Jika ingat alamat tersebut, maka tulis alamat pada sampul surat, jika tidak lebih dahulu pada buku alamat kemudian tulis alamat sampul surat

6.Tempel perangko pada surat

7.Bawa surat ke kantor pos untuk di poskan.

Ketujuh langkah diatas merupakan prosedur yang efektif. Banyaknya instruksi adalah hingga masing-masing bersifat diskrit dan jelas serta dapat kita kerjakan secara mekanik.

Selain menyajikan prosedur seperti cara diatas, yang sering disebut sebagai pseudocode, kita dapat menyajikan dalam bentuk flowchart atau diagram alur.

b.Mesin Turing

Jauh sebelum lahirnya computer, 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, dan biasa disingkat MT. 

Selain itu mesin turing, masih terdapat beebrapa model lain untuk keperluan serupa diantaranya adalah mesin post.

Cara kerja MT adalah ekivalen dengan cara kerja computer digital sekarang ini. Ia juga ekivalen dengan problema komputasi matematika.

Sebagai input MT adalah kata atau untai atas alphabet T. Ia berhenti dengan keadaan menerima atau menolak untai. Kadang-kadang terjadi perulangan atau looping tak hingga.

c.Penyajian  Mesin Turing

Ada bermacam-macam cara menyajikan MT. Sebelum itu, kita definisikan   dahulu suatu MT secara formal. Mesin turing M atas alphabet, terdiri atas:

1.Tape atau pita yang berbentuk dari deretan sel. Tape mempunyai sel terkiri atau leftmost, tetapi mempunyai tak hingga sel ke kanan. Setiap sel hanya bisa berisi satu symbol pita.

Simbol pita terdiri dari huruf dalam alphabet T, huruf pada alphabet hingga V(alphabet tambahan), serta symbol blank.

2.Tape head atau Kepala pita. yang mengamati satu sel tape apda satu waktu. Head dapat bergerak. Pada setiap move atau gerak, head mencetak sebuah symbol pada sel yang diamati. mehghapus apa yang telah tertulis sebelumnya pada sel itu, lalu move ke kiri atau ke kanan.

3.Sebuah program,merupakan digraph hingga. Ia merupakan sebuah finite control. Simpul diagraph merupakan Stata.

Selalu terdapat Stata Awal yang disebut START, dan sebuah himpunan Stata Akhir(boleh hampa) yang disebut HALT.

d.Cara Kerja Mesin Turing

Mula-mula untai w ditempatkan dibagian paling kiri dari tape, sisa dibagian program, kanan diisi symbol blank, Tape head menunjuk pada leftmost sel. Program bermula pada Stata START. Kalau tercapai stata HALT, komputasi dihentikan, untai diterima mesin turing. 

Sumber: Pengantar Automata Bahasa Formal dan Komputasi , D. Suyadi H.S, Universitas Gunadarma