Model-Model Komputasi

Dibawah ini adalah contoh penerapan dari Model Komputasi, diantaranya :

1. Mesin Mealy
Dalam teori komputasi sebagai konsep dasar sebuah komputer, mesin Mealy adalah otomasi fase berhingga (finite state automaton atau finite state tranducer) yang menghasilkan keluaran berdasarkan fase saat itu dan bagian masukan/input. Dalam hal ini, diagram fase (state diagram) dari mesin Mealy memiliki sinyal masukan dan sinyal keluaran untuk tiap transisi. Prinsip ini berbeda dengan mesin Moore yang hanya menghasilkan keluaran/output pada tiap fase.
Nama Mealy diambil dari "G. H. Mealy" seorang perintis mesin-fase (state-machine) yang menulis karangan "A Method for Synthesizing Sequential Circuits" pada tahun 1955.
Mesin Mealy dinyatakan dengan 6-tuple (Q, Σ, Δ, δ, λ, q0), dimana:
- Q:himpunan berhingga status.
- Σ: himpunan berhingga simbol alfabet.
- Δ: himpunan simbol keluaran (alfabet keluaran).
- δ : fungsi transisi yang memetakan Q x Σ ke Q.
- λ: fungsi yang memetakan Q x Σ ke Δ, λ(q,a) memberikan keluaran yang diasosiasikan dengan transisi dari q thd simbol keluaran a.
- q0: status awal, anggota Q.

Keluaran mesin Mealy terhadap masukan a1 a2…an≥n adalah λ(q0,a1) λ(q0,a1) λ(q1,a2) … λ(qn-1,an) dimana q0, q1,…,qn-1 adalah barisan status sedemikian sehingga δ(qi-1,ai) = qi untuk 1≤i≤n. Jika string masukan ε, mesin Mealy memberikan keluaran ε.

2. Mesin Moore
Dalam teori komputasi sebagai prinsip dasar komputer, mesin Moore adalah otomasi fase berhingga (finite state automaton) di mana keluarannya ditentukan hanya oleh fase saat itu (dan tidak terpengaruh oleh bagian masukan/input). Diagram fase (state diagram) dari mesin Moore memiliki sinyal keluaran untuk masing-masing fase. Hal ini berbeda dengan mesin Mealy yang mempunyai keluaran untuk tiap transisi.
Nama Moore diambil dari "Edward F. Moore" seorang ilmuwan komputer dan perintis mesin-fase (state-machine) yang menulis karangan "Gedanken-experiments on Sequential Machines".
Mesin Moore dinyatakan dengan 6-tuple (Q,Σ, Δ, δ, λ, q0), dimana:
-  Q:himpunan berhingga status.
-  Σ: himpunan berhingga simbol alfabet.
-  Δ: himpunan simbol keluaran (alfabet keluaran).
-  δ : fungsi transisi yang memetakan Q x Σ ke Q.
-  λ: fungsi yang memetakan Q ke Δ, memberikan
keluaran yang diasosiasikan dengan tiap status.
-  q0: status awal, anggota Q.

Keluaran mesin Moore terhadap masukan a1 a2…an≥n adalah λ(q0)λ(q1)…λ(qn) dimana q0, q1,…,qn adalah barisan status sedemikian sehingga δ(qi-1,ai) = qi untuk 1≤i≤n. Jika string masukan ε, mesin Moore
memberikan keluaran λ(q0)

3. Petri Net

