Kuliah Bahasa Pemrograman: Komputasi dan Mesin Turing

Peralatan digital elektronik yang Anda gunakan sekarang untuk membaca tulisan ini kita sebut dengan nama Komputer, terjemahan dari kata dalam bahasa Inggris Computer.

Apa perbedaan antara Computer dengan Calculator? Mengapa kita menciptakan sebuah istilah baru untuk peralatan digital ini, Computer, dan tidak cukup hanya dengan istilah Calculator?

Secara bahasa, Computer berasal dari kata dasar "to Compute", sedangkan Calculator berasal dari kata dasar "to Calculate". Ketika kedua kata tersebut diterjemahkan ke dalam bahasa Indonesia, keduanya
sama-sama memiliki makna "menghitung". Untuk memberikan gambaran perbedaan antara kedua istilah itu, berikut ini diberikan sebuah contoh masalah yang bisa diselesaikan melalui cara "to Compute":

1. Menghitung suhu dalam skala Celsius dari nilai suhu dalam skala Fahrenheit.
2. Membalik sebuah kata, misalnya "Hello" menjadi "olleH".
3. Menentukan rangkaian molekul DNA dalam fase transkripsi gen.

Dari tiga contoh yang diberikan, kesimpulan sederhana yang bisa dibangun tentang perbedaan "to Compute" dengan "to Calculate" kurang lebih adalah bahwa "to Compute" lebih luas cakupannya daripada "to Calculate".

Untuk menghitung sebuah nilai dari nilai input yang diberikan, kita melakukan perhitungan (kalkulasi). Dalam contoh di atas, kita menghitung suhu Celsius dari nilai Fahrenheit yang diberikan. Contoh ini juga menunjukkan bahwa dalam mencari nilai suhu dalam skala Celsius, kita melakukan langkah-langkah tertentu (mengetahui nilai Fahrenheit yang ingin dihitung, memasukkannya ke dalam rumus konversi Fahrenheit-Celsius, dan mendapatkan hasilnya).

Untuk membalik sebuah kata, kita juga melakukan langkah-langkah dalam urutan tertentu. Akan tetapi dalam contoh ini kita sama sekali tidak menggunakan rumus seperti dalam contoh konversi suhu. Dalam contoh transkripsi gen, kita juga tidak melibatkan rumus matematika sama sekali, kecuali mungkin sebuah pemetaan atau relasi sederhana: Molekul A ditranskripsikan ke molekul T (atau sebaliknya) dan molekul C ditranskripsikan ke molekul G (atau sebaliknya).

Dari contoh-contoh di atas sebuah satu definisi sederhana yang bisa diberikan untuk istilah Komputasi adalah sebagai berikut:

Sekumpulan langkah yang jelas untuk melakukan sesuatu, dan langkah-langkah ini dapat diselesaikan dalam waktu yang terbatas.

Mesin Turing

Sebuah model matematika untuk Komputasi diberikan dalam bentuk Mesin Turing. Sebuah Mesin Turing memiliki beberapa komponen:

1. Sebuah Tape atau Pita, yang panjangnya tak berhingga dan dibagi ke dalam sel-sel. Setiap sel dapat berisi simbol-simbol tertentu.
2. Sebuah Head, yang membaca simbol-simbol pada masing-masing sel pada Tape, atau dapat juga menulis simbol-simbol ke masing-masing sel pada Tape. Head juga dapat bergerak ke kiri atau ke kanan, sesuai arah pergerakan Tape.
3. Sekumpulan States atau Status dari mesin Turing yang bersangkutan. Sekurang-kurangnya ada dua status yang dimiliki oleh sembarang mesin Turing: Start State dan Halt State. Mesin Turing selalu memulai proses komputasi dari status Start dan berakhir pada status Halt.
4. Sekumpulan aturan Transisi yang didefinisikan berdasarkan apa yang dibaca oleh Head dari Tape dan Status dari mesin pada satu saat tertentu.

Contoh Mesin Turing Sederhana

Sebuah contoh mesin Turing dapat dibangun untuk melakukan komputasi sederhana yang didefinsikan seperti ini:

Tentukan ada berapa angka 1 dalam sebuah string berbentuk 0111...110 (rangkaian angka 1 yang didahului dengan 0 dan diakhiri juga dengan 0), apakah berjumlah genap atau berjumlah ganjil.

Jika angka 1 di antara dua angka 0 berjumlah genap, tulis sebuah angka 0 pada salah satu sel dari tape mesin Turing.

Jika angka 1 di antara dua angka 0 berjumlah ganjil, tulis sebuah angka 1 pada salah satu sel dari tape mesin Turing.

Untuk menyelesaikan masalah komputasi ini, kita buat tiga buah State bagi mesin Turing ini, yaitu Start, Even, dan Odd. Di samping itu kita buat sekumpulan aturan Transisi yang digunakan oleh
mesin Turing ini untuk melakukan proses komputasinya. Aturan-aturan Transisi tersebut dapat dituliskan demikian:

1. Jika mesin Turing berada pada status Start, dan membaca simbol 0 pada Tape, lakukan hal berikut: Pindah status menjadi status Even, Ganti simbol 0 pada Tape dengan Blank (atau Hapus simbol 0 pada Tape), dan Bergerak ke kanan satu sel.
2. 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.
3. 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.
4. Jika mesin Turing berada pada status Even, dan membaca simbol 0 pada Tape, lakukan hal berikut: Pindah status menjadi Halt, Ganti simbol 0 pada Tape dengan 0, dan tetap pada sel tersebut (tidak perlu berpindah ke kiri maupun ke kanan).
5. 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.

Berkas presentasi tentang Komputasi, Mesin Turing, dan Komputabilitas dapat diunduh di sini.

Sumber Rujukan

1. Gambar dari ATuringMachine dot com. Satu tautan video menarik tentang mesin Turing juga bisa dilihat pada situs ini.
2. Contoh mesin Turing dari buku "A Guided Tour to Complexity", karya Melanie Mitchell.