Mesin Turing dan Bahasa Otomata (Automata)

MESIN TURING dan AGEN AI

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.”

Mesin Turing adalah model yang sangat sederhana dari komputer. Secara esensial, mesin Turing adalah sebuah finite automaton yang miliki sebuah tape tunggal dengan panjang tak terhingga yang dapat membaca dan menulis data.
Mesin Turing menggunakan notasi seperti ID-ID pada PDA untuk menyatakan konfigurasi dari komputasinya.
Mesin terdiri dari sebuah finite control, yang dapat berada dalam sebuah himpunan berhingga dari state. Terdapat sebuah tape yang dibagi ke dalam kotak-kotak atau sel-sel. Setiap sel dapat menampung sebuah dari sejumlah berhingga dari simbol.
Pada awalnya, input yang merupakan string dari simbol dengan panjang berhingga dipilih dari input alphabet, ditempatkan pada tape.

• Sel-sel tape yang lain, perluasan secara infinite ke kiri dan ke kanan, pada awalnya menampung simbol khusus yang dinamakan blank.
• Blank bukan sebuah input symbol, dan mungkin terdapat simbol tape yang lain disamping input symbol dan blank.
• Terdapat sebuah tape head yang selalu ditempatkan pada salah satu dari sel-sel tape.
• Mesin turing dikatakan men-scan sel tersebut. Pada awalnya, tape head berada pada sel paling kiri yang menampung input.

Sebuah pergerakan mesin Turing adalah sebuah fungsi dari state dari finite control dan tape symbol yang di-scan.
Dalam satu pergerakan, mesin Turing akan:
 Merubah state.v Next state dapat sama dengan current state.
v Menulis sebuah tape symbol dalam sel yang di-scan. Tape symbol ini mengganti symbol apapun yang ada dalam sel tersebut. Secara opsional, simbol yang dituliskan dapat sama dengan simbol yang sekarang ada dalam tape.
 Memindahkan tape head ke kiri atau ke kanan.v

Mesin Turing dijelaskan oleh 7-tuple:
M = (Q, S, G, d, q0, B, F)
Komponen-komponennya adalah:
• Q: Himpunan berhingga dari state dari finite control.
• S: himpunan berhingga dari simbol-simbol input.
• G: Himpunan dari tape symbol. S merupakan subset dari G.
• d: Fungsi transisi. Argumen d(q, X) adalah sebuah state q dan sebuah tape symbol X. Nilai dari d(q, X), jika nilai tersebut didefinisikan, adalah triple (p, Y, D), dimana:
• p adalah next state dalam Q
• Y adalah simbol, dalam G, ditulis dalam sel yang sedang di-scan, menggantikan simbol apapun yang ada dalam sel tersebut.
• D adalah arah, berupa L atau R, berturut-turut menyatakan left atau right, dan menyatakan arah dimana head bergerak.
• q0: start state, sebuah anggota dari Q, dimana pada saat awal finite control ditemukan.
• B: simbol blank. Simbol ini ada dalam G tapi tidak dalam S, yaitu B bukan sebuah simbol input.
• F: himpunan dari final state, subset dari Q.

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.

Alan Mattison Turing lahir di Paddington London, 23 Juni 1912. Turing melewati awal hidupnya di sebuah rumah panti asuhan di India. Saat kembali ke Inggris tahun 1926, Turing bersekolah di Sherborne. Keingintahuannya dalam bidang matematika dan sains sangat berbading terbalik dengan minatnya dibidang Bahasa dan social.

Tahun 1931 Turing bersekolah di King’s College, Cambridge University. Dalam penelitiannya Turing lebih banyak “menciptakan kembali” dibandingkan “menggunakan” temuan yang sudah ada. Setelah lulus Turing mendapat keanggotaan di King’s College (1935).Pada saat ini lah Turing mempunyai konsep mengenai “Mesin Turing”. Melalui sebuah kuliah, di tahun 1935, Turing diperkenalkan pada pertanyaan berkaitan dengan Logika Matematika, yang di ajukan oleh Hilbert. Ini adalah pertanyaan tentang “Decidability”, “the Entscheidungs problem”. “Mungkinkah ada, walau hanya dalam teori, sebuah metode atau proses yang mampu menyelesaikan semua bentuk dan jenis pertanyaan matematika ?”.

