Sebuah Review Singkat Terhadap Emulasi Cellular Automata pada Mesin Turing

Abstract

Mesin-mesin Turing adalah suatu jenis abstraksi dari komputasi dan merupakan pemodelan yang sangat sederhana dari komputer. Mesin Turing sebagai model komputasi teoritis berfungsi sebagai model ideal untuk melakukan ilustrasi perhitungan/komputasi matematis. Meskipun 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 diselesaikan oleh komputer atau tidak (menentukan computable function). Universalitas komputasi adalah kemampuan dari sebuah mesin atau program untuk menghitung iterasi dari mesin atau program lain. Oleh karena bukti yang ada dari universalitas komputasi hanya berkaitan dengan Mesin Turing yang asli, maka pembuktian universalitas komputasional bagi programprogram yang lain dapat dilaksanakan melalui emulasi. Emulasi berarti bahwa serangkaian iterasi dalam suatu program akan menghasilkan suatu representasi yang setara (equivalent) dengan setiap langkah komputasi dari program yang ditiru. Pada artikel ini akan dipaparkan secara singkat pengemulasian sebuah Celullar Automata terhadap Mesin Turing. Celullar Automata adalah sebuah model komputasi terdesentralisasi yang menyediakan sebuah platform yang mangkus bagi pelaksanaan suatu komputasi yang lebih komplek.