sebuah review singkat terhadap emulasi CeLlular Automata pada mesin turing

Hernawan Sulistyanto

DOI: https://doi.org/10.23917/komuniti.v6i2.2957

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.

Full Text:

PDF

References

Davis, M. 2000. The Universal Computer: The Road from Leibniz to Turing. New York: Norton.

Hopcroft, J.E., R. Motwani, and J. D. Ullman. 2001. Introduction to Automata Theory, Languange, and Computation. Edisi ke-2. Addison-Wesley

Maida, K., dan C. Sakama. 2007. Identifying Celullar Automata rules, in Journal of Celullar Automata,

Vol. 2, pp. 1-20.

Martin, O., A. M. Odlyzko, and S. Wolfram. 1984. Algebraic properties of Celullar Aotumata, Communications in Mathematical Physics, Springer-Verlag.

Mitchell, M. 1998. Computation in Celullar Automata, in Nonstandard Computation, pp. 95-140. Weinheim

Sipser, M. 2013. Introduction to the theory of computation, 3rd Ed, Cengage Learning, Boston USA.

Wegener, I. 2003. Complexity Theory: Exploring the limits of efficient algorithms, Springer-Verlag, Berlin.

Wolfram, S. 2002. A New Kind of Science. Champaign, IL: Wolfram Media Inc.

Zvi Kohavi, Z. 2005. Switching and Finite Automata Theory, McGraw-Hill.

Article Metrics

Abstract view(s): 253 time(s)
PDF: 138 time(s)

Refbacks

  • There are currently no refbacks.