Menanggapi pertanyaan ini Turing memberikan solusi mekanikal berupa konsep “Mesin Universal Turing”. Dalam konsep ini turing menggambarkan sebuah mesin yang mampumembaca rangkaian beberapa “nol dan satu” (binary digit) yang akan menjelaskan cara penyelesaian masalah matematika, dan menyediakan jawaban yang dibutuhkan. Inti dari mesin ini yang dikemudian hari dikenal sebagai ide tentang sebuah komputer. Mesin ini masih berupa konsep, sampai kemudian diwujudkan dalam bentuk nyata beberapa tahun kemudian.

Agustus 1936, Turing mengeluarkan paper untuk konsep ini berjudul “On Computable Numbers With an Application to the Entscheidungs problem”. Ditahun yang sama dia mendapatkan “Smith’s Prize” (penghargaan dari Cambridge University) untuk pekerjaannya dalam teori probabilitas dan kemudian melanjutkan ke Princeton University.

Selama perang dunia II(1939-1945), Turing bekerja pada Depertemen Komunikasi Britania Raya. Disana dia ditugaskan untuk memecahkan kode sandi yang diciptakan oleh Mesin Enigma milik pihak Jerman. Ini adalah pekerjaan berat karena mesin ini mampu menghasilkan kode yang berubah secara konstan, dan untuk memecahkannya adalah suatu hal yang mustahil pada zaman itu. Namun ternyata itu tidak mustahil bagi Turing, yang kemudian menciptakan “COLOSSUS”, sebuah mesin yang mampu memecahkan kode enigma dalam waktu singkat. Mesin ini juga merupakan suatu awal menuju Komputer Digital.

Turing juga mempunyai minat yang sangat besar dalam pengembangan “Artificial Intelligence”. Untuk itu dia menghabiskan satu tahun di Cambridge untuk mempelajari Neurologi dan Fisiologi. Di tahun 1947 dia menulis sebuah paper (tidak pernah diterbitkan selama hidupnya) mengenai konsep yang sekarang dikenal dengan “jaringan neural”, dimana serangkaian ssistem kompleks mampu memeliki kemampuan belajar. Kemudian tahun 1950 mengeluarkan paper yang berpengaruh besar berjudul “Computing Machinery and Intelligence”. Dalam papernya ini Turing mengusulkan “Tes Turing” sebagai sebuah metode untuk menentukan apakah sebuah mesin memiliku “Artificial Intelligence”. Hingga tahun 1990-an Tes ini masih dianggap sebagai cara yang paling baik untuk menentukan intelegensia dari sebuah mesin.

Turing juga berusaha untuk mewujudkan konsep “Mesin Turing” menjadi kenyataan dalam bentuk “Automatic Computing Engine” di “National Physical Laboratory”, walaupun pekerjaan ini tidak pernah selesai. Kemudian ia berpindah ke University of Manchester, membuat panduan untuk operasi Manchester Automatic Digital Machine (MADAM).

Turing mempunyai banyak kemampuan. Selain di bidang komputer, Turing juga mengeluarkan paper dalam bidang Biologi, berjudul “The Chemical Basis of Morphogenesis”. Yang mengejutkan, Turing pernah menjuarai kejuaran lari jarak jauh dan menengah di tingkat negara bagian Amerika, dan bahkan nyaris mewakili Amerika di Olimpiade. Ini dilakukannya untuk menghilangkan stress.

Dalam kecerdasan buatan, sebuah agen cerdas (IA) adalah sebuah entitas otonom yang mengamati dan bekerja pada sebuah lingkungan (yaitu ia adalah sebuah agen) dan mengarahkan aktivitasnya ke arah pencapaian tujuan. Intelligent agen mungkin juga belajar atau menggunakan pengetahuan untuk mencapai tujuan mereka. They may be very simple or very complex : a reflex machine such as a thermostat is an intelligent agent, as is a human being, as is a community of human beings working together towards a goal. Mereka mungkin sangat sederhana atau sangat kompleks: sebuah mesin refleks seperti termostat adalah agen yang cerdas, seperti manusia, seperti komunitas manusia bekerja bersama menuju tujuan.