Petri net adalah salah satu model untuk merepresentasikan sistem terdistribusi diskret. Sebagai sebuah model, Petri net merupakan grafik 2 arah yang terdiri dari place, transition, dan tanda panah yang menghubungkan keduanya. Di samping itu, untuk merepresentasikan keadaan sistem, token diletakkan pada place tertentu. Ketika sebuah transition terpantik, token akan bertransisi sesuai tanda panah. Petri net pertama kali diajukkan oleh Carl Adam Petri pada tahun 1962.  Sebuah Petri net (juga dikenal sebagai tempat / net transisi atau P / net T) adalah salah satu dari beberapa bahasa pemodelan matematika untuk deskripsi sistem terdistribusi. Sebuah Petri net adalah grafik bipartit diarahkan, di mana node merupakan transisi (yaitu peristiwa yang mungkin terjadi, ditandai dengan batang), tempat (kondisi yaitu, ditandai dengan lingkaran), dan busur diarahkan (yang menggambarkan tempat-tempat yang merupakan pra-dan / atau postconditions untuk yang transisi, ditandai dengan panah). jala Petri diciptakan pada bulan Agustus 1939 oleh Carl Adam Petri – pada usia 13 – untuk tujuan menjelaskan proses kimia.

Seperti standar industri seperti diagram aktivitas UML, BPMN dan EPCs, jala Petri menawarkan notasi grafis untuk proses bertahap yang mencakup pilihan, iterasi, dan eksekusi konkuren.Tidak seperti ini standar, jala Petri memiliki definisi matematis pasti dari semantik eksekusi mereka, dengan teori matematika berkembang dengan baik untuk analisis proses.

Petri jaring dasar-dasar

Sebuah Petri net terdiri dari tempat, transisi, dan busur diarahkan. Busur lari dari tempat untuk sebuah transisi atau sebaliknya, tidak pernah diantara tempat-tempat atau antara transisi.Tempat dari mana sebuah busur berlari untuk transisi disebut tempat input transisi; tempat-tempat yang busur lari dari transisi disebut tempat keluaran transisi.  Tempat mungkin berisi sejumlah alami token. Sebuah distribusi token atas tempat jaring disebut menandai. Sebuah transisi dari Petri net dapat api setiap kali ada tanda di akhir semua busur input; ketika kebakaran, mengkonsumsi bukti tersebut, dan tempat-tempat tanda di akhir semua busur output. pembakaran adalah atom, yaitu sebuah langkah non-interruptible tunggal.

Pelaksanaan jala Petri adalah nondeterministic: ketika beberapa transisi akan diaktifkan pada saat yang sama, salah satu dari mereka mungkin api. Jika transisi diaktifkan, mungkin api, tapi tidak harus. Sejak pembakaran adalah nondeterministic, dan mungkin beberapa token hadir di mana saja (bahkan di tempat yang sama) bersih, Petri jaring sangat cocok untuk pemodelan perilaku bersamaan sistem terdistribusi.

Definisi formal dan terminologi dasar

Definisi formal berikut ini secara longgar didasarkan pada (Peterson 1981). Banyak alternatif definisi ada. Sebuah grafik Petri net (disebut Petri net oleh beberapa, tapi lihat di bawah) adalah 3-tupel, di mana
S adalah himpunan berhingga tempat
T adalah himpunan berhingga transisi
S dan T adalah memisah, yaitu objek tidak dapat menjadi tempat dan transisi adalah multiset dari busur, yakni mendefinisikan busur dan memberikan kepada setiap busur keserbaragaman sebuah integer non-negatif busur, perhatikan bahwa tidak ada busur dapat menghubungkan dua tempat atau dua transisi.  Hubungan arus adalah himpunan busur:. Dalam banyak buku teks, busur hanya dapat memiliki bermacam 1, dan mereka sering menentukan Petri jaring menggunakan F bukannya W.  Sebuah grafik Petri net adalah multidigraph bipartit dengan partisi node S dan T.  Preset dari t transisi adalah himpunan tempat input:; postset adalah himpunan tempat outputnya:. Definisi pre-dan postsets tempat yang analog.  Sebuah tanda dari Petri net (grafik) adalah multiset wilayah operasional, yaitu pemetaan. Kami mengatakan menugaskan untuk menandai setiap tempat sejumlah token.  Sebuah Petri net (disebut ditandai Petri bersih dengan beberapa, lihat di atas) adalah 4-tupel, di mana (S, T, W) adalah grafik Petri net;  M0 adalah tanda awal, tanda dari grafik Petri bersih.