Mesin Turing (Turing Machine)

Sejarah Mesin Turing

Mesin Turing ini diusulkan pada tahun 1936 oleh Alan Turing, seorang matematikawan Inggris sebagai model matematis sederhana sebuah komputer.

Meskipun sederhana, Mesin Turing memiliki kemampuan untuk menggambarkan perilaku komputer general-purpose.

Mesin Turing dapat digunakan untuk menghitung kelas fungsi bilangan bulat yang dikenal sebagai fungsi rekursif sebagian (partial recursive function).

Sama seperti Finite State Automata dan Push Down Automata yang dapat mengenali bahasa formal, maka mesin Turing juga dapat berperan sebagai mesin pengenal bahasa formal.

Bahasa yang dikenali oleh Mesin Turing adalah bahasa tanpa-pembatasan (non-restricted language), yang disebut juga himpunan terenumerasi rekursif (recursively enumerable set).

Alan Turing - Penemu Mesin Turing

Finite State Automata (FSA), Deterministic Finite Automata (DFA), Non Deterministik Finite Automata (NFA)

Finite State Automata (FSA)

Finite state automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.

Push Down Automata (PDA)

Pengertian Push Down Automata

PDA adalah mesin otomata yang memiliki kendali masukan menggunakan teknik LIFO (Last In First Out), untuk menentukan apakah suatu output diterima atau tidak oleh mesin tsb. Dalam melakukan proses peneerimaan input, PDA menggunakan memory stack.

Linear Bounded Automata (Linear Bounded Automaton)

Sejarah Linear Bounded Automata

Pada tahun 1960, John Myhill memperkenalkan model Automata yang sekarang dikenal sebagai deterministik Linear Bounded Automaton. Pada tahun 1963, Peter S. Landweber membuktikan bahwa bahasa yang diterima oleh LBA deterministik peka terhadap konteks. Pada tahun 1964, S.-Y. Kuroda memperkenalkan model automata terbatas linier (nondeterministik) yang lebih umum, mencatat bahwa bukti Landweber juga berfungsi untuk automata terikat linier nondeterministik, dan menunjukkan bahwa bahasa yang diterima oleh mereka adalah bahasa yang peka konteks.

John Myhill