Intelligent agents are often described schematically as an abstract functional system similar to a computer program . Agen cerdas sering digambarkan secara skematik sebagai sistem fungsional abstrak mirip dengan program komputer. For this reason, intelligent agents are sometimes called abstract intelligent agent s (AIA) to distinguish them from their real world implementations as computer systems, biological systems, or organizations. Untuk alasan ini, agen cerdas kadang-kadang disebut agen cerdas abstrak (AIA) untuk membedakan mereka dari dunia nyata implementasi sebagai sistem komputer, sistem biologis, atau organisasi. Some definitions of intelligent agents emphasize their autonomy , and so prefer the term autonomous intelligent agent s.Beberapa definisi agen cerdas mereka menekankan otonomi, dan jadi lebih suka istilah otonom agen cerdas. Still others (notably Russell & Norvig (2003) ) considered goal-directed behavior as the essence of intelligent and so prefer a term borrowed from economics , ” rational agent “.Yang lain (terutama Russell & Norvig (2003)) dianggap perilaku terarah tujuan sebagai esensi dari cerdas dan jadi lebih suka istilah yang dipinjam dari ekonomi, “agen rasional”.

Intelligent agents in artificial intelligence are closely related to agents in economics , and versions of the intelligent agent paradigm are studied in cognitive science , ethics , the philosophy of practical reason , as well as in many interdisciplinary socio-cognitive modeling and computer social simulations. Agen cerdas dalam kecerdasan buatan sangat terkait dengan agen di ekonomi, dan versi dari agen cerdas paradigma yang dipelajari dalam ilmu pengetahuan kognitif, etika, filsafat alasan praktis, juga di banyak interdisipliner sosio-kognitif pemodelan dan simulasi komputer sosial.

Intelligent agents are also closely related to software agents (an autonomous software program that carries out tasks on behalf of users).            Agen cerdas juga berkaitan erat dengan agen perangkat lunak (program perangkat lunak otonom yang melakukan tugas atas nama pengguna). In computer science , the term intelligent agent may be used to refer to a software agent that has some intelligence, regardless if it is not a rational agent by Russell and Norvig’s definition. Dalam ilmu komputer, istilah agen cerdas dapat digunakan untuk mengacu ke agen perangkat lunak yang memiliki kecerdasan, tidak peduli apakah itu bukan agen rasional oleh Russell dan Norvig definisi. For example, autonomous programs used for operator assistance or data mining (sometimes referred to as bots ) are also called “intelligent agents”. Sebagai contoh, program-program otonom digunakan untuk bantuan operator atau data mining (kadang-kadang disebut sebagai bot) juga disebut “agen cerdas

Russell & Norvig (2003) kelompok agen ke dalam lima kelas berdasarkan tingkat kecerdasan dan kemampuan yang dirasakan:

1. simple reflex agents Agen refleks sederhana
2. model-based reflex agents Refleks berbasis model agen
3. goal-based agents Tujuan berbasis agen
4. utility-based agents Utilitas berbasis agen
5. learning agents Agen pembelajaran

TEORI BAHASA & AUTOMATA

Teori Bahasa

Teori bahasa membicarakan bahasa formal (formal language), terutama untuk
kepentingan perancangan kompilator (compiler) dan pemroses naskah (text
processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah
bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama. Sebuah bahasa
formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa
formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya.
Bahasa manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata
yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan
disebut ‘bahasa’ saja.

Automata

Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima
(accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
Automata berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja
secara otomatis (mesin).

Pengertian mesin bukan hanya mesin elektronis/mekanis saja melainkan segala sesuatu (termasuk perangkat lunak) yang memenuhi ketiga ciri di atas. Penggunaan automata pada perangkat lunak terutama pada pembuatan kompiler bahasa pemrograman. Secara garis besar ada dua fungsi automata dalam hubungannya dengan bahasa, yaitu :

1.        Fungsi automata sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam hal ini bahasa sebagai masukan dari automata.

2.        Fungsi automata sebagai pembangkit (GENERATOR) string-string dari suatu bahasa, dalam hal ini bahasa sebagai keluaran dari automata.

Otomata dan Bahasa Formal

Otomata hingga

Otomata hingga melibatkan stata dan transisi antar stata yang merupakan tanggapan atas masukan. Otomata hingga berguna untuk merekayasa perangkat lunak-perangkat lunak tertentu termasuk komponen lexical analyzer yang terdapat pada compiler dan sistem pemeriksa kebenaran pada sirkuit atau protocol.

Automata merupakan suatu studi abstrak yang terdiri dari suatu himpunan tiga tupel yaitu M={S, S, D} dimana S menyatakan state (keadaan); S menyatakan input; dan D menyatakan penentuan keadaan nilai.

Subjek utama dalam tulisan ini adalah mesin sekuensial, sebuah struktur penting yang menjadi dasar dari pirantipiranti, aktivitas, dan proses pengambilan keputusan, terutama yang berhubungan dengan komputer.

Automata merupakan suatu sub struktur utama dari mesin atau proses sekuensial tersebut. Pada mesin sekuensial, suatu proses dibangkitkan oleh masukan tertentu dan menghasilkan keluaran tertentu pula berdasarkan informasi yang dimiliki.
Automata merupakan struktur transisi dari suatu mesin sekuensial, dengan demikian pada dasarnya automata adalah bagian dari suatu mesin sekuensial dengan struktur keluaran yang telah dihapus.

Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu Pemodelan geografis berbasiskan Cellular Automata (CA) dan Multi Agent System (MAS) memiliki kekurangan:

1.      Pada Cellular Automata, automata secara individual dapat menyebarkan informasi, tapi tidak bebas bergerak

2.      Pada Multi Agent System, automata bergerak secara bebas dan mandiri, tetapi mengabaikan sifat-sifat ruang (space) dan keruangan (spasial).

Cellular Automata

Automata merupakan bentuk jamak dari automaton. Automaton adalah suatu mekanisme pemrosesan secara diskrit, berdasarkan keadaan internal dari suatu obyek. Dalam automata, obyek (sel atau agent) memiliki keadaan dan aturan yang menentukan perubahan.

Berikut sifat-sifat dari Automaton:

1.      Berganti keadaan menurut waktu

2.      Sesuai seperangkat aturan

3.      Berdasarkan keadaan internal dan eksternal

4.      Dalam langkah yang berurutan

Ekspresi Reguler

Exspresi regular merupakan notasi structural untuk mendeskripsikan pola-pola yang sama dan dapat diwakili oleh otomata hingga. Exspresi regular digunakan pada berbagai tipe perangkat lunak yang biasa kita gunakan, termasuk perangkat lunak untuk mencari pola-pola dalam texs atau nama file.

Tata Bahasa Bebas-Konteks

Tata bahasa bebas konteks ini merupakan notasi penting yang digunakan untuk mendeskripsikan sruktur bahasa pemograman dan himpunan-himpunan untai yang berhubungan; digunakan untuk membuat komponen parser pada compiler.

Mesin Turing

Mesin turing adalah otomata yang menjadi model computer yang kita kenal saat ini. Mesin turing memungkinkan kita untuk mempelajari decidability, yaitu pertanyaan mengenai apa yang dapat dan tidak dapat dikerjakan oleh computer. mesin ini juga memungkinkan kita menbedakan tractable problem (dapat dipecahkan dalam waktu polynomial) dari intractable problem (tidak dapat dipecahkan dalam waktu polynomial).

Pembuktian Deduktif

Metode pembuktian yang mendasar ini dilakukan dengan cara mendaftar stateman yang diketahui benar atau yang secara logika mengikuti beberapa statemen sebelumnya.

Pembuktian stetemen jika-maka

Banyak teorema memiliki bentuk “jika (sesuatu) maka (sesuatu yang lain)”. Stateman tersebut atau stateman yang mengikuti “jika” merupakan hipotesis dan yang mengikuti “maka” adalah kesimpulan. Pembuktian deduktif statemen jika-maka dimulai dengan hipotesis dan dilanjutkan dengan statemen yang mengikuti secara logika hipotesis dan statemen sebelumnya, hingga kesimpulan dibuktikan sebagai salah satu statemen.

Pembuktian stateman jika dan hanya jika

Ada teorima-teorema yang memiliki bentuk “(sesuatu) jika dan hanya jika (sesuatu yang lain)”. Statemen-statemen tersebut dibuktikan dengan cara statemen “jika-maka” pada kedua arah. Jenis teorema yang sama mengklain kasamaan himpunan-himpunan yang dideskripsikan dengan dua cara yang berbeda.

Pembuktian Kontrapositif

Pembuktian kontrapositif kadang kala, lebih mudah untuk membuktikan statemen “jika H maka C” dengan membuktikan “jika hal dan bukan C maka (sesuatu yang diketahui salah).” Pembuktian dengan cara ini disebut sebagai pembuktian dengan kontradiksi.

Counter example:

Tidak jarang kita diminta untuk menunjukan bahwa suatu statemen tertentu tidak benar. jika statemen memiliki satu atau lebih para meter, makakita dapat menunjukan bahwa statemen tersebut salah sebagai suatu generalisasi dengan menyediakan satu saja counterexample, yaitu suatu penetapan/penyerahan nilai kepada parameter yang membuat statemen tersebut salah.

Pembuktuan Induktif

Statemen yang memiliki parameter bilangan bulat n sering kali dapat dibuktikan dengan induksi pada n. kita membuktikan statemen tersebut benar atau basis, yaitu sejumblah berhingga kasus untuk nilai n tertentu dan kemudian membuktikan langkah induktif: bahwa jika statemen bernilai benar untuk nilai-nilai hingga n, maka ia juga bernilai benar untuk n + 1.

Intruksi Struktural

Pada beberapa situasi, teorema yang akan dibuktika secara induktif teorema mengenai suatu kontruksi yang didefinisikan secara rekursif , misalnya pohon (tree). Kita dapat membuktikan teorema mengenai obyek-obyek yang dikontruksi melalui induksi pada jumblah langkah yang digunakan untuk mengkontruksinya. Jenis intruksi ini dirujuk sebagai structural.

Alfabet

Alphabet adalah sembarang himpunan simbol-simbol.

Untai (string):

Untai adalah deretan simbul-simbul yang panjangnya berhingga.

Bahasa Dan Problema

Bahasa adalah himpunan (bisa jadi himpunan tak hingga) untai-untai, seluruhnya memilih timbulnya dari satu alphabet yang sama. Ketika suatu untai bahasa ditafsirkan denggan suatu cara pertanyaan mengenai apakah untai tersebut berada dibahasanya sering disebut sebagai problema.

Bahasa suatu Automata

Otomaton menerima untai-untai. Suatu untai diterima jika sejak dari stata mula, alihan yang disebabkan oleh pemrosesan sombol-simbol untai-untai tersebut. diagram alihan, untai diterima jika terdapat label lintasan dari stata mula kesuatu stata penerima.

Kontruksi himpunan bagian

Dengan memperlakukan himpunan stata NFA sebagai stata suatu DFA, kita dapat mengkonfersi sembarang NFA menjadi DFA penerima bahasa yang sama.

Teori Bahasa Automata Dalam Ilmu Komputer

Suatu teori hanya menarik jika dapat membantu dalam mencari solusi terbaik. Tanpa penerapan timbul pertanyaan, mengapa mempelajari teori? Teori memberikan konsep dan prinsip yang menolong untuk memahami perilaku dari suatu persoalan yang berkorelasi dengan teori tersebut. Bidang ilmu komputer meliputi topik yang luas, dari perancangan mesin sampai pemrograman.

Disamping perbedaan yang ada, terdapat keseragaman prinsip-prinsip umum yang dipakai. Untuk mempelajari prinsip-prinsip dasar tersebut, kita mengkonstruksi suatu mesin otomata sebagai model abstrak dari komputer dan komputasi.

Teori bahasa membicarakan bahasa formal (formal language), yang terdiri dari kumpulan kalimat. Sebuah kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama oleh dua atau lebih tata bahasa yang berbeda terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor).

Bahasa dalam hal ini berisi semua string yang dapat dihasilkan menggunakan aturan-aturan grammar yang mempunyai nilai/ manfaat sangat besar di ilmu informatika/ computer karena untuk mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa-bahasa formal lain dan dapat diterapkan pada perancangan kompilator.

Teori otomata merupakan kajian mengenai perangkat komputasi abstrak atau bisa dikatakan mesin abstrak. Teori menyediakan konsep-konsep dan prinsip-prinsip yang dapat membantu kita memahami sifat umum suatu bidang kajian yang berkaitan dengan Automata.

Sedangkan otomata (Automata) adalah suatu sistem yang terdiri atas sejumlah berhingga state yang mempelajari tentang mesin abstrak yang menerima input dan mengeluarkan output dalam bentuk diskret (satu per satu).

Dimana state adalah suatu kondisi yang menyatakan informasi mengenai input yang lalu sedangkan input pada otomata dianggap sebagai batas yang harus dikenali oleh mesin.