CATATAN TENTANG BATAS BAHASA

BISMILLAH:
Review:CS 301 – Lecture 23, Recursive and Recursively Enumerable Languages
.
(1).
Definition:
A language is recursively enumerable
if some Turing machine accepts it
.
mesin turing dapat kita lihat juga sebagai mesin pencacah.
mengapa?
karena dia memetakan setiap langkah-langkah komputasi ke dalam bilangan asli.
disana dia menyediakan set instruksi untuk mencacah langkah-langkah sebagai transisi-transisi state, entah nantinya pencacahan itu menghasilkan halt, fail atau looping forever.
.
recursively enumerable, artinya, terdapat langkah-langkah algoritma dalam cacahan bilangan asli untuk menyelesaikan suatu input.
.
(2).
Definition:
A language is recursively enumerable
if some Turing machine accepts it
.
Definisi ini memiliki arti bahwa:
Jika L bahasa yang recursively enumerable
dan M adalah mesin turing yang menerima/generate L
maka:
jika w di L maka w diterima M dan M halt di final state.
jika w bukan di L maka w diproses M tetapi M berakhir di non-final state atau loop forever.
.
(3).
Definition:
A language is recursive
if some Turing machine accepts it
and halts on any input string
.
artinya bahwa misal L bahasa yang recursive (tidak sampai recursively enumerable) maka ada sejumlah mesin turing yang menerima L, dan halt pada setiap string input.
entah halt pada final state atau non-final state, tetapi tidak pernah looping forever.
.
ini menunjukkan bahwa setiap mesin turing M yang menerima L, tidaklah terlalu rumit, tidak sedemikian sehingga dia memiliki struktur yang bisa looping forever.
.
tetapi jika ada M yang bisa looping forever maka mestilah bahasa L yang diwakilinya adalah tidak sekedar recursive tetapi juga recursively enumerable.
.
[Turing acceptable languages?]
[Enumeration Procedures?]
enumerate strings = mencacah string dalam artian membangun hitungan bilangan asli, tetapi dalam arti string maka itu adalah berarti mengenerate string dari sejumlah karakter dasar.
.
misal diberikan {a,b}
maka dicacah sebagai berikut:
a
b
ab
ba
aa
bb
aab
…. dst.
.
mesin pencacah string (enumeration machine) = mesin yang mengenerate string + mesin yang memilih hasil cacahan
.
[Rangkuman cara pembuktian]
Teorema 1:
Untuk setiap bahasa rekursif L terdapat mesin enumerasi yang dapat mencacah L
Atau:
Untuk setiap bahasa rekursif L terdapat prosedur enumerasi yang dapat mencacah L
Atau:
Untuk setiap bahasa rekursif L terdapat algoritma enumerasi yang dapat mencacah L
.
Bukti:
buat mesin E yang melakukan enumerasi acak pada seluruh alphabet L.
E mengenerate seluruh string yang mungkin dari alphabet tersebut.
.
tetapi L adalah bahasa rekursif, maka itu berarti ada mesin turing M yang jika menerima string yang termasuk dalam L maka M halt di final state.
dan jika menerima string yang bukan dari L maka M halt di non-final state.
.
konstruksikan mesin enumerasi khusus untuk L (bukan mesin enumerasi umum seperti E) dengan cara buat E dan M serial, yaitu E menerima input berupa semua alphabet L, lalu mengenerate semua string yang mungkin, lalu outputnya berupa setiap string hasil generasi, lalu output itu diberikan ke M, M akan memeriksanya, jika diterima maka M memberikan output atau mencetak string tersebut, jika tidak maka string itu tidak dioutputkan, tetapi diabaikan.
maka diperoleh mesin enumerasi khusus untuk L sebagai berikut:
.
mesin enumerasi khusus untuk L:
mesin EM = alphabet L –> E –> cacahan acak E –> M –> string L
.
dalam ekspresi prosedur enumerasi atau algoritma enumerasi yaitu:
E menerima alphabet L.
Repeat:
E mengenerate string w yang mungkin dari cacahan kombinasi alphabet L.
M mengecek string w tersebut, jika elemen L maka w dijadikan output/diprint
jika w bukan elemen L, maka w diabaikan.
.
teorema terbukti.
q.e.d.
.
.
Teorema 2:
Untuk setiap bahasa L yang recursive enumerable terdapat mesin enumerasi untuknya.
Atau:
Untuk setiap bahasa L yang recursive enumerable terdapat prosedur enumerasi untuknya.
Atau:
Untuk setiap bahasa L yang recursive enumerable terdapat algoritma enumerasi untuknya.
.
Bukti:
Bukti analogi di atas, tetapi mesin turing M didefinisikan lain agar dapat menangani keluaran E yang dapat menyebabkan M looping forever.
.
M didefinisikan bekerja/mencacah atau melangkah sebagaimana proses mencacah bilangan pecahan.
.
q.e.d.
.
.
Teorema 3:
Untuk setiap bahasa L yang dapat digenerate oleh mesin enumerasi E maka L adalah bahasa yang recursively enumerated.
Bukti:
untuk membuktikan bahwa L adalah recursively enumerated maka harus dibuktikan bahwa terdapat mesin turing yang dapat menerima L.
.
buat sebuah pita dimana string w milik L ditempatkan.
buat mesin turing dengan struktur sebagai berikut:
sebut mesin turing itu adalah EK, EK terdiri dari E dan sebuah komparator K.
ketika K membaca w pada pita, K membandingkan setiap keluaran E (bkerja looping) dengan w. jika keluaran E sama dengan w maka mesin EK menerima w.
.
diperoleh bahwa mesin turing EK adalah mesin turing yang menerima seluruh string L
.
Tetapi apakah L recursive?
misalkan L recursive maka L juga recursive enumerable.
.
teorema terbukti, bahwa L revursively enumerable.
.
tetapi misal dia recursively enumerable, maka secara langsung teorema terbukti juga.
.
q.e.d.
.
.
#IDE1:
mesin turing yang bekerja mencacah seperti mencacah bilangan rasional/pecahan dapat digambarkan sebagai berikut:
sebuah pita yang panjangnya infinite.
ketika sebuah word1 masuk, head1 langsung membaca karakter pertama word1, instruksi dijalankan, lalu masuk langkah kedua, word2 diterima masuk ditempatkan serial pada pita, dan head langsung membaca karakter pertama word2 dan instruksi dieksekusi, tetapi terlebih dahulu catatan sejarah eksekusi instruksi untuk word1 disimpan pada pita kedua, lalu catatan sejarah instruksi untuk word2, dan setersunya. jalannya instruksi seperti membaca susunan matrik konstruksi bilangan rasional/pecahan, dibaca secara silang atau zig-zag.
#END IDE1.
.
mesin enumerasi atau prosedur enumerasi atau algoritma enumerasi = mesin yang bisa mendaftar atau melist seluruh isi sebuah bahasa.
.
enumerable = countable(?).
recursively enumerable = secara recursif dan countable(?).
.
teorema 4:
Disana terdapat bahasa yang bukan merupakan bahasa yang recursively enumerable.
Bukti:
Ambil sebuah alphabet E={a}
.
konstruksikan sebarang bahasa dari E, misal:
G1={a}
G2={aa}
G3={aaa}
dan seterusnya, atau suatu kombinasi dari a^n menjadi Li={aa,aaa,aaaaaa} dan seterusnya.
.
misal diperoleh himpunan bahasa {G1,G2,G3,…}
.
secara umum konstruksi sebuah barisan bahasa-bahasa baru berdasarkan {G1,G2,G3,…}.
misal Li={G1}U{G3}U{G6} = {aa,aaa,aaaaaa}, yang merupakan analogi dari powerset yang dibentuk dari {G1,G2,G3,…}.
.
kemudian secara berurut diperoleh L1,L2,L3,….
.
susun dalam tata cara pembuktian bahwa powerset dari bilangan asli adalah uncountable.
yaitu dengan membuat kolom2 L1,L2,L3,… dan baris-baris L1(M1), L(M2), L(M3),… untuk setiap bahasa Li yang diassumsikan recursively enumerable sehingga untuk setiap bahasa Li ada Mi mesin turing yang menerimanya.
.
kemudian enkoding untuk setiap Li dengan suatu koding biner.
lalu diperoleh susunan matriks koding untuk seluruh kolom Li dengan baris L(Mi).
.
ambil diagonal matriks, maka diagonal ini menyatakan suatu bahasa Lk yang berpadanan dengan suatu Mk mesin turing.
.
buat negasi dari koding Lk, diperoleh suatu bahasa ~Lk yang merupakan negasi koding dari LK.
.
misalkan ~Lk adalah suatu bahasa yang enumerable juga.
.
maka mestilah enkoding ~Lk terdaftar dalam matriks, akan tetapi dia adalah negasi diagonal matriks, sehingga disana ada bit yang merupakan negasi dirinya sendiri.
.
ini kontradiksi karena tidak mungkin 0=1 atau 1=0 dalam enkoding.
.
maka ~Lk tidak mungkin terdaftar dalam matriks enkoding dari selurh bahasa rekursively enumerable.
.
maka tidak mungkin ada mesin turing Mt yang bisa menerima ~Lk.
.
maka ~Lk adalah bukti bahwa ada bahasa yang yang bukan merupakan bahasa yang recursively enumerable.
.
Ini berarti, bahasa memiliki wilayah lebih luas dari mesin turing.
yang berarti juga bahwa kemampuan komputasi kita terbatas ke dalam bahasa yang countable (enumerable).
.
——————————————————————————————
Bagaimana mereka membuktikan bahwa terdapat bahasa yang tidak dapat diterima oleh mesin turing? atau gramatikanya tidak dapat direpresentasikan oleh mesin turing?
——————————————————————————————
[embed-review:https://en.wikipedia.org/wiki/Unrestricted_grammar%5D
(1).
unrestricted grammars characterize the recursively enumerable languages.
.
yaitu bahwa suatu set aturan produksi yang memiliki susunan gramatika ß ? ? yang unrestricted adalah dapat merumuskan atau merepresntasikan sebarang bahasa yang recursively enumerable.
.
pernyataan di atas dibuktikan dengan menunjukkan bahwa gramatika yang unrestricted adalah selalu dapat disimulasikan oleh mesin turing.
dan sebaliknya bahwa sebarang mesin turing dapat dinyatakan oleh sebuah gramatika unrestricted.
karena definisi bahasa yang recursively enumerable adalah sebarang bahasa yang dapat direpresentasikan oleh mesin turing, ini berarti gramatika unrestricted juga dapat menyatakan sebuah bahasa yang recursively enumerable.
.
(2).
Konstruksi mesin turing untuk suatu aturan produksi ß ? ? dimana tak ada batasan bagaimana menempatkan non-terminal atau terminal, adalah sebagai berikut:
.
.
[embed-review:https://en.wikipedia.org/wiki/Formal_grammar#sentential-form%5D
Grammar adalah sebuah sintaks
Bahasa adalah semantik dari grammar.
.
setiap elemen dari bahasa adalah sentence, yaitu hasil akhir penurunan semantik dari gramatika yang berupa seluruhnya terminal (tak ada non-terminal).
karenanya, setiap sentence adalah sebuah nilai semantik.
dan karenanya, bahasa sebagai set of sentence adalah juga sebuah semantik.
.
misal kita mendefinisikan bahasa L sebagai sebuah himpunan, contoh L={a^n.b^n: a,b elemen alphabet dan n integer bulat positif}, definisi seperti ini adalah definisi semantik.
karena a^n.b^n adalah sebuah nilai semantik.
.
operasi semantik secara umum sebuah bahasa adalah =G=>, dimana G adalah gramatika.
x=G=>y = ada u,v,p,q elemen set non terminal N gabung set terminal E dimana berlaku:
(x=upv)dan(p=>q elemen P gramatika)dan(y=uqv)
.
operator =G=> bersifat reflexive (x=G=>x), transitif (x=G=>y dan y=G=>z maka x=G=>z) dan closure (x=G=>y maka y elemen L).
.
dari operator =G=> orang mengkonstruksikan =G*=> yaitu ringkasan dari langkah =G=> dalam jumlah langkah nol hingga berhingga langkah (finite).
.
sentential form = segala bentuk string hasil penurunan sesuai garmatika.
.
sentential form bukanlah himpunan semantik karena mungkin masih ada bentuk non terminl dalam string.
.
tetapi bhasa L adalah himpunan sentential yang sudah jadi sentence (tampa ada non terminsal) maka disebut semantiknya.
.
bahasa jika ditulis dalam bentuk operator semantik, maka:
L = {w elemen E*|S=G*=>w}.
.
[?]Apa arti rinci dari gramatika, aturan produksi dan language?
Secara matematika, gramatika adalah sebuah tupel.
yaitu:
gramatika G = (N,E,P,S)
aturan produksi = rule = P
language = himpunan sentence = {sentence w|dimana S=G*=>w} = {…} sebarang definisi himpunan yang sesuai.
.
jadi sebenarnya yang setara dengan mesin turing atau automata, bukanlah P aturan produksi, tetapi G. ingat itu lan.
.
bukan juga bahwa yang setara dengan bahasa L adalah mesin turing M tetapi G dari L yang setara dengan mesin turing M.
ini secara matematika ditulis:
bukan L setara M tetapi L(G)=L(M) sehingga G setara M.
.
suatu bahasa yang dibangun oleh G ditulis L(G). bukan L(P).
suatu bahas yang dibangun oleh M ditulis L(M).
.
[embde-review:https://en.wikipedia.org/wiki/Semi-Thue_system%5D
[?]Apa beda Thue system dengan semi thue system?
pada semi thue system (E,R).
R hanya bersifat reflexive transitif clousure.
tetapi pada Thue system, R bersifat symetric reflexive transitif clousure.
ada tambahan symetric.
.
[?]Apa beda semi-thue system, abstrac rewriting system dengan G?
semi-Thue system, Thue system = hanyalah sebuah sistme aljabar, yang melihat R semata relasi dalam aljabar dan suatu proses reduksi ekspresi aljabar berjalan berdasarkan R.
tetapi melihat elemen2 nya adalah string, suatu sistem aljabar bagi string, ditujukan untuk memecahkan masalah monoid dalam aljabar(?).
.
tetapi abstrac rewriting system = adalah sebuah sistem rewriting untuk string-string, sistem rewriting menggunakan R untuk mengenerarate konsep rewriting rule yaitu “==>”.
dimana sebuah sistem dapat ditulis ulang menggunakan “==>”.
.
tetapi “==>” diinduksi oleh R, artinya bahwa proses rewriting di guide atau dilakukan berdasarkan ekspresi R, sehingga ini dtulis orang sebagai =R=>.
.
G sendiri adalah sebuah abstract rewriting system, hanya bedanya, G menempatkan secara khusus S sebagai start segala proses rewriting. atau memilih S sebagai s0, dan G hanya bekerja di atas E, tetapi abstract rewriting system adalah di atas E*.
.
sedang abstract rewriting system adalah sembarang memilih start untuk proses rwriting.
.
G sendiri karena abstract rewriting system adalah sebenarnya suatu semi thue system, maka G sendiri adalah juga sebenarnya adalah suatu semi thue system.
.
Akan tetapi “==>” dapat melakukan sebarang rewriting tanpa R, karenanya itulah sebabnya orang menulis bahwa R adalah subset dari “==>”.
atau bahwa “=R=>” adalah subset dari “==>”.
.
[?]Apa hubungan antara UTM dengan semi thue system?
cara kerja UTM, mungkin didefiniskan orang menuruti cara kerja semi thue system atau abstract rewriting system.
.
artinya bahwa UTM mengenkoding seluruh automata atau sebarang mesin atau gramatika, ke dalam sebuah semi thue system. lalu mengeksekusi/mensimulasikannya dengan cara menjalanakan semi thue system tersebut.
.
pertanyaanya?
bagaimana mengenkoding timed-automata ke dalam semi thue system?
.
[?]Bagaimana kita melihat ekspresi running sebuah mesin turing/automata ke dalam ekspresi rewriting rule?
yaitu dengan melihat perubahan instruksi ke instruksi lain sebagai proses rewriting rule.
.
tetapi mungkin ini bukanlah cara yang fix.
.
kita dapat melihat proses running bukan sebagai ekspresi proses rewriting rule.
.
.
#IDE:
The word problem for semi-Thue systems can be stated as follows: Given a semi-Thue system T := ( S , R ) {\displaystyle T:=(\Sigma ,R)} T:=(\Sigma ,R) and two words (strings) u , v ? S * {\displaystyle u,v\in \Sigma ^{*}} u,v\in \Sigma ^{*}, can u {\displaystyle u} u be transformed into v {\displaystyle v} v by applying rules from R {\displaystyle R} R? This problem is undecidable, i.e. there is no general algorithm for solving this problem.
.
ini menjelaskan bahwa kita tidak dapat memechkan masalah secara umum bahwa sebarang string selalu dapat diedit untuk emnghasilkan string lain.
#END IDE.
——————————————————————————————
[embde-review:Mastering recursive programming,Learning recursion yields maintainable, consistent, provably correctcode,Jonathan Bartlett,June 16, 2005]
.
(1).
Buku ini menyajikan suatu proof of concept bahwa konsep mesin rekursif dapat diimplementasikan ke dalam algoritma, tepatnya ke dalam koding, membangun konsep atau cara pandang atau paradigma pemrograman baru, yaitu pemrograman rekursif.
dalam cara pandang ini, segala hal dalam program dikerjakan secara rekursif.
.
(2).
Konsep dasar atau dasar intuitif dari gagasan ini adalah ekspresi rekursif fungsi faktorial yang dinyatakan secara rekursif:
bentuk dasarnya adalah:
fungsi f(argumen) {
ekspresi kapan rekursif berhenti.
ekspresi rekursif.
}
.
——————————————————————————————
[embed-review:https://en.wikipedia.org/wiki/Compiler%5D
mengapa interpreter yg kamu buat dapat disebut compiler, karena menerjemahkan bahasa reguler ke pemetaan satu ke satu yang yanpa gramatika.
atau gramatikanya hanyalah sebuah tabel pemetaan.
.
——————————————————————————————
[Artikel]
#Tentang bagaimana cara membuktikan via komputasi bahwa konstruksi sebuah teori tunggal untuk menjelaskan seluruh peristiwa alam adalah tidak mungkin (ketidakmungkinan konstruksi grand unified theory, GUT)?

.
Dalam artikel ini, tidaklah saya bermaksud mengemukakan sebuah jalan bukti yang rigid, karena rasanya, begitu banyak cara kerja pengetahuan yang rinci yang belum dapat sya pahami. Akan tetapi, membiarkan gagasan kita menua dalam pikiran, melemah dan hilang karena banyak hal yang lebih mendasar harus kita kerjakan dan dahulukan, rasanya seperti hantu yang
.
alam semesta dengan waktu yang tidak simetri (entropy tidak dapat berbalik ke masa lalu) kita hampiri dengan sebuah graph berarah berdimensi tak hingga yang tidak ada siklus di dalamnya (directed acyclic graph). Pendahulun gagasan tentang graph ini telah saya kemukakan pada artikel sebelumnya dalam akun ini ketika membahasa tentang lambda calculus.
.
tak ada fraktal yang bisa memodelkan segala entiti di alam semesta.
[End artkel]
.
[Artikel]
#Pandangan filosofis dan penurunan rumus-rumus decision three dari gagasan entropy shannon.
.
Tentang bagaimana cara orang menurunkan rumus2 decision three (ID3, C4.5, dsb) bermula secara filosofis dari konsep entropy shannon.
.
dataset –> DAG –> pemilihan atribut output –> entropy dataset beerdasarkan pemilihan atribut output.
[End artikel]
.
[Artikel]
Tentang bagaimana cara merumuskan alam semesta yang time asimetri menggunakan timed-DAG.
[End artikel]
.
[Artikel]
{a,b,c}, M konstruk theorem then there is a set of axiom where M cannot construct theorem.
[Artikel]
for every x element A, x is tautologi, where A is a line.
.

——————————————————————————————
[continu-review:https://plato.stanford.edu/entries/recursive-functions/#1.1%5D
(1).
As an example,
.
consider the function f which maps any 3 numbers as argument to the successor of the second argument.
.
We can define this function by composition from initial functions. In this case, let g in the above definition be the successor function s and let h in the above definition be the projection function p2. Then,

TINJAU SEKILAS KERJA RAJEEV

BISMILLAH:
.
#REVIEW1:
Review: http://www.cis.upenn.edu/~alur/nw.html (diakses tgl 29 nov 2017).
.
What are nested words?
Nested words is a model for representation of data with both a linear ordering and a hierarchically nested matching of items.
.
Data yang dimaksud disini adalah dataset atau source code.
Tetapi secara umum adalah himpunan string yang linier ordered atau hierarchial nested matching.
.
#inspirasi1
Ini memberi pengetahuan implisit bahwa:
Sebarang susunan kalimat program, dapat direpresentasikan ke dalam latiks dengan bentuk:
a linear ordering atau
a hierarchically nested matching.
.
Ini juga memberi pengetahuan juga bahwa:
Sebarang bahasa pemrograman dapat direpresentasikan dalam bentuk graph berarah yang linier ordered atau hierarchial nested matching.
.
Bagaimana filosofi hierarchial nested matching?
Bismillah:
Pertama:
(Pengertian hierarki dalam string).
Sebuah untai string adalah sebuah linier string.
Linier string pertama adalah sebuah string root, atau string level 0.
Kemudian pada sebuah pasangan karakter yang matching berpasangan sebagai begin-end atau call-result atau open-close tag, terdapat nested, maka nested itu adalah string level 1.
pada string level 0, mungkin terdapat n_1 buah pasangan matching, maka pada string 0, terdapat n_1 buah nested yang merupakan n_1 buah string level 1.
.
Tetapi pada setiap string level 1, mungkin masing-masing terdapat nested lagi, misal masing-masing memiliki m_n_i nested, maka seluruh nested tersebut adalah string level 2, dan seterusnya, sebuah string bisa mencapai string level k.
.
demikian sehingga sebarang nested word, adalah sebuah word yang mengandung nested string hingga level k. tetapi smeuanya bisa ditulis dalam satu baris 1, tetapi disana setiap nested ditandai oleh sebuah karakter matching.
.
Kedua:
(Cara bagaimana merepresentasikan nested word ke dalam sebuah grapah berarah)
Sebuah node = sebuah keyword atau kata tercadang atau simbol khusus atau sebarang kata yang sah di dalam bahasa pemrograman X tertentu.
.
Sebuah tali (edge) antara node dibentuk berdasarkan prinsip:
jika sebuah kata (keyword) atau simbol khusus berjarak 1 kata (atau 1 simbol khusus) dengan kata (atau simbol khusus) lain dalam level yang sama, maka kedua kata itu membentuk sebuah tali (edge).
.
#end inspirasi1.
.
#IDE 1:
Kita mungkin membangun sebuah mesin AI beruapa jaringan syaraf tiruan atau bayes network yang dapat mengkonstruksikan sebuah linier ordered atau hierarchial nested matching.
dimana dia mengkonstruksikan sebuah program.
.
ini juga memungkinkan kita mengajari mesin untuk memecahkan masalah dengan membangun snipet2 atau potongan2 kode yang memecahkan masalah tersebut.
.
Kemudian kita dapat membuat automata yang memeriksa keabsahan program yang dibuat oleh mesin tersebut dengan cara sebagai berikut:
(1).
Buat himpunan snipet yang absah atau tidak error atau bebas celah atau kumpulkan dari berbagai sumber snipet2 tersebut.
(2).
Terjemahkan setiap snipet ke dalam nested word.
Kumpulkan seluruh nested word menjadi sebuah bahasa.
Bangun sebuah automata atau grammar yang menerima bahasa tersebut.
.
Lalu biarkan mesin mengkonstruksikan sebarang nested word.
Lewatkan ke dalam automata.
.
Setiap nested word yang lolos maka diterima sebagai snipet yang dibuat oleh mesin AI.
.
Snipet bisa berisi operasi-operasi dasar atau task-task dasar dalam sebuah konstruksi program.
.
Sehingga jika sebuah program dibangun maka mesin cukup merangkai snipet2 tersebut.
Keabsahan sebuah program diuji dengan menerjemahkan program ke dalam nested word lagi, lalu melewatkan ke dalam automata.
.
automata untuk setiap word di dalam setiap nested tunggal di bentuk berdasarkan gramatika bahasa X dimana himpunan nested word dibangun.
.
automata untuk himpunan nested wordnya, atau suatu nested word adalah nested automata, yaitu automata yang bila menemui karakter matching maka dia melompat ke automata lain atau ke sub automata atau ke automata dirinya sendiri.
(3).
Cara konstruksi node dan tali suatu bahasa X.
LIHAT DI ATAS padabagian inpsirasi1.
(4).
Cara konstruksi snipet/program:
mesin membuat secara acak nested word.
diperoleh sebuah semesta nested word.
.
lalu mesin menguji setiap nested word menggunakan set automata (yang diambil dari gramatika bahasa X).
diperoleh subhimpunan semesta newsted word yang valid.
.
lalu berdasarkan suatu metrik (misal himpunan metrik yang berdasarkan konsep entropy) mengevaluasi seluruh nested word yang valid.
diperoleh set nested word yang optimum atau mungkin bebas celah.
.
lalu dari seluruh nested word yang tersisa, dirangkai nested word yang lebih besar yang merupakan sebuah program.
.
(Cara bayesian ut menebak yang terbaik, kembangkan sebarang metrik.
Gunakan konsep entropy untuk menilai suatu snipet adalah bagus.
cara jaringan syaraf tiruan untuk memperoleh snipet terbaik.
cara hill climb untuk kosntruksi snipet, dan sebagainya)
.
Mungkin seperti ini ide dasar proyek riset yang sedang dikerjakan oleh Rajeev sekarang.
#END IDE 1.
.
#END REVIEW1.
.
#REVIEW2:
Review: Visibly Pushdown Languages, by Rajeev Alur and P. Madhusudan.
.
(1).ABSTRAK:
[We propose the class of visibly pushdown languages.
as embeddings of context-free languages that is rich enough to model program analysis questions and yet is tractable and robust like the class of regular languages.]
.
“as embeddings of context-free languages” dimana? dimana cfg ditanam atau dilekatkan?
.
In our definition, the input symbol determines when the pushdown
automaton can push or pop, and thus the stack depth at every position.
.
Kalau deterministik automata, simbol-simbol input menyebabkan perpindahan state, maka pada PDA, simbol-simbol input menyebabkan terjadinya operasi push dan pop pada stack, dan perpindahan state.
.
[We show that the resulting class Vpl of languages is closed under union, intersection, complementation, renaming, concatenation, and Kleene-*.]
.
VPL = sebuah kelas dari bahasa-bahasa, dimana :
operasi union (penggabungan dua bahasa) menghasilkan bahasa yang VPL juga.
operasi intersection (pengirisan dua bahasa) menghasilkan bahasa yang VPL juga.
operasi komplemen dua bahasa, menghasilkan yang bahasa VPL juga.
operasi renaming(encoding setiap elemen dalam bahasa menghasilkan bahasa encoding?) dua bahasa yang VPL juga.
operasi konkatenasi (konkatenasi dua bahasa, untuk setiap elemen L1 yang VPL dan elemen L2 yang VPL, kemudian kedua elemen dikonkatenasi, maka menghasilkan suatu himpunan L3 sebauah bahasa yang VPL juga.
.
kemudian pembentukan kleene star dari suatu bahasa L yang VPL, menghasilkan bahasa L* yang VPL juga.
.
pertanyaanya, apakah VPL? apakah set rule yang menyatakan bahwa sebuah bahasa adalah VPL?
.
[and problems such as inclusion that are undecidable for contextfree languages are Exptime-complete for visibly pushdown automata]
.
suatu bahasa L1 yang VPL dan L2 VPL, apakah dapat ditentukan bahwa L1 subset dari L2 atau L2 subset dari L1 atau L! sama dengan L2?
dalam cfg, ini adalah undecideable.
tapi dalam kelas bahasa yang VPL, ini adalah Exptime-complete.
.
pertanyaanya, bagaimana membuktikannya?
apakah Exptime-complete?
.
[Our framework explains, unifies, and generalizes many of the decision procedures in the program analysis literature, and allows algorithmic verification of recursive programs with respect to many context-free properties including access control properties via stack inspection and correctness of procedures with respect to pre and post conditions.]
.
bagaimana susunan framework rajeev?
.
katanya dia berhasil menjelaskan, menyatukan dan mengeneralisasikan banyak prosedur2 pengambilan keputusan dalam komputasi khususnya literatur analisis program, dan menawarkan verifikasi secara algoritmic bagi program rekursif yang berkaitan dengan sifat2 context-free, mencakup sifat access control melalui stack inspection dan correctness of procedures yang respek terhadap pre dan post condition.
.
framework ini menawarkan cara verifikasi terhadap program (kode program?) dengan konsep access control, dimana access control dilakukan melalui inspeksi terhadap stack, dan koreksi prosedur yang melihat pre dan post condition.
.
[We demonstrate that the class Vpl is robust by giving three alternative characterizations: a logical characterization using the monadic second order (MSO) theory over words augmented with a binary matching predicate, a correspondence to regular tree
languages, and a restricted class of context-free grammars.]
.
framework rajeev adalah class VPL.
bagaimana dia mengkonstruksikan class VPL?
bagaimana dia menggunakannya?
apakah MSO theory?
apakah “over words augmented with a binary matching predicate”?
apakah regular tree languages?
apakah a restricted class of context-free grammars?
.
[We also consider visibly pushdown languages of infinite words and show that the closure properties, MSO-characterization and the characterization in terms of regular trees carry over.]
.
bagaimana bentuk visibly pushdown languages of infinite words.
bagaimana dia membuktikan bahwa “the closure properties, MSO-characterization and the characterization in terms of regular trees” adalah terpenuhi?
.
bagaimana dia mengkonstruksikan “nondeterministic Buchi visibly pushdown automata dan deterministic Muller visibly pushdown automata”
.
bagaimana dia mengukur “determinizability”?
.
(2).INTRODUCTION:
[Pushdown automata naturally model the control flow of sequential computation in typical programming languages with nested, and potentially recursive, invocations of program modules such as procedures and method calls.]
.
Secara alami, pushdown automata dibuat terutama sebagai model bagi semua bahasa yang memiliki konsep control flow.
contoh control flow yang dimiliki oleh bahasa seperti itu adalah:
afdanya nested, recursive, dan invokasi modul atau method atau program lain.
.
bahasa yang dimodelkan oleh regular automata adalah semua bahasa yang menurunkan ekspresinya secara linier saja atau regular, tanpa ada looping, siklus, nested, rekursif atau lompatan (invokasi).
.
[Consequently, a variety of program analysis, compiler optimization, and model checking questions can be formulated as decision problems for pushdown automata.]
.
Disini tampak ide umum lain dari rajeev, yaitu bahwa segala macam variasi analisis terhadap program (yaitu misal, pertanyaan2/permasalahan2 dalam hal optimasi compiler, pertanyaan2/permasalahan2 dalam model checking, adalah dapat diformulasikan ulang ke dalam decision problems pushdown automata, sehingga bisa secara global bisa dianalisa dalam satu cara pandang yaitu apakah dia decideable atau undecideable dalam pushdown automata. jika decideable maka bagaimana cara mengkonstruksikannya menggunakan framework class VPL.
.
[For instance, in contemporary software model checking tools, to verify whether a program P (written in C, for instance) satisfies a regular correctness requirement psi (written in linear temporal logic, for instance), the verifier first abstracts the program into a pushdown model Pa with finite-state control, compiles the negation of the specifcation into a finite-state automaton Apsi’ that accepts all computations that violate psi and algorithmically checks that the intersection of the languages of Pa and Apsi’ is empty.]
.
paragraf ini mengungkapkan sebuah startegi model checking untuk memverifikasi sebuah program P adalah memenuhi sebuah regular correctness requirement, sebut sebagai psi.
.
Bagaimana mengkonstruksikan “a regular correctness requirement” menggunakan LTL?
atau secara umum bagaimana menerjemahkan set requirement ke dalam LTL?
.
#Inspirasi2:
Bagaimana menerjemahkan sebuah program ke dalam pushdown automata?
Cara memodelkan sebarang bahasa program X ke dalam PDA adalah:
Assumsi-> sebarang bahasa pemrograman adalah ditulis dalam bentuk cfg.
tetapi sebaeang cfg adalah ekivalen atau dapat dimodelkan dengan sebuah PDA.
.
permodelan bahasa pemrograman X ke PDA adalah dengan melihat kepada set gramatika dari bahasa X, lalu menerjemahkan set gramatika ke PDA.
diperoleh sebuah PDA.
kemudian model checking dilakukan di atas PDA.
.
secara umum, kita dapat mengeneralisasi konsep model checking sebagai berikut:
sebarang naskah bahasa tipe n dalam hiereraki chomsky dapat diperiksa dalam konsep model checking dengan cara menerjemahkan gramatika bahasa tipe n itu ke dalam mesin turing.
selanjutnya gagasan model checking di terapkan di atas mesin turing.
pertanyaanya adalah bagaimana menjalankan proses model checking di atas model mesin turing? karena selama ini dijalankan di atas automata (finite state automata atau PDA).
.
kita lebih dapat memperluas ini dengan memperluas pertanyaan sebagai berikut:
Bagaimana menerapkan konsep model checking di atas lambda calculus. Ini karena lambda calculus ekivalen dengan mesin turing.
.
akan tetapi sebarang mesin dapat direpresnetasikan oleh algoritma, algoritma dapat ditulis dalam bahasa X (cfg atau bukan).
maka mesin dapat diverifikasi menggunakan model checking (baik di atas automata, mesin turing atau fungsi lambda).
.
mesin bisa berarti mesin cerdas, mesin protokol, dan sebagainya.
.
tapi apakah artinya “model Pa with finite-state control”.
#End inspirasi2.
.
[The problem of checking regular requirements of pushdown models has been extensively studied in recent years leading to ecient implementations and applications to
program analysis (RHS95, BEM97, BR00, ABE+05, HJM+02, EKS03, CW02). While many analysis problems such as identifying dead code and accesses to uninitialized variables can be captured as regular requirements, many others require inspection of the stack or matching of calls and returns, and are context-free. Even though the general problem of checking context-free properties of pushdown automata is undecidable, algorithmic solutions have been proposed for checking many dierent kinds of non-regular properties. For example, access control requirements such as \a module A should be invoked only if the module B belongs to the call-stack,” and bounds on stack size such as \if the number of interrupt-handlers in the call-stack currently is less than 5, then a property p holds” require inspection of the stack, and decision procedures for certain classes of stack properties already exist [JMT99, CW02, EKS03, CMM+04]. A separate class of non-regular, but decidable, properties includes the recently proposed temporal logic Caret that allows matching of calls and returns and can express the classical correctness requirements of program modules with pre and post conditions, such as \if p holds when a module is invoked, the module must return, and q holds upon return” [AEM04]. This suggests that the answer to the question \which class of properties are algorithmically checkable against pushdown models?” should be more general than \regular.” In this paper, we propose visibly pushdown languages as an answer with desirable closure properties, tractable decision problems, multiple equivalent characterizations, and adequate for formulating program analysis questions.]
.
Kalimat2 di atas menyatakan, mendeskripsikan, bagaimana program analysis itu, bagaimana memformulasikan program analysis, bagaimana menyusun program analysis question.
.
Apa yang penting sebenafnya dari konsep di atas adalah pertanyaan:
Apakah requirements sebenarnarnya, apa artinya?
Bagaimana merumuskan ke dalam LTL atau CTL?
Bagaiaman requirements dikonstruksikan atau dari mana diambil? dari kondisi2 yang diiningkan user atau secara umum rule-rule yang harus dipatuhi program ketika berjalan.
.
#Inspirasi3:
tapi bagaimana mengkonstruksikan rule-rule itu?
.
Yang jelas bahwa:
Bukan bahwa program itu ada dulu baru bikin rule-rule.
Akan tetapi rule-rule itu ada dulu baru kemudian program, program dikonstruksikan dari rule-rule tersebut.
pada dasarnya rule-rule itu adalah spesifikasi yang menjelaskan dengan rinci bagaimana sebuah kotak bekerja, kotak yang menerima input dan memberi otuput, kotak sebagai mesin komputasi atau sebarang mesin abstrak atau nyata.
.
Jadi prosesnya sebagai berikut:
Set spesifikasi (yang dinyatakan dalam rincian jika-maka atau sebarang ekspresi logika level n, rincian yang menyatakan bagaimana kotak bekerja).
Lalu dari set spesifikasi itu, orang mengkonstruksikan kotak.
Yaitu dengan mengkonstruksikan mekanisme input, mekanisme output, dan isi kotak atau himpunan state dalam kotak, yang dinyatakan dalam algoritma, algoritma yang dinyatakan dalam program bahasa X tertentu.
.
Jadi sebenarnya konsep model checking adalah:
model checking terhadap kotak.
model checking memodelkan, mengabstrasikan program dalam kotak menjadi FSA, PDA dsb automata, mesin turing, fungsi lambda.
Lalu mengkompile semua ekspresi rule/requirements yang ditulsi dalam logika level n, kemudian melewatkan ke dalam kotak.
.
untuk memeriksa celah atau error atau sebarang kesalahan dalam program adalah dengan cara:
buat negasi logika dari seluruh requirements/rule yang ditulis dalam logika level n tersebut, lalu buat automata yang menerima seluruh negasi itu, lalu periksa apakah bahasa yang dibangun oleh automata ut negasi dan bahasa yang dibangun ut original requirements, apakah kedua bahasa beririsan? jika ya, maka isi dari irisan itu adalah celah atau error atau kesalahan dari program.
.
#End inspirasi3.
.
#Inspirasi4:
[?]Apakah strusktur data yang rekursif?
Yaitu misal suatu butir data X (rekord, teks, node dan sebagainya), disefinisikan secara rekursif dengan cara sebagai berikut:
Misal data X didefinisikan sebagai struktur dengan format Y.
butir data X = susuanan data dengan format Y
tetapi di dalam format Y, butir data X didefiniskan lagi.
.
misal:
struct X { int data; struct X }
.
jika diterjemahkan dalam konsep rekord:
rekord X { int data; rekord X}
.
jika diterjemahkan dalam konsep node:
node X { int data; node X}
.
jika direpresentasikan dalam memory:
sebuah wilayah memory X dengan format Y
tetapi di dalam wilayah ini dibuat lagi wilayah memory X dengan format Y.
.
akan tetapi konsep ini secara nhyata tentulah sulit, karena sulit membayangkan di dalam sebuah wilayah memory dibuat lagi wilayah memory yang sama, tentunya dengan cepat wilayah memory habis.
.
dalam penerepannya, rekursif diterapkan secara pointer.
yaitu bahwa dalam butir data X didefinisikan pointer butir data X lain, jadi bukan butir data X sebenarnya, hanya pointernya. sedang kita dapat menunjuk suatu wilayah memory sebarang di luar sebagai tempat pointer menunjuk.
dengan cara ini suatu struktur data rekursif dapat dikonstruksikan secara terus menerus seakan tanpa batas.
.
sebagai contoh:
rekord X { int data; pointer rekord X berikut}
.
jika diterjemahkan dalam konsep node:
node X { int data; pointer node X berikut}
.
[?]Apakah fungsi/prosedur rekursif?
yaitu fungsi yang dalam definisi batang tubuh kodenya, dia mengeksekusi dirinya sendiri.
.
JIka di terapkan dalam konsep kotak:
sebuah kotak yang didefinisikan, dimana dalam kotak ada kotak yang sama definisinya.
.
Jika diterapkan dalam fungsi lambda, maka sebuah fungsi lambda dimana dalam ekspresinya terdapat fungsi lambda yang sama.
.
Jika diterapkan dalam kosntruksi gramatika bahasa dalam bahasa2 chomsky, sebuah bahasa rekursif yaitu jika dalam rule atau aturan produksi gramatikanya terdapat aturan produksi yang rekursif.
aturan produksi yang rekursif, contoh:
A –> A | aAb | AB | B | Ba
dalam hal ini:
A –> A adalah rekursif
A –> aAb adalah rekursif
A –> AB adalah rekursif.
.
[?]Bagaimana orang mengeneralisais konsep rekursif?
Suatu rekursi dapat dikosntruksikan tunggal atau linier:
contoh:
A –> aAb
tetapi bisa juga binary tree:
A –> aAbbcAc, karena bisa bercabang dua.
tetapi bisa juga terniary tree:
A –> aAbbcAcA, karena bisa bercabang tiga.
.
atau contoh lain:
rekursif biner:
node X { int data; pointer node X berikut kanan; pointer node X berikut kiri;}
rekursif terner:
node X { int data; pointer node X berikut kanan; pointer node X berikut kiri;pointer node X berikut tengah;}
atau quartener:
node X { int data; pointer node X berikut 1; pointer node X berikut 2; pointer node X berikut 3; pointer node X berikut 4;}
.
secara umum suatu konsep rekursif adalah bisa n-ner rekursif.
lebih umum lagi bisa sebarang graph.
.
contoh mesin yang m-rekursif:
sebuah kotak X didefinisikan dimana di dalam kotak X terdapat m buah kotak X.
.
Pertanyaan penting:
bagaimana orang membuktikan bahwa ekspresi rekursif adalah turing complete?
.
[?]Apakah filosofi dasar dari konsep rekursif?
Konsep rekursif adalah suatu ekspresi matematika induksi.
Artinya bahwa pada dasarnya konsep rekursif adalah suatu logika induksi.
.
Akan tetapi langkah2 induksi ini dapat dilihat sebagai langkah2 komputasi, dan langkah2 komputasi ini dapat mensimulasikan seluruh mesin turing.
.
Jadi bayangkan sebuah kotak yang isinya adalah matematika induksi atau langkah2 rekursif.
.
Pembuktian ini secara intuitif adalah sebagai berikut:
Sebarang algoritma yang benar adalah dapat dibuktikan dengan menggunakan matematika induksi. Ini berarti bahwa sebarang algoritma yang benar itu adalah dapat dienkoding atau diekspresikan ke dalam term2 induksi, yang berarti term2 rekurisf, yang berari langkah2 komputasi rekursif.
Sehingga konsep rekursif adalah turing complete.
.
#End inspirasi4.
.
#Inspirasi5:
[?]Bagaimana fungsi rekursif sepadan dengan mesin turing standar atau turing complete?
Nyatakan setiap transisi ke dalam ekspresi rekursif.
Misal:
State X {data input; state X}
dimana X = A,B,C,D,…
.
atau:
node {data input; node}
.
atau:
state {data input; state}
.
untuk undeterministik:
state {data input; (state,state,…,state)}
.
untuk mesin turing:
instruksi {data input; aksi; instruksi}
.
untuk undeterministik turing machine:
instruksi {data input; aksi; (instruksi,instruksi,instruksi)}
.
atau:
state {data input; aksi; (state,state,…,state)}
.
[?]Bagaimana lambda calculus sepadan dengan mesin turing atau turing complete?
Nyatakan setiap transisi dalam mesin turing standar dalam ekspresi fungsi lambda.
Misal:
q(A,b) –> q(B,c,R)
menjadi:
lambda(Ab).BcR
dan seterusnya, sehingga setiap program yang ditulis dengan set instruksi mesin turing adalah dapat juga ditulis dengan ekspresi lambda.
.
#End inspirasi5.
.
apa lagi lan?
Bagaimana model checking melihat set requrement terhadap model automata?
mungkin jawaban ut ini dapat mengantar kita pada model checking di atas mesin turing atau lambda calculus atau fungsi rekursif.
.
#Inspirasi6:(https://en.wikipedia.org/wiki/Recursion)
Definisi rekursif dalam cara pandang teori himpunan adalah sebagai berikut:
0 in N
if n is in N, then n+1 is in N
.
Kita dapat mengeneralisir ini dalam graph berarah sebagai berikut:
node_awal is in G
node_n is in G then node_n–>node_n+1
.
akan tetapi orang mengeneralisir konsep rekursif dan mungkin dapat kita bawa kepada seluruh cara pandang, yaitu sebagai berikut:
yaitu rekursif yang membangun tree atau binary tree, atau secara umum n-ner tree, atau secara umum sebuah graph yang acyclic, tapi mungkin juga cyclic.
.
[?]Bagaimana secara umum dan intuitif kita dapat membuktikan bahwa sebarang automata atau mesin turing dapat dinyatakan ke dalam mesin turing?
Yaitu bahwa:
Sebarang graph berarah acyclic atau cyclic dapat direpresentasikan sebagai fungsi rekursif. Tetapi sebarang automata dapat direpresentasikan ke dalam grap berarah, cyclic atau acyclic.
.
[?]Bagaimana mengekspresikan fungsi rekursif ke dalam gambar?
yaitu dengan gambar fraktal.
akan tetapi mesin turing dapat direpresentasikan ke dalam cellular automaton, sedang cellular automaton dapat direpresentasikan ke dalam gambar fraktal, maka mesin turing dapat dinyatakan ke dalam fungsi rekursif.
#End inspirasi.
.
#Inspirasi7:(https://en.wikipedia.org/wiki/Structural_induction)
Konsep pembuktian dalam matematika menggunakan matematika induksi diperluas orang menjadi pembuktian secara structural induction.
contoh:
buktikan untuk k=0,
misalkan untuk k1 benar
misalkan untuk k2 benar
misalkan untuk k3 benar
…
misalkan untuk kn benar
.
buktikan untuk k1+1
buktikan untuk k2+1
buktikan untuk k3+1
…
buktikan untuk kn+1
.
demikian sehingga seluruh cabang tree dibuktikan.
atau buktikan secara induksi seluruh kombinasi k1,k2,k3,..,kn yang mungkin.
.
untuk sebarang graph:
dekomposisikan graph ke dalam n buah path.
lalu buktikan secara induksi untuk tiap2 path.
#End inspirasi7.
.
#Inspirasi8:
[?]Bagaimana orang mengerjakan model checking?
Bismillah:
Pertama:
Orang menulis seluruh requirements dari prakonstruksi kotak (mesin,sistem).
Kemudian seluruh requirements ditulis ke dalam logika orde-n. untuk n yang dipilih.
.
kemudian orang mengkonstruksikan kotak menurut petunjuk set requirements.
.
kemudian orang melakukan verifikasi terhadap kotak yang telah dikonstruksikan dengan cara:
untuk setiap statemen (sebuah pernyataan requirement dalam logika orde-n)
statemen terverifikasi terhadap kotak jika hanya jika disana terdapat titik atau set titik atau path posisi dalam untai run kotak dimana statemen bernilai benar.
.
verifikasi statemen ke statemen bisa berarti path ke path dalam untai run kotak.
.
jika seluruh statemen benar maka terverifikasi.
.
tetapi dalam cara lain, orang membuat negasi dari statemen, dan menjalankan negasi-negasi itu dalam kotak, jika negasi2 itu juga benar, maka kotak tidak terverifikasi.
.
#End Inspirasi8.
.
#Inspirasi9:
[?]Bagaimana secara rill orang membangun bahasa pemrograman yang moderen seperti sekarang ini, dimana letak gagasan-gagasan mesin komputasi di dalamnya?
.
Sepertinya orang membangun bahasa secara praktis dengan menggabung atau mengkombinasikan beberpa konsep mesin komputasi dalam bahasa yang dibangunnya, misal:
Bahasa X = sintak dan semantik untuk:mesin fungsi lambda + mesin fungsi rekursif + mesin iteratif (ini termasuk rekursif) + mesin objek oriented + mesin2 lainnya yang mungkin.
ditambahkan dengan style atau sintak atau semantik yang global untuk keseluruhan.
.
[?]Apakah computable function?
Yaitu setiap fungsi yang dapat dinyatakan dalam suatu algoritma dan sebaliknya.
Atau setiap fungsi yang dapat dinyatakan dalam mesin turing dan sebaliknya.
.
[?]Apakah class of computable function?
Yaitu sebuah fungsi yang computable membangun himpunan kelas yang serupa. misal kelas fungsi lambda, kelas fungsi rekursif, dsb.
.
#End inspirasi9.
.
#END REVIEW2.
.
#REVIEW3:
Review:https://plato.stanford.edu/entries/recursive-functions/#1.1
.
#Inspirasi10:
[?]Bagaimana kita melihat sifat universal dari deret fibonacci?
Bismillah:
Pertama:
Kita dapat melihat bahwa deret fibonacci adalah generalisasi dari persamaan subtitusi berulang dari Raffaele Bombelli:
x = 1 + 1/x = 1 + 1/(1+1/x) = 1 + 1/(1+1/(1+1/x)) = …
.
yang jika diperumum dalam bentuk:
f(n+2)/f(n+1)=1+1/(f(n+1)/f(n))
.
diperoleh deret fibonacci dalam bentuk umum:
f(n+2)=f(n)+f(n+1)
.
Kedua:
Deret fibonacci di atas dikatakan umum karena kita dapat mendefinisikan f(n) dalam sebarang cara.
.
cara yang paling sederhana tentunya adalah dengan mendefinisikan f sebagai berikut:
f(n)=n
.
sehingga kita memperoleh deret fibonacci yang asli.
.
[?]Bagaimana kita memperumum deret fibonacci?
Bismillah.
Pertama:
Dalam bentuknya yang sudah umum, yaitu: f(n+2)=f(n)+f(n+1)
.
kita dapat membawa ini kepada geometri sebagai berikut:
misalkan suatu deret g(1),g(2),g(3),…,g(n) menyatakan suatu deret benda-benda atau figur-figur geometri.
kemudian kita membuat aturan konstruksi sebagai berikut:
L(g(n+2))=L(g(n))+L(g(n+1))
.
kita mengatakan bahwa konstruksi ini adalah konstruksi dalam deret fibonacci.
.
Secara umum, kita dapat mengenarilisir ini ke dalam segala bentuk perubahan pola yang bisa dipetakan ke bilangan asli, Kita mengatakan itu sebagai perubahan pola dalam deret fibonacci.
.
[?]Bagaimana melihat bahwa sebarang polinom adalah sebuah bentuk fungsi rekursif?
Atau:
[?]Bagaimana melihat bahwa sebarang polinom dapat dikonstruksikan dari suatu fungsi rekursi, atau suatu bentuk rekursif?
Bismillah:
misalkan sebuah polinom F(x)=0
nyatakan dalam bentuk:
f(x)=g(x)
.
lalu nyatakan ke dalam bentuk:
f(x)=g(f(x))
.
contoh:
2x^3-4x-2=0
.
diperoleh:
x=(2/x)+(1/x^2)
sebuah bentuk rekursif, misalkan x digeneralisir menjadi sebarang polinom f(x), diperoleh:
f(x)=(2/f(x))+(1/f(x)^2)
.
yaitu bentuk:
f(x)=g(f(x))
.
ini dapat digeneralisir lagi menjadi sebarang f(x) polinom atau bukan.
.
Berdasarkan ini kita dapat membuat sebuah teorema sebagai berikut:
Sebarang kompleksitas polinomial adalah merupakan sebuah bentuk rekursif dari kompleksitas polinomial yang lain.
Bukti:
Misalkan kita memiliki kompleksitas yang dinyatakan oleh O(p(x)).
nyatakan p(x) ke dalam f(x)=g(f(x)) dimana f(x) suatu polinomial tertentu.
maka teorema terbukti.
.
Teorema lagi:
Sebarang kompleksitas secara umum aalah sebuah bentuk rekursif dari kompleksitas yang lain.
Ini karena berdasarkan assumsi bahwa sebarang fungsi dapat dinyatakan oleh suatu deret polinomial berhingga atau tak hingga.
.
Teorema yang lain:
Sebarang sinyal adalah bentuk rekursif dari sinyal yang lain.
dengan melihat sinyal adalah deret fourier
dan tiap sin cos dinyatakan dalam eksponensial
dan tiap eksponensial dapat dinyatakan ke dalam deret polinomial tak hingga.
.
Ini memberi kita sebuah konjekture bahwa sebarang bangun geometri yang dapat direpresentasikan oleh suatu polinom adalah selalau dapat dinyatakan dalam ekspresi rekursif, atau dikonstruksikan secara rekursif.
.
#End isnpirasi10.
.
(1).
First Recursion Theorem (Odifreddi, 1989, II.3.15):
Sepertinya adalah sebuah argumen bahwa sebarang fungsi rekursif dapat dihitung dengan menerjemahkannya ke dalam bentuk polinomial.
Atau:
Sebarang bentuk rekursif dapat dikembalikan ke bentuk polinomial, selanjutyna dipecahkan atau dihitung dalam bentuk polinomial.
.
Tetapi kita dapat mengambil ide kebalikannya, yaitu bahwa sebarang bentuk polinomial dapat dikonstruksikan ke dalam bentuk rekursif.
.
Secara keseluruhan, First Recursion Theorem ini menyatakan cara untuk membhitung fungsi rekursif dalam 2 jalan:
Pertama:
Terjemahkan fungsi rekursif ke dalam polinomial, lalu pecahkan hitungan nilainya sebagiamana memecahkan masalah polinomial.
.
Kedua:
Pecahkan secara bagian ke bagian lain atau rekursif ke rekursif lain.
Sedemikian sehingga diperoleh seuah barisan bilangan rekursif.
Contoh untuk ini adalah pemecahan dalam bentuk persamaan Raffaele Bombelli.
x=1+(1/x)=1+1/(1+1/x)=1+1/(1+1/(1+1/x))=….. dan seterusnya.
.
Misal:
Pecahkan untuk x=1+(1/x) (sebuah pemecahan polinomial).
lalu pecahkan untuk 1+1/(1+1/x)=1+1/(1+1/(1+1/x)) (sebuah pemecahan polinomial).
dan seterusunya.
.
(2).
Apa hubungannya Differentiable functions dengan fungsi rekursif?
Apakah sebarang fungsi yang differensiabel dapat dinyatakan secara rekursif atau dapat dinyatakan dalam deret fungsi rekursi (polinomial)?
.
Yaitu bahwa sebarang fungsi differensiabel, dapat dihitung secara rekursif.
How?
.
#Inspirasi10.5:
Secara umum, gagasan pada bagian ini adalah sebagai berikut:
Sebarang fungsi analitik (differensiabel) adalah dapat dinyatakan ke dalam bentuk rekursif dari diffrenesial-differensialnya.
.
Sebagai contoh (formula newton):
x(n+1)=xn-f(xn)/f'(xn)
dan seterusnya….
Contoh yang lain:
Rumus taylor (deret taylor).
.
#End inspirasi10.5.
.
#Inspirasi11:
Sebarang bentuk rekursif:
…=…
kemudian diperpanjang menjadi:
…=…=…=…=… …=..
Sebenarnya adalah ekspresi yang ekivalen atau merepresentasikan sebuah barisan entiti atau bilangan.
Jadi:
[…=…=…=…=… …=..] = Barisan bilangan rekursif
.
Misal:
[…=…] = ekivalen dengan n9,n8,n7,n6.
berikutnya:
[…=…] = ekivalen dengan n5,n4,n3,n2.
dan seterusnya sehigga diperoleh sebuah barisan bilangan.
.
#End inspirasi11.
.
#inspirasi12:
[?]Bagaimana fungsi rekursif atau mesin rekursif diimplementasikan ke dalam algoritma atau bahasa pemrograman atau koding?
Bismillah:
mesin rekursif diimplementasikan dengan sintaks:
while-end
do-while
loop-end
for
dan setersunya.
.
Sehingga suatu ekspresi rekursif dapat dinyatakan dalam suatu deret:
while-end = while-end1 + while-end2 + while-end3 +…+ while-endN
atau:
do-while = do-while1 + do-while2 + do-while3 +…+ do-whileN
atau:
for = for1 + for2 + for3 +…+ forN
dan setersunya.
.
[?]Bagaimana melihat bahwa metode elemen hingga sebenarnya adalah ekspresi mesin rekursif?
Bismillah:
Pertama:
Metode elemen hingga adalah semata metode numerik.
kana tetapi metode numerik adalah sekumpulan komputasi mesin rekursif.
Yaitu sekumpulan fungsi rekursif.
.
Dimana sebarang hitungan dunia nyata diterjemahkan atau dihitung dalam konteks fungsi rekursif.
.
[?]Bagaimana implementasi metode elemen hingga atau metode numerik pada bahasa pemrograman?
Implementasi metode elemen hingga atau metode numerik dalam pemrograman komputer, secara mendasar adalah menggunakan implementasi mesin-mesin rekursif pada bahasa-bahasa pemrograman, seperti while-end, do-while, do-loop, loop-end, for, dan sebagainya.
.
[?]Apakah hakikat konsep aproksimasi?
Bismillah:
Konsep aproksimasi dapat dilihat saja sebagai sebuah mesin rekursif yang berhitung untuk mencapai suatu nilai.
.
Implementasi konsep ini, adalah sebagai berikut:
Sebarang fungsi f, dapat didekati secara rekursif (rekursif oleh dirinya sendiri atau oleh turunannay, atau oleh yang lain).
.
#End inspirasi12.
.
#Pertanyaan1:
Bagaimana newton, rahpson menurunkan konsep rekursif untuk rumus aproksimasi mereka?
Bagaimana taylor menurunkan mesin rekursif berdasarkan turunan?
Bagaimana mac laurin menurunkan mesin rekursif?
Bagaimana orang mengeneralisir mesin rekursif ke ruang vektor, ke ruang berdimensi n, dan seterusnya?
.
Perluasan ini penting untuk penerapan mesin rekursif pada kalkulasi di ruang berdimensi n.
.
Penurunan secara umum bentuk fibonacci f(n+2)=f(n)+f(n+1) dari gagasan bentuk rekursif adalah belum jelas secara argumentatif, masih tampak sebagai suatu trik matematika saja.
.
#End pertanyaan1.
.
#Inspirasi13:
[?]Bagaimana orang melihat mesin rekursif sebagai framework universal untuk ilmu pengetahuan?
Bismillah:
Orang menggunakan mesin rekursif untuk membangun suatu sistem formal ilmu pengetahuan.
Dengan menulis sintaks dari definisi2, aksioma2, postulat2 ke dalam bentuk rekursif.
Selanjutnya segala teorema atau elemen2 dalam sistem formal itu dibangun secara rekursif menggunakan mesin rekursif tersebut.
.
Sebagai contoh logika, topologi, atau bahasa formal yang dikonstruksikan menggunakan mesin rekursif.
.
Bentuk dasar intuitif dari framework ini yaitu bahwa suatu himpunan bilangan asli dapat dikonstruksikan secara rekurssif, sehingga sebarang sistem formal yang dapat dipetakan ke bilangan asli adalah dapat dibangun secara rekursif.
.
[?]Bagaimana melihat bahwa metode newton-raphson adalah solusi rekursif atau sebuah mesin rekursif bagi eksperesi rekursif sendiri?
Bismillah:
Pada dasarnya metode newton-raphson ditujukan sebagai solusi general bagi cara menemukan atau menghitung suatu root atau akar sebarang polinom.
.
Jadi bisa dirumuskan sebuah inspirasi sebagai berikut:
Metode newton-raphson adalah sebuah mesin rekursif general untuk menghitung sebarang polinomial dengan 1 variabel.
.
Orang Kemudian mengeneralisir suatu cara, yaitu menemukan sebuah mesin rekursif yang bekerja di ruang berdimensi n untuk sebarang polinom dengan n variabel, yaitu suatu polinom di ruang berdimensi n.
.
Akan tetapi sebarang polinom dapat dikembalikan ke bentuk rekursif, sehingga ini berarti metode newton raphson dapat digunakan untuk menghitung sebarang ekspresi rekursif.
.
Kemudian orang mencari mesin rekursif yang lebih umum lagi yang bekerja di ruang berdimensi n untuk sebuah ekpresi rekursif dalam ruang berdimensi n.
.
[?]Bagaimana kita melihat masalah konvergensi dan divergensi sebagai sesuatu yang penting (fundamental) dalam semesta komputasi?
.
Ini karena sebarang ekspresi rekursif bilangan dapat dinyatakan ke dalam sebuah deret. Ini berarti gagasan decideable sebuah mesin rekursif adalah ekivalen dengan gagasan konvergen dari deret yang mewakilinya.
.
Sehingga sebuah konjektur dapat kita peroleh sebagai berikut:
Sebuah mesin rekursif adalah decideable jika hanya jika ekpresi deret yang mewakilinya adalah konvergen.
.
#End inspirasi13.
.
[embed_rev:https://en.wikipedia.org/wiki/Newton%27s_method%5D
[1].
Ide dasar mesin rekursif metode newton raphson adalah sebagai berikut:
L1:tentukan titik x0
L2:tentukan garis tangen di (x0,f(x0))
L3:tentukan titik potong garis tangen dan sumbu x, diperoleh x1
Rekrusif:
L1:diperoleh ririk x1
L2: dst
L3: dst.
.
Kerja mesin rekursif ini bisa konvergen, bisa divergen.
.
Orang mengeneralisir ini di ruang berdimensi n.
.
Secara umum, orang membangun kelas metode yang serupa dengan metode newton ini, secara umum dalam kelas ini dinyatakan sebagai kelas metode yang berusaha memecahkan persamaan:
f(x)=0
menggunakan mesin rekursif.
.
Pertanyaan penting:
Bagaimana orang membangun sebuah mesin rekursif di ruang berdimensi n untuk menghitung
f(x,y,z,…)=0 ?
.
[?]Mengapa metode numerik dikatakan sebagai matematika komputasi?
Ini jelas karena seluruh atau hampir seluruh(?) disana adalah penggunaan mesin rekursif untuk memecahkan masalah-masalah matematika.
Sehingga kita menyebutnya sebagai komputasi untuk matematika, atau matemtaika komputasi, secara lebih hakikat sebenarnya adalah komputasi mesin rekursif untuk matematika.
.
Mungkin kita bisa membangun matematika komputasi menggunakan semata fungsi lambda, atau semata mesin turing, sebagai mesin-mesin yang setara dengan mesin rekursif.
.
Imajinasi dasar, atau starting point untuk membangun ranah penggunaan mesin rekursif untuk memecahkan masalah-masalah matematika (analitik) adalah temuan newton-raphson, atau secara umum temuan kelas mesin rekursif yang memecahkan masalah f(x)=0, yaitu kelas Householder.
.
[?]Posisi mesin rekursif newton terhadap sistem persamaan linier secara umum?
Bismillah:
Kita dapat melihat mesin rekursif newton sebagai mesin atau metode yang memecahkan masalah persamaan non linier secara umum.
.
Hingga kepada sistem persamaan non linier.
.
Lebih umum lagi kelas mesin householder, dan generalisasinya untuk variabel banyak adalah mesin rekursif yang digunakan untuk memecahkan masalah sistem persamaan non linier:
f(x,y,z,…)=0
.
tetapi non linier yang dimaksud adalah persamaan polinomial.
.
Orang mengeneralisasinya lagi kepada mesin-mesin rekursif untuk pengertian non linier yang bukan polinomial, seperti eksponensial, trigonometrik, logaritmik dan sebagainya.
.
Kita dapat melihat rumus2 taylor sebagai gagasan yang bagus untuk ini.
.
[?]Bagaimana kita melihat arti penting temuan fourier untuk deret fouriernya?
Ini memiliki arti filosofis yang sangat penting, yaitu bahwa fourier menemukan suatu hukum bahwa tiap-tiap persamaan non linier atau sistem persamaan non linier adalah dapat dinyatakan ke dalam atau diekspresikan ke dalam atau dapat dihitung oleh sebuah mesin rekursif (ekspresi deret fungsi gelombang sederhana).
.
Ini memiliki arti bahwa sebarang fenomena non linier di alam adalah mungkin dapat dihitung menggunakan mesin rekursif.
.
Bahkan secara umum:
Sebarang persamaan atau sistem persamaan linier dan non linier adalah dapat diekspresikan ke dalam bentuk mesin rekursif (ekspresi deret fungsi gelombang sederhana), dan karenanya dapat dihitung menggunakan mesin rekursif tersebut.
.
[?]Apakah dasar ide metode newton dan kelas householder secara umum atau kepada persamaan non linier variabel banyak?
Dasar ide ini bukanlah penurunan geometri analitik di cartesian.
Akan tetapi dapat dilihat semata secara general (telah digeneralisasi) ke dalam fondasi gagasan ekspansi taylor.
.
Jadi secara umum, metode newton-raphson, dan seluruh metode dalam kelas householder adalah diturunkan semata dari ekspansi taylor.
.
generalisasi metode newton-raphson, adalah semata generalisasi order dari ekspansi taylor.
.
Demikian ketika orang mengeneralisir ini ke banyak variabel, orang menggunakan ekspansi taylor, dengan merumuskan ekspansi taylor dalam perubah banyak.
.
[?]Bagaimana kita melihat universalitas rumus taylor, dan bagaimana generalisasinya dalam cara pandang polinomial?
Bismillah:
Rumus taylor mengeneralisasi seluruh rumus dalam kelas mesin rekursif dari Householder, bahkan lebih jauh dari pada metode house holder sendiri.
.
Rumus taylor menerjemahkan seluruh cara hitung fungsi-fungsi yang analitik (analitik artinya bisa diturunkan hingga turunan ke-n) ke dalam proses numerik yang rekursif (mesin rekursif).
.
Ini memberi cara pandang baru, bahwa sebarang hitungan fungsi yang analitik adalah bisa dihitung secara analitik semata (menggunakan tool2 kekontinuan, differensial, dan sebagainya) atau cara hitung numerik menggunakan mesin rekursif.
.
Ini memberi power bagi komputasi untuk masuk ke dalam seluruh area matematika dengan menerjemahkan atau melihat seluruh persoalan matematika sebagai semata persoalan algoritmik atau numerik.
.
[Artikel]
#Tentang bagaimana melihat seluruh persoalan matematika sebagai semata persoalan komputasi
Bismillah:
Pertama:
Penemuan konsep deret dan barisan (secara teknis adalah rumus newton-raphson hingga rumus taylor dan semua generalisasinya), secara intuitif, sebenarnya memberi pintu masuk yang sangat powerfull bagi komputasi untuk masuk ke dalam seluruh area matematika (terutama matematika analisis), kita bisa melihat bahwa gagasan itu menerjemahkan seluruh persoalan matematika menjadi semata persoalan komputasi, secara teknis, saya melihat ini sebagai menerjemahkan seluruh fungsi-fungsi analitik ke dalam langkah-langkah mesin rekursif.
.
Akan tetapi mesin rekursif (fungsi rekursif) adalah mesin yang ekivalen dengan mesin turing, bahkan ekivalen dengan seluruh mesin dalam kelas lambda calculus, sehingga kita bisa melihat secara intuitif, bagaimana mesin turing meraja ke dalam seluruh area matematika murni, demikian juga lambda calculus.
.
Hanya saja saya belum pernah melihat ada orang yang merumuskan atau mengemukakan sebuah teorema bahwa “sebarang fungsi analitik adalah selalu dapat dinyatakan atau dihitung dalam langkah-langkah lambda calculus” atau bahwa “sebarang fungsi analitik selalu dapat diekspresikan ke dalam langkah-langkah mesin turing”.
.
Sebagai sebuah teorema yang ekivalen dengan rumus taylor.
.
Membuktikannya sepertinya mudah secara intuitif, hanya dengan membuktikan bahwa ekspresi rumus taylor adalah ekspresi mesin rekursif, kemudian menggunakan ekivalensi dengan mesin turing atau lambda calculus, maka tujuan kita tercapai.
.
Insight di atas memberi kita cara pandang baru bahwa selain kita dapat menyusun mata kuliah metode numerik yang secara hakikat sebenarnya adalah matematika dalam cara pandang komputasi menggunakan mesin rekursif, kita sebenarnya dapat juga membangun mata kuliah metode numerik yang seluruhnya dalam cara pandang lambda calculus, atau metode numerik yang seluruhnya dalam cara pandang mesin turing.
.
Ini juga memberi arti baru bagi konsep konvergen dan divergen dalam matematika analisis, yang diterjemahkan sebagai sesuatu yang sebenarnya adalah konsep decideable dan undecideable dalam komputasi.
.
Artinya bahwa, jika kita mengatakan bahwa sebuah deret adalah konvergen, maka itu berarti adalah bahwa ekspresi mesin rekursif ekivalennya adalah konvergen ke suatu nilai atau beberapa nilai. Itu berarti mesin rekursif ekivalennya adalah decideable, yang berarti mesin turing ekivalennya adalah decideable.
.
Sebaliknya jika sebuah deret adalah divergen, maka itu berarti mesin rekursif ekivalennya adalah divergen, menuju ke suatu nilai yang tidak tentu, yang berarti bahwa mesin rekursif itu undecideable, yang berarti mesin turing ekivalennya adalah undecideable.
.
Bagi saya ini adalah sebuah konjektur yang bisa kita tulis sebagai berikut:
“Tiap-tiap fungsi analitik yang ekspresi deretnya adalah konvergen jika hanya jika mesin turing ekivalennya adalah decideable”
.
Berdasarkan ini juga, kita dapat menemukan sebuah teorema yang mungkin dapat kita tulis sebagai berikut:
Teorema:
“Sebarang mesin turing atau algoritma adalah memiliki kompleksitas langkah-langkah yang dibangun secara rekursif oleh sejumlah kompleksitas yang lain”
.
Yaitu bahwa jika kita memiliki mesin turing atau algoritma dengan kompleksitas O(P(x)) maka disana terdapat kompleksitas O(f(x)) yang membangun O(P(x)) secara rekursif.
.
Bukti teorema ini mungkin sebagai berikut:
Misalkan P(x) ekspresi polinomial, maka kita dapat memecah polinom ini dan menuliskannya dalam bentuk rekursif sebagai berikut:
f(x)=g(f(x))
.
Ini berarti kompleksitas O(P(x)) dibangun secara rekursif oleh O(f(x)).
.
Misalkan P(x) bukan polinomial, tetapi fungsi analitik, maka kita dapat menyatakannya sebagai polinomial menggunakan rumus taylor atau generalisasinya, selanjutnya kita dapat menyatakannya dalam bentuk rekursif sebagai f(x)=g(f(x)).
.
dan seterusnya.
.
Teorema di atas dapat kita perluas untuk mesin turing nondetreministik (termasuk juga mesin turing paralel), dengan melihat secara intuitif bahwa kompleksitas mesin turing atau algoritma yang bekerja secara nondeterministik memiliki kompleksitas yang seumpama atau analogi dengan ekspresi sistem persamaan non linier, sehingga kompleksitas seperti itu dapat dihampiri secara polinomial oleh perluasan rumus taylor ke sistem non linier perubah banyak, dengan demikian, kita kembali dapat mengekspresikan kompleksitas mesin turing nondeterministik sebagai kompleksitas yang dibangun secara rekursif oleh kompleksitas lain.
.
Kedua:
Untuk seluruh matematika yang bukan matematika analisis (seperti logika formal, geometri, topologi, aljabar, dsb) secara intuitif seluruh sistemnya dapat kita lihat sebagai seumpama konstruksi bilangan asli yang dibangun secara rekursif. Yaitu dengan menulis ulang fondasi mereka (definisi, aksioma, postulat) ke dalam bentuk rekursif, sehingga kita bisa melihat secara intuitif bahwa seluruh sistem itu adalah sebuah sistem yang dibangun secara komputasional menggunakan mesin rekursif, yang berarti dibangun secara komputasional menggunakan mesin turing atau lambda calculus.
.
Allahu ‘Alam
Ponorogo, 4 Dsember 2017
.
#Pandangan diatas mungkin bisa memberi kita rasa percaya diri yang kuat dan sebuah visi bahwa kita dapat membenamkan seluruh matematika ke dalam otak sebuah mesin (komputer) dan membiarkan mesin itu membangun sistem-sistem formal matematika baru yang mungkin belum pernah kita pikirkan sebelumnya.
.
Dimasa depan, kita mungkin cukup hanya mengkomunikasikan imajinasi kita (tentang dunia yang kita pikirkan) kepada mesin lewat antarmuka otak-mesin atau membiarkan mesin mengindera fenomena-fenomena alam secara sendirian, lalu mesin-mesin itu mengenerate sistem-sistem matematika formal yang baru untuk melakukan berbagai permodelan dan kalkulasi.
.
Dengan demikian, epistimologi bagi ilmu pengetahuan, hanyalah sesuatu yang komputasional yang dapat dikonstruk begitu saja atau dilepas begitu saja.
.
Kita tidak saja mungkin merevolusi cara kita memahami alam dan mengambil ilmu pengetahuan daripadanya, yang dulunya lambat dan terjebak dalam jebakan “bottle neck”, menjadi sesuatu yang sangat cepat dan fly.
.
——————————————————
Pertanyaan yang tersisa sampai disini:
Bagaimana rumus taylor digeneralisir ke dimensi n.
[2].
[embed_review:http://numbers.computation.free.fr/Constants/Algorithms/newton.html#Householder%5D
Generalisasi ini hanya dengan melakukan analogi pada penurunan metode newton-raphson menggunakan ekspansi taylor untuk orde 1 (digunakan hanya sampai pada term orde 1), lalu konstruksikan matriks jacobian, dan seterusnya diperoleh bentuk analogi dari metode newton-raphson di ruang berdimensi n untuk sebuah sistem persamaan non linier dengan variabel banyak.
.
Secara umum, dengan melepas batasan tidak hanya sebatas orde 1 tetapi orde yang lebih tinggi pada ekspansi taylor, maka kita memperoleh generaliasi untuk kelas Householder bagi sistem persamaan non linier dengan variabel banyak.
.
——————————————————
Pertanyaan tersisa berikut:
Bagaimana taylor mengkonstruksikan taylor expansion?
Bagaimana memasukkan dalam artikel tentang gagasan orang, merepresentasikan sebarang sistem non linier ke dalam mesin rekursif.
.
[embed-review:https://en.wikipedia.org/wiki/Interpolation%5D
[3]Apakah interpolasi?
Interpolasi jika dilihat dalam konteks semata data, adalah konstruksi titik-titik data baru atau konstruksi rekord-rekord baru menggunakan data yang ada.
Konstruksi ini bisa dinamakan sebagai prediksi atau estimasi titik data baru.
.
#Inspirasi14:
Berdasarkan pengertian ini, proses membuat kartu pengetahuan baru dalam sistem CBR, adalah proses interpolasi, dimana titik data baru adalah kartu baru.
.
Ini juga bisa memiliki arti bahwa interpolasi titik-titik data baru bisa jadi bisa menghasilkan rule-rule baru dalam proses mining rule pada datamining.
.
#End inspirasi14.
.
Tetapi jika dilihat secara geometri, ketika kita memetakan seluruh titik data lama ke dalam ruang cartesian, maka interpolasi adalah konstruksi titik-titik cartesian baru dalam ruang cartesian.
Pekerjaan ini dapat disederhanakan saja sebagai menarik garis atau membuat area dalam ruang cartesian, karena garis yang kita tarik adalah pada hakikatnya kumpulan titik-titik data baru.
.
Jika kita melihatnya secara analitik, adalah berarti memprediksi nilai-nilai fungsi berdasarkan nilai-nilai fungsi yang ada, nilai-nilai fungsi yang diambil dari sampling atau eksperimen, bukan dari eksekusi body fungsi (disini dimisalkan bahwa body fungsi tidak diketahui, tetapi input dan outputnya diketahui sebagian).
.
[?]Apakah artinya gagasan interpolasi polinomial newton.
Yaitu cara newton untuk mengkonstruk titik-titik data baru dengan cara mengkonstruksikan polinomial yang melewati seluruh titik-titik data lama.
Sehingga semua titik yang ada dalam polinomial, bukan titik lama, adalah himpunan titik-titik data baru.
.
[?]Apa bedanya interpolasi dan ekstrapolasi?
Interpolasi berarti konstruksi titik-titik data baru di dalam range titik-titik data lama.
Ekstrapolasi berarti konstruksi titik-titik data baru di luar range titik-titik data lama.
.
[?]Bagaimana orang memperluas gagasan interpolasi kepada dimensi yang lebih tinggi?
Pekerjaan ini seperti menemukan atau memprediksi piksel menggunakan piksel-piksel tetangganya, atau memprediksi voxel menggunakan voxel-voxel tetangganya, dan setersunya berbagai cara yang bisa dikembangkan orang.
.
Konsep filter dalam citra, dapat dilihat sebagai gagasan interpolasi dibidang.
.
[?]Apakah spline interpolation?
Yaitu memecah range data ke dalam sejumlah partisi, lalu diatas tiap2 partis dikonstruksikan polinomial derajat rendah, sehingga secara keseluruhan untuk seluruh range, ada n buah polinomial yang disambung secara mulus untuk n buah partisi.
.
Ini sebenarnya adalah generalisasi dari linier interpolation, yang menggunakan garis-garis linier untuk mengkonstruk titik2 baru dalam sebuah partisi, kemudian seluruh garis-garis linier disambung. Sedang linier interpolation adalah generalisasi dari piecewise constant interpolation.
.
Jadi sebenarnya, spline interpolation dapat juga dijuluki atau dilihat sebagai bagian dari nonlinier interpolation.
.
Generalisasi spline interpolation adalah konstruk polinomial variabel banyak dengan derajat yang sesederhana mungkin pada tiap-tiap hyperpartision.
.
Generalisasi spline interpolation berikutnya adalah konstruk non-linier dengan variabel banyak, misal untuk tiap-tiap hyperplane adalah fungsi eksponensial perubah banyak atau logaritmic variabel banyak atau fungsi-fungsi trigonometri variabel banyak.
.
Konstruksi polinomial ini berdasarkan hitungan-hitungan terhadap titik awal dan akhir dari partisi, lalu hitungan kurvatur atau turunan pertama atau turunan kedua atau turunan ketiga dan sebagainya.
.
[?]Bagaimana ilustrasi spline interpolation pada dimensi yang lebih tinggi:
Kita ambil contoh pada ruang berdimensi 3.
misal range data adalah sebuah bidang datar pada lantai ruang, bidang datar berbentuk segi empat.
Jika kita melihat dari atas,piecewise constant interpolation adalah seumpama membagi bidang datar/range data ke dalam partisi-partisi segi empat kecil yang warnanya konstan, menutupi seluruh bidang datar.
Tetapi jika dilihat dari samping, adalah seperti membagi ruang 3D dalam partisi-partisi datar kecil yang membentuk tangga-tangga.
.
Sedang sebuah linier interpolation, jika dilihat dari atas adalah seperti membagi bidang datar/range data dalam partisi-partisi segi empat yang warnanya bergradasi linier.
.
Sedang sebuah spline interpolation, jika dilihat dari atas adalah seperti membagi bidang datar/range data dalam partisi-partisi segi empat yang warnanya menyebar, memiliki titik warna pusat, selebihnya warna lain menyebar secara radial.
.
Selanjutnya imajinasi ini dapat kita generalisir ke dimensi yang lebih tinggi.
.
[?]Apa hubungannya antara gambaran spline interpolation dengan topologi?
Bismillah:
pertama kita dapat melihat bahwa konstruksi manifold adalah konstruksi yang analogi dengan spline interpolation pada dimensi yang lebih tinggi.
.
Kemudian konstruksi sebarang ruang topologi, dapat dilihat seumpama sebagai konstruksi spline interpolation pada sebarang dimensi.
.
[?]Mengapa spline interpolation atau sebarang jenis interpolasi dapat dilihat sebagai suatu cara aproksimasi?
Bismillah:
Ini karena sebarang titik data yang dihasilkan oleh populasi boleh jadi mengekspresikan atau mewakili sebuah fungsi yang kompleks atau sangat kompleks, atau memiliki kompleksitas yang tinggi (big Oh dengan polinomial tingkat tinggi atau eksponensial atau logaritmik atau kombinasinya).
.
Akan tetapi dengan melakukan interpolasi, kita mengkonstruksikan sebuah fungsi atau kumpulan fungsi sesederhana (polinomial sederhana dsb) yang melewati seluruh titik data.
.
Ini berarti interpolasi melakukan aproksimasi atau juga penyederhanaan terhadap fungsi yang kompleks tersebut yang mewakili kompleksitas populasi.
.
tetapi penyederhanaan oleh interpolasi adalah dalam dua tahap:
pertama, menyederhanakan kompleksitas hubungan antar titik data dalam suatu sampel data.
kedua, kontruksi kompleksitas sederhana ini digeneralisir untuk seluruh populasi, sehingga menyederhanakan kompleksitas populasi.
.
————————————————————
(3).
In this entry, we provide an account of the class of recursive functions, with particular emphasis on six basic kinds of recursion: iteration, primitive recursion, primitive recursion with parameters, course-of-value recursion, and double recursion.
.
Site ini menjelaskan 6 macam bentuk rekursif, tapi apa hubungannya dengan rekursif yang digeneralisir untuk pohon n-ner atau dalam sebarang graph berarah?
.
The recursive functions are characterized by the process in virtue of which the value of a function for some argument is defined in terms of the value of that function for some other (in some appropriate sense “smaller”) arguments.
.
Pertanyaan penting untuk bagian ini adalah:
Bagaimanakah sebenarnya bentuk mesin rekursif?
Bagaimana kita melihat fungsi rekursif sebagai mesin rekursif?
Bagaimana melihat 6 jenis dasar rekursif yang dijelaskan dalam site ini dilihat sebagai mesin rekursif?
.
Bagaimana cara mereka mengkonstruksikan fungsi rekursif dari 6 jenis rekursif dasar?
Bagaimana cara mebgkonstruksikan fungsi rekursif dari sebuah graph berarah?
Bagaimana cara mengkonstruksikan fungsi rekursif secar umum?
.
[embed-review:https://en.wikipedia.org/wiki/%CE%9C-recursive_function%5D
.
(1).
mu-recursive function = the µ-recursive functions are a class of partial functions from natural numbers to natural numbers that are “computable” in an intuitive sense.
.
Ackermann function = fungsi yang setara mu-recursive function(?), bisa merupakan mesin turing atau UTM?
.
Markov algorithms = algoritma yang setara mesin turing? bisa mensimulasika semua fungsi rekursif?
.
Bagaimana menggunakan mu-recursive function untuk membangun algoritma sebarang atau program komputer?
.
——————————————————————————————
[embed-review: http://people.irisa.fr/Francois.Schwarzentruber/recursive_functions_to_turing_machines/help_recursive_functions_syntax.html%5D
Bagaimana struktur sintaks yang global diterima orang?
Pertama:
Sebuah ekspresi fungsi rekursif, adalah sebuah fungsi, atau sebuah ekspresi fungsi.
yaitu sebagai berikut:
fungsi rekursif = [f=……]
.
jika kita membangun sebuah program komputer dengan seluruhnya berbasis fungsi rekursif, mungkin kita memiliki beberapa gagasan untuk itu, akan tetapi secara umum, pertama kali adalah sebagai berikut:
program = sebuah fungsi rekursif
atau:
program = sebuah fungsi rekursif yang memuat sejumlah fungsi rekursif.
atau:
program = sebuah barisan fungsi rekursif.
atau:
program = sebuah komposisi atau sebuah barisan komposisi fungsi rekursif.
.
contoh:
f=…..
g=…..
main=main(f,g,….)
.
dan seterusnya.
.
Tetapi secara umum, ekspresi global adalah sesuai konteks jenis rekursif yang kita ambil.
misal jenis primitif rekursif, iteratif, double rekursif,… dsb.
.
(2).
mengapa null function harus ada?
apa arti argumen bagi fugsi rekursif?
bagaimana cara menulis argumen pada fungsi rekursfi?
apa arti argumen bilangan asli dan return bilangan asli?
dimana kita meletakkan algoritma yang sebenarnya?
.
penggunaan argumen dan return bilangan asli, atau secara umum, eksistensi fungsi null dan fungsi suksesor adalah implementasi pendefinisian fungsi rekursif beradasarkan himpunan bilangan asli. dimana mungkin merekea hendak menerapakan filosofi induksi bagi fungsi rekursif.
.
sekarang, apa arti fungsi suksesor dalam definisi fungsi rekursif?
.
(3).
mesin rekursfi adalah sebuah mesin dengan input dan output.
inputnya adalah fungsi-fungsi rekursif(?)
——————————————————————————————
Mengapa fungsi-fungsi rekursif mengambil bilangan asli/integer sebagai argumen dan memberikan integer sebagai output?
dimana letak arti “compute” di dalamnya?
apakah yang dia compute?
bagaimana dia sejajar mesin turing?
bagaimana dia digunakan untuk memodelkan sebarang komputasi?
.
mengapa kalau suatu fungsi rekursif grow? mengapa jika dia grow quickly?
.
mengapa fungsi rekursif ackerman hanya mengkonstruksikan bilangan asli, seakan hanya mengenarlisir cara induksi matematika mengkonstruksikan bilangan asli, tetapi ackerman mengkonstruksikan dengan sangat cepat.
.
bagaimana kita menggunakan fungsi ackerman untuk memodelkan komputasi?
bagaimana kita menggunakan induksi matematika untuk memodelkan komputasi?
?
.
dimana posisi constant function, succesor function dan projection function pada gagasan fungsi rekursif?
.
#Inspirasi15:
Sebenarnya:
6 jenis rekursif yang mereka kemukakan hanyalah cara dasar untuk membangun fungsi rekursif.
.
fungsi ackerman dan semua fungsi-fungsi rekursif lainnya yang menerima input adalah bilangan non negatif integer dan mengembalikan non negatif integer, hanyalah semata fungsi rekursif khusus untuk integer.
.
mereka membangun suatu generalisai fungsi rekursif untuk bilangan bulat, itu saja.
semata untuk bilangan bulat.
.
6 jenis fungsi rekursif itupun adalah suatu skema global untuk membangun fungsi rekursif, tetapi tidak terbatas pada fungsi rekursif yang menerima argumen bilangan bulat, tetapi untuk seluruhnya jenis yang dapat dipetakan ke bilangan bulat atau sebaliknya.
.
penggunaanya ke komputasi, sebarang langkah-langkah algoritma dapat dipetakan ke bilangan bulat, sehingga argumen-argumen yang berupa bilangan bulat dapat digantikan oleh sebarang argumen yang 1-1 dengan himpunan bilangan bulat.
.
sebagai contoh, kita dapat menggantikan bilangan bilat pada fungsi ackerman dengan sebarang bilangan atau sebarang proposisi yang himpunannya adalah bijectice terhadap bilangan bulat.
contoh:
ackerman dalam bilangan bulat:
A(1,2)=A(1,A(1,1))
menjadi:
A(p1,p2)=A(p1,A(p1,p1))
dan seterusnya.
.
semua fungsi rekursif itu ditujukan untuk mengkonstruksikan bilangan integer.
filosofi ini dapat kita bawa untuk menerapkan fungsi-funsgi rekursif tersebut ke dalam komputasi.
misalkan kita memiliki algoritma dengan langkah-langkah:
p1,p2,p3,…,pn
.
oleh karena tiap-tiap p dipetakan dengan tepat ke suatu bilangan bulat i sehingga menjadi pi, maka konstruksi algoritma mulai dari p1 sampai pn dapat diekspresikan dengan fungsi rekursif, dengan memilih salah satu bentuk fungsi rekursif untuk bilangan bulat.
yaitu misal:
fungsi rekursif f:
f {
p0;
pn<–pn-1;
}
dan seterusnya.
.
ini berarti sebarang langkah-langkah komputasi dengan eksresi p1,p2,p3,…,pn
dapat dinyatakan ke dalam ekspresi fungsi rekursif.
.
tetapi ada beberapa jenis model fungsi rekursif yang bisa kita pilih.
.
berbagai jenis itu menghasilkan kompleksitas komputasi yang berbeda-beda.
yang lain mungkin dapat memodelkan komputasi paraleel dan dapat berhitung dengan sangat cepat, yang lain mungkin tidak, hanya berhitung dengan lambat.
.
sebagai contoh:
orang memiliki langkah-langkah komputasi p1,p2,p3,…,pn
mereka dapat memilih model fungsi rekursif yang berdasarkan primitive rekursif
atau memilih model fungsi ackerman.
lalu mengimplementasikan dalam bentuk bahasa pemrograman.
akan tetapi kecepatan model fungsi ackerman untuk mencapai langkah berikutnya adalah lebih cepat dibanding fungsi rekursif primitif.
.
pertanyaan yang tersisa:
dimana posisi ide fungsi konstan, susesor, dan proyeksi?
.
#End inspirasi15.
.
[PENTING1: Arti kerja Ackerman]
Apa yang dilakukan oleh ackerman, hanyalah mengeneralisasi cara orang untuk membangun bilangan asli secara rekursif, atau membuat variasinya.
.
Secara umum, semua fungsi rekursif demikian adalah generalisasi cara orang membangun fungsi rekursif untuk konstruk bilangan asli.
.
implementasinya pada komputasi bahwa, itu berarti generalisasi cara orang membangun langkah-langkah komputasi (algoritma) menggunakan cara rekursif.
.
[Artikel]
Sehingga, implementasi fungsi rekursif ke komputasi adalah sebagai berikut:
“Segala langkah-langkah komputasi yang terurut sesuai bilangan asli maka mesti dapat dinyatakan secara rekursif, dengan memilih berbagai model rekursif yang ada”
.
fungsi rekursif yang didefinisikan orang, misal oleh ackerman, jika dapat mensimulasikan aritmetika dan logika, maka otomatis secara intuitif dapat mengekspresikan sebarang bahasa pemrograman.
.
seumpama mesin register yang dibuat oleh minsky yang dapat mensimulasikan aritmetiak dan logika, sehingga dia dapat menjadi sebuah prosesor.
.
maka fungsi rekursif yang dapat mensimulasikan aritmetika, logika, maka dia dapat menjadi sebuah prosesor.
.
demikain pula bahwa fungsi lambda yang dapat mensimulasikan aritmetika dan logika maka dapat menjadi sebuah prosesor.
.
[?]Mengapa deret jumlah (kali atau bagi dsb) atau barisan adalah sesuatu yang dapat dinyatakan secara rekursif atau diekspresikan ke dalam mesin rekursif.
ini karena setiap suku dalam deret atau barisan dapat dipetakan dengan 1-1 ke bilangan asli, dengan bukti induksi, orang memverifikasi pemetaan 1-1 itu, kemudian karena dia 1-1, maka berbagai ekspresi rekursif konstruksi bilanan asli dapat digunaka untuk menyatakan deret tersebut.
.
[?]Apa hubungan antara bukti induksi dengan fungsi rekursif/mesin rekursfi?
Yaitu bahwa bukti induksi memverifikasi pemetaan bilangan asli ke langkah-langkah hitung atau algoritma atau komputasi, dan fungsi rekursif dipilih untuk mengekpsresikan algoritma tersebut sebagai sebuah mesin rekursif yang mengenerate seluruh langkah-langkah lagoritma.
.
[TRY]
try1:
fungsi yang menyatakan dirinya sendiri, misal:
x=x
atau f=f
adalah sebuah bentuk rekursif, sirkular menunjuk dirinya sendiri
.
try2:
bentuk fungsi rekursif yang dirumuskan dalam bentuk:
fungsi konstan f(n)=c, suksesor S(n)=n+1, proyeksi pin(1,2,3,4,…,i,….,n)=pi
adalah sebuah pernyataan dasar untuk konstruksi bilangan asli, tetapi ketika digunakan untuk sebarang langkah komputasi.
misal:
f = fungsi rekursif sebarang = sebuah langkah komputasi,
misal ada n buah langkah komputasi, sehingga ada n buah fungsi rekursif:
f1,f2,f3,…,fn.
maka:
1. f(fn)=fc atau f(fn)=c (ini merumuskan bagaimana dia memiliki titik tetap)
2. S(fn)=fn+1 (ini merumuskan bagaimana suatu fungsi rekrusif berpindah fungsi rekursif lain
3. pin(f1,f2,f3,f4,…,fi,….,fn)=fi
.
try3:
pelabelan fungsi rekursif menjadi f1,f2,f3,f4,…,fi,….,fn
atau pelabelan langkah-langakh komputasi, atau pelabelan proposisi-proposisi dalam langkah2 yang terurut.
tetapi kita dapat memodelkan langkah-langkah komputasi ke dalam 2-ary index atau 3-ary index, dan setersunya, sehingga memperluas bentuk fungsi rekursfi dengan 2 index atau 3 index.
misal fungsi rekuursif ackerman dengan 3 index.
.
contoh: f(1,2),f(3,4), dan seterusnya, sehingga kita bisa menggunakan fungsi ackerman untuk memodelkan langkah-langkah komputasi ini.
.
try4:
f(n)=c bisa kita artikan sebagai f(0)=c atau f(3)=c, atau f(0)=f3 yang memiliki arti bahwa langkah komputasi dalam bentuk rekursif dimulai pada langkah 3 atau fungsi rekrusif 3.
.
S(n)=n+1, bisa kita artian juga S(n)=n-1 atau S(n)=n+3 atau S(n)=n^2+n+1 dan setersunya.
.
bisa juga kita artikan secara rinci satu persatu yang menyatakan urutan langkah-langkah komputasi misal sebagai berikut:
S(1)=2, S(2)=3, S(3)=7, S(7)=1, dan setersunya.
.
try5:
impementasi ke komputer bisa sebagai berikut:
semua statemen langkah2 komputasi di taruh dalam memory kemudian di indeks sesuai langkah-langkahnya sesuai urutan bilangan asli, jika ada k-ary index maka diindekx dalam k-ary dst.
lalu sebuah mesin rekursif ditempat dimemori lain yang akan mengeksekusi semua langkah-langkah komputasi itu sesuai definisi fungsi rekursif pada dirinya sebagai mesin rekursif.
.
jika berpijak pada jenis rekursif, f(n)=c S(n)=n+1, dst, maka mesin rekursif mengeksekusi langkah2 yang sudah diindex sesuai jenis rekursif ini.
.
[END TRY]
.
[END PENTING1]
#END REVIEW3.
.

CATATAN SEPTEMBER 2017

CATATAN 1 SEPTEMBER 2017:
——————————————————————————————
sebelum logic sampling algorithm dijalankan, seluruh probability node (local probability) telah terhitung, baik itu given atau parameter learning.
.
logic sampling memilih state sebuah node dari sejumlah state yang dimiliki node tersebut.
likelihooh weighing juga memilih state tetapi dengan tambahan informasi bobot, terlebih dahulu membobot state2 tersebut.
bobot dari state adalah berdsarkan prior probabilitynya.
.
———————
Sort the nodes of the graph so that
parents always proceed children
=
urutkan semua node dari graph sedemikian rupa sehingga parent selalu di atas atau mendahului child.
.
seluruh node terbagi dua kategori, node evidence dan non-evidence, kategori ini terjadi manakala kita berdiri disebuah node, maka kita dapat melihat bahwa terdapat node yang menjadi evidence bagi node tersebut, dan mungkin terdapat node2 lain yang bukan evidence node tersebut. paling tidak adalah node tempat kita berdiri.
ATAU:
semua node evidence adalah semua node yang terobservasi atau memiliki nilai.
.
———————
Misalkan D adalah sebuah dataset, dan M adalah model dag bagi D, bagaimanakah mereka menghitung P(M|D)?
Apa artinya P(M)?
Apa artinya P(D|M)
cara menghitungnya?
.
misalkan jumlah model yang mungkin memodelkan D adalah M1, M2, M3,…, Mn
Bagaimanakah mereka menghitung distribusi probability untuk seluruh model?
Bagaimanakah mereka menurunkan setiap kemungkinan model?
———————
#Bagaimana menghitung P(D|M)?
misalkan diberi model M, lakukan prediksi terhadap D menggunakan M.
misal terdapat 100 rekord pada D, dan hasil prediksi M juga menghasilkan 100 rekord.
jika terdapat 20 rekord salah prediksi, maka P(D|M)=80/100.
sehinga:
P(D|M) = jumlah prediksi benar/jumlah rekord D keseluruhan
.
#Bagaimana menghitung P(D)?
1 item observasi = 1 rekord data.
observasi = himpunan rekord
.
misalkan kita memiliki data D 100 rekord dari observasi pendahuluan.
jika kita melakukan observasi ulang dengan 100 item observasi.
jika terdapat 40 item yang terulang sempurna pada D, maka probability P(D)=40/100.
.
#Bagaimana menghitung P(M)?
jika kita memiliki n model yaitu M1,M2,M3,…,Mn
and there is no apriori information in favor M1,M2,M3,…,Mn then p(Mi)=1/n
selebihnya if there is apriori information then we can assign every P(Mi) according to their weight.
.
#Bagaimana menghitung P(M|D)?
gunakan teorema bayes.
.
————————————-
#Bagaimana pengertian likelihood?
Secara umum berarti:
Nilai kemungkinan/probabilitas suatu entitas relatif terhadap suatu entitas atau set entitas lain.
.
misal entitas itu set.
maka likelihood X menurut set Y adalah P(X|Y) atau f(X|Y)
.
misal entitas itu agregat suatu set, atau parameter suatu set, atau representasi suatu set berupa fungsi dan sebagainya.
misal agregat itu atau parameter itu adalah theta.
theta adalah parameter atau set parameter yang menjadi representasi set Y, tulis thetaY.
maka likelihood X menurut thetaY adalah P(X|thetaY) atau f(X|thetaY).
f(X|thetaY) bisa jadi merupakan sebuah fungsi padat peluang.
P(X|thetaY) adalah fungsi distribusi.
.
Maximum likelihood estimation = perkiraan kemungkinan maksimum.
itu berarti nilai maksimum yang mungkin dari max{P(X|thetaY)} atau turunan pertama nol yaitu df(X|thetaY)/dx=0.
.
——————————————————————————————
#Apa gunanya logic sampling atau likelihood weighin?
untuk melakukan inferensi.
inferensi dalam graph probabiliy = memilih path inferensi yg paling besar kemungkinannya.
jadi sebenarnya logic sampling atau likelihood weighing adalah algoritma memilih path inferensi.
.
ini berarti cpquery yang bekerja berdasarkan logic sampling atau likelihood weighing sebenarnya adalah cp inferensi.
.
mengapa inferensi?
contoh inferensi:
jika A,B,C maka D (inferensi 1)
jika B,C maka D (inferensi 2)
jika K,B,C maka D (inferensi 3)
.
inferensi 1 berarti cp P(D|A,B,C)
inferensi 2 berarti cp P(D|A,B)
inferensi 3 berarti cp P(D|K,B,C)
.
akan tetapi dalam grap belief network boleh jadi antara A,B,C,K dan D terdapat puluhan node lain yang tidak diketahui nilainya (tak terobservasi) sehingga hanya A,B,C,K yang terobservasi.
ATAU:
A,B,C,K melewati ratusan kombinasi jalan node ke node yang tak terobservasi hingga sampai ke D, maka algoritma memilih path yang maksimum probabilitnya.
dengan syarat semua probability lokal (probability tiap node) dan global telah diketahui
.
algoritma (logic sampling atau likelihood weighing) memilih yang cp maksimum.
.
ini menunjukkan uncertinitity pada model.
.
——————————————————————————————
#Apakah marginal probability?
unconditional probability.
lawan dari conditional probability.
misal conditional probability P(X|Y)
maka marginal probability adalah P(X)
ATAU:
misal joint probability P(X,Y)
maka masing2 marginal probability untuk X dan Y adalah P(X) dan P(Y).
akan tetapi secara (X.Y) maka P(X.Y) adalah marginal juga.
ATAU:
marginal probability = prior probability.
.
tetapi ini secara umum digambarkan dalam definisi cp sebagai berikut:
conditional probability = joint probability/marginal probability.
——————————————————————————————
Aku sering merasa takut pada bulan yang penuh
ketika suatu saat berdiri di tempat yang tinggi
dengan cahayanya yang kuat…
di kala malam yang bertiup…
bulan seakan memandangku dan aku seperti semata berdiri sendiri…
.
entah rasa apa yang aku miliki…
yang aku tau aku hanya seakan lari menjauhi…
melompat dari tempat yang tinggi…
dan bergelayut di sebuah pohon menahan diri…
.
dari sebuah mimpi di beberapa puluh tahun yang lalu…
.
dan aku selalu mengenangnya…
dan bertanya…
mengapa?
.
——————————————————————————————
dynamic decision making in node to node communication?
=
pengambilan keputusan yang bergerak, setelah memutuskan memilih node dari sejumlah node, maka berikutnya berpindah ke node pilihan, lalu memutuskan lagi memilih node dari sejumlah node sampai sampai.
.
propagating belief network values?
=
memilih node adalah proses belief, merambatkan keputusan node ke node adalah merambatkan belief ke belief selanjutnya.
yaitu bahwa kita memutuskan pilihan berdasarkan kepercayaan atau belief.
.
a brute force algorithm for propagating belief network values?
= berarti percaya/belief secara brute force.
.
——————————————————————————————
Bagaimana merambatkan belief secara brute force pada network dengan 2 node?
Bagaimana mengeneralisirnya ke n node?
.
#Apakah joint probability suatu network/dag?
misalkan network memiliki n node.
tiap node memiliki secara berturut2 jumlh state adalah:
untuk jumlah state node1=m1, secara umum jumlah state node-n=mn.
.
maka state dari network adalah kombinasi yang mungkin dari state2 seluruh node.
sehingga jumlah state dari network = m1xm2xm3x…xmn
untuk setiap state dari network adalah memiliki joint probability.
jadi yang dimaksud:
joint probability network = joint probability suatu state dari network.
.
karena itu jika terdapat m1xm2xm3x…xmn state dari netwok,
maka itu berarti terdapat m1xm2xm3x…xmn joint probabilit network.
.
misal state node1=k1, state node2=k2, …, state node-n=kn
maka state network dinyatakan sebagai tupel state tersebut, yaitu (k1,k2,k3,…,kn).
misal node-i=Xi.
.
dan joint probability pada saat state (k1,k2,k3,…,kn) adalah P(X1=k1,X=k2,…,Xn=kn)
dan marginal probabilitynya adalah P(X1=k1),P(X=k2),…,P(Xn=kn)
.
secara total, joint probability network secara total adalah 1, yaitu:
P(X1,X2,X3,…,Xn)=1=Sum(P(X1=ki1,X=ki2,…,Xn=kin)), i=1,2,3,…
.
akan tetapi dalam algoritma yang ditawarkan oleh brute force, seluruh nilai dinormalkan oleh node event.
.
#Bagaimana memilih path perambatan belief?
gampang saja, tinggal pilih yang paling besar joint probabilitynya.
.
akan tetapi jika jumlah state dari network adalah sangat besar, dalam hal ini seluruh kombinasi state network membangun suatu state space.
.
state space = himpunan seluruh state dari network, tiap2 state punya joint probability sendiri (yang bisa dihitung seluruhnya atau hanya sebgain saja jika banyaknya state network sangat besar atau tak hingga). tetapi joint probability total dari network adlh 1. hanya saja mungkin tidak lagi diperhatikan joint probability total dari network, manakal tiap2 joint probability dimanipulasi (misal dinormalkan) sehingga total joint probability tidk memiliki arti lagi untuk di pertimbangkan.
.
jika ukuran state space sangat besar, atau tak berhingga (misal salah satu dari node memiliki state yang tak hingga tak terbilang, berupa bilangan real), maka tidak mungkin menghitung joint probability setiap state network.
.
apa yang dilakukan adalah memilih sejumlah state saja atau subset state dari state space.
memilih state itu adalah yang hanya memiliki node yang terobservasi (evidence), akan tetapi mungkin juga ini jumlahnya sangat besar atau tak hingga, sehingga hanya dipilih suatu subset saja.
.
kemudian dari pilihan subset tersebut, dilakukan perhitungan perambatan belief atau perhitungan joint probability untuk tiap2 state network yang ada dalam subset state space.
.
kemudian hasil joint probability dinormalkan, dimanipulasi sesuai algortima yang dipilih, lalu dijadikan nilai score untuk path network pilihan.
.
path network inilah (joint probability atau score nya) yang menjadi bahan untuk melakukan inferensi.
.
kemudain cp dalam network ini dapat dihitung dengan menggunakan joint probability tersebut.
.
#Apakah cpquery dalam bahasa R?
cp yang dihitung dari joint probability/score yang terpilih.
.
#Apakah cpdist dalam bahasa R?
menampilkan semua path atau net dari subset state space yang telah dipilih.
.
——————————————————————————————
#Skenario hitung:
net/dag/path sudah diketahui.
data tersedia.
aliran cp dapat diketahui.
.
untuk 1 path.
generate tabel yang menghitung setiap jp dari state path.
setiap rekord tabel = state setiap node|state path|jp state path
.
lalu buat score setiap state path:
state node1|state node2|…|state node-n|state path/net|jp net|score net
.
misal net: A–>B
.
state A|state B|state [A][B|A]|jp [A,B]=[A][B|A]|score [A,B]|
.
pilih net dengan score [A,B] tertinggi. untuk suatu nilai variabel evidence A tertentu.
jumlah rekord untuk suatu evidence A tertinggi adalah m untuk m jenis state dari B.
tetapi jumlah ini bisa tak hingga jika B numerik.
sehingga hanya bisa dipilih suatu subset rekord dari tabel.
ini dilakukan pengambilan keputusan dengan memilih sejumlah rekord saja.
.
misal terpilih [A=x,B=y]=[A=x][B=y|A=x]…..(1)
.
maka cpquery dihitung berdasarkan (1) yaitu:
cpquery=[B=y|A=x]=[A=x,B=y]/[A=x]
.
dan cpdist= set A=x–>B=y yang digunakan pada subset rekord tersebut.
.
#Skenario ini lebih luas jika:
A–>C–>D–>B
maka tabel yang digenerate adalah tabel [A][C|A][D|C][B|D]
jika hanya A yang diobservasi yaitu A=x, C, dan D tidak, sedang kita menginginkan B=y.
.
semua rekord yang terpilih adalah dimana A=x dan B=y.
tetapi semua rekord yang memuat semua kemungkinan nilai C dan D diambil.
.
lalu net [A=x][C|A][D|C][B=y|D] diberi score untuk setiap statenya (state net).
lalu dipilih yang maksimum nilainya.
.
lalu cpquery dihitung untuk net yang maksimum nilainya.
cpquery(data, B=y, A=x)=P[B=y|D=d]
diambil dari P(X=a,C=c,D=d,B=y)=P[A=x].P[C=c|A=x].P[D=d|C=c].P[B=y|D=d]
dimana C=c dan D=d adalah nilai yang memaksimumkan score net [A=x][C|A][D|C][B=y|D], c dan d diperoleh dari rekord pada tabel dimana score dari rekord adalah maksimum.
.
cpdist=set D–>B=y atau [B=y|D] yang digunakan untuk menghitung [A=x][C|A][D|C][B=y|D]
.
#Generalisasi skenario:
kasus di atas hanya ada satu bentuk net yang diperoleh yaitu net [A=x][C|A][D|C][B=y|D], kemudian di generate tabelnya untuk mencari score maksimumnya.
.
bisa jadi ada k buah net atau path atau lintasan yang mungkin yang diperoleh.
sebut:
net 1= net [A=x]…[B=y|…]
net 2= net [A=x]…[B=y|…]
net 3= net [A=x]…[B=y|…]
.
.
.
net k= net [A=x]…[B=y|…]

dimana “…” memiliki arti sebarang node yang dilewati, antar net yang berbeda bisa berbeda2.
.
maka tabel digenerate untuk net [A=x]…[B=y|…] secara keseluruhan.
lalu kerjakan seperti sebelumnya.
diperoleh:
cpquery(data, B=y, A=x)=P[B=y|…] diambil dari net [A=x]…[B=y|…] yang maksimum.
.
cpdist = set …–>B=y atau [B|…] yang digunakan menghitung net [A=x]…[B=y|…].
.
#Generalisasi lebih luas lagi:
Misal bukan hanya A yang terobservasi atau evidence, tetapi A1,A2,A3,…,An dan B1,B2,B3,…,Bm
.
tulis secara umum path/net/dag yang memuat node2 terobseravasi sebagai:
net(evidence=A1,A2,A3,…,An, event=B1,B2,B3,…,Bm)
.
generate tabel yang tiap2 rekordnya memuat kombinasi state (dan juga jp masing2 kombinasi) sebagai berikut:
A1,A2,A3,…,An|?,?,?,…..|B1,B2,B3,…,Bm|net|jp net|score net|
dan seterusnya dengan cara yang sama kita dapat menghitung cpquery dan cpdist.
.
—————————————————————————————————
Bagaimana cara skoring?
Markov blanket?
Cara skoring dalam hc dan sejenisnya?
.
——————————————————————————————
#Apakah model statistik?
Model statistik = set assumsi pdf atau pmf + koleksi set parameter untuk pdf atau pmf tersebut.
secara umum ditulis:
Model statistik = f(x|theta)
dimana f adalah pdf atau pmf dan theta adal set parameter untuk f.
.
Model statistik = {fi(Xi|theta-i)|i=1,2,3,…, Xi=(Xi1,Xi2,Xi3,…)}
.
——————————————————————————————
#Apakah fungsi likelihood?
Review: https://en.wikipedia.org/wiki/Likelihood_function
.
Likelihood is used after data are available to describe a function of a parameter (or parameter vector) for a given outcome.
=
Likelihood ada atau eksis atau term ini digunakan manakala dataset telah tersedia dari eksperimen atau dari fenomena. Likelohood pada posisi ini digunakan untuk menjelaskan sebuah fungsi dari parameter dari outcome yang diberikan.
=
Mengapa setelah data ada? karena jika data ada maka seluruh parameter dapat ditentukan, yaitu parameter mean dan standar deviasi atau parameter2 lain.
Kemudian menggunakan parameter2 ini, sebuah fungsi pdf atau pmf yang diassumsikan untuk dataset (set outcome) adalah dapat dikonstruksikan.
.
Probability is used before data are available to describe possible future outcomes given a fixed value for the parameter (or parameter vector).
=
Istilah probability digunakan ketika data belum tersedia (atau juga mungkin telah tersedia tetapi kita tak tertarik menghitung parameter2nya) kemudian berdasarkan metode frequentis (jika data telah tersedia) atau metode lain, probabiloity dari tiap2 outcome diprediksikan atau diassumsikan.
.
Ini adalah perbedaan penggunaan istkilah likelihood dan probability, walaupun keduanya sama senbagai kemungkinan.
—————————————————————————————————
dalam komposisi teorema bayes:
P(H|X)=P(X|H).P(H)/P(X)
.
P(X|H) dikatakan likelihood karena dia dihitung setalah data ada atau dihitung berdasarkan data.
P(H) dikatakan prior dari H karena dalam tinjauan ini dia dihitung sebagai marginal probability dan dihitung setelah data ada sebelum P(H|X).
P(X) hanya sekedar marginal probability (entah data ada atau tidak).
P(H|X) dikatakan posterior karena dihitung setelah perhitungan likelihood dan prior, dan setelah data ada.
——————————————————————————————

CATATAN YANG BERMULA DI PERPUS UGM

Bagaimana mereka memasang time atau clock pada automata secara umum?
Bagaimana memasang time atau clock pada probabilistik automata?
—————————————————————————————
Bagaimana timed automata memodelkan sistem?
Bagaimana probabilistic automata memodelkan sistem?
Bagaimana orang menggabungkan gagasan timed dan probabilistic automata?
—————————————————————————————
Review:https://arxiv.org/pdf/1703.08936.pdf
(1).
Pada dasarnya, timed dan probabilistic adalah behavior atau law yang dapat melekat pada suatu sistem.
.
Jika sebuah sistem memiliki behaviour: timed
maka dia mungkin dapat dimodelkan dengan timed automata.
.
Jika sebuah sistem memiliki behaviour: probabilistic
maka dia mungkin dapat dimodelkan dengan probabilistic automata.
.
Jika sebuah sistem memiliki behaviour: timed dan probabilistic
maka dia mungkin dapat dimodelkan dengan timed probabilistic automata.
.
(2).
Mengapa sistem navigasi memiliki behaviour: timed dan probabilistic?
karena :
sistem navigasi = sistem panduan untuk berjalan di atas sebuah graph (peta, dan sebagainya).
.
Probabilistic:
sehingga mungkin terdapat n pilihan untuk memilih suatu jalan atau arah atau edge atau click (pada peta tree dari web) dan sebagainya.
ini berarti sistem navigasi adalah bersifat probabilistic.
.
Timed:
karena setiap jalan yang dipilih untuk ditempuh mungkin memiliki waktu tempuh, atau edge atau state atau lokasi memiliki waktu tinggal yang dibolehkan atau tidak.
sehingga sistem navigasi bisa timed.
bisa disebut sebagai sistem navigasi yang critical (memiliki konstrain2 atau titik kritis utnuk suatu jalan yang ditempuh atau lokasi yang dicapai).
.
(3).
Mengapa web security memiliki behaviour: timed dan probabilistic?
pertama:
karena web bisa diprepresentasikan dalamkonsep peta, berupa graph tree, yang ada jalan dan lokasi atau ada node dan edge atau ada halaman dan link.
yang berarti ada kemungkinan percabangan pilihan jalan atau edge.
yang berarti probabilistic.
.
kedua:
sebagai cara security, sebuah lokasi atau node atau sebuah halaman memiliki definisi waktu atau clock waktu hidup, sehingga jika expaire maka harus di refresh ulang atau login ulang atau memasukkan kredensial user kembali, secara umum, setiap node atau lokasi atau halaman diberi clock waktu hidup atau waktu terbuka, dan sebuah koneksi oleh link juga mungkin memiliki clock untuk memberi waktu bagi lamanya usaha koneksi yang diijinkan.
.
(4).
Mengapa algoritma trading memiliki behaviour: timed dan probabilistic?
Pertama:
trading memberi pilihan2 untuk membeli item atau pilihan2 cara melakukan transaksi, atau perhitungan2 resiko pembelian yang memberikan pilihan2 pada trading.
ini berarti dia bersifat probabilistic.
.
Kedua:
dalam trading mungkin ada batas2 waktu penawaran sebuah item, jika batas itu lewat maka item boleh ditawar orang lain, jika batas pembayaran melampaui jatuh tempo maka item batal dijual atau ditarik ulang dan sebagainya.
maka trading bersifat timed.
.
Ketiga:
ini berarti usaha2 orang untuk membangun algoritma trading adalah berarti memperhitungkan behaviour timed dan probabilistic.
.
(4).
Mengapa search-engine optimization memiliki behaviour: timed dan probabilistic?
Pertama:
sebuah mesin pencari sebenarnya dapat dilihat sebagai bot yang sedang berjalan di jejala internet (peta), karenanya dia mesti menemui pencabangan2 pilihan untuk memilih ke arah mana berjalan terlebih dahulu untuk melakukan pencarian.
karena itu dia menjadi probabilistic.
.
Probabilistic:
misalnya pada pengalaman pencarian sebelumnya, dia lebih sering menemukan targetnya pada jalan a dibanding jalan b dan c, maka pada kali berikutnya jika hendak mencari maka probability untuk menempuh jalan a terlebih dahulu menjadi lebuh besar.
secara umum dia merangking pilihan jalan berdasarkan probabilitasnya.
.
Timed:
untuk setiap jalan yang dia tempuh dia harus menghitung waktu tempuh rata2 atau yang mungkin, sehingga model pencarian mejadi timed.
.
(5).
Mengapa communication protocol design memiliki behaviuor: timed dan probabilistic?
Pertama:
Sebuah komunikasi adalah pengiriman paket data ke belantara jejala internet atau jejala komunikasi. ini berarti disana terjadi banyak pilihan rute (route) untuk ditempuh.
Sebuah protokol yang belajar, mestinya waktu kewaktu menghitung probability setiap rute untuk ditempuh, probability dalam artian yang mungkin banyak jenis probabilitynya, mungkin probabilitas kemanaan paket, probabilitas kerusakan data bila melewati rute tertentu, probabilitas kepadatan lalulintas data pada jam2 tertentu bagi rute2 tersebut dan sebagainya.
Karenanya dia menjadi probabilistic.
.
Kedua:
Sebuah komunikasi tentunya menghitung kecepatan tempuh dari jalan2 atau rute2 yang ditempuhnya, memberi batasan atau clock untuk menerima ACK sehingga bisa menentukan kapan mengirim ulang data karena kemungkinan hilang atau error dans sebagainya.
Karenanya dia menjadi timed.
.
(6).
Mengapa hardware failure prediction memiliki behaviour: timed dan probabilistic?
Pertama:
Karena sistem harus bisa memprediksi, kapan riap2 hardware harus memberi respon (timed) untuk memutuskan bahwa hardware bekerja baik atau failure.
Karenanya sistem adalah timed.
.
Kedua:
Sistem juga harus bisa membangun tabel probabilistic tentang peluang tiap2 device mengalami kerusakan jika terdapat n buah tanda tertentu.
Karenanya sistem adalah probabilistic.
.
——
Bagaimana Model Checking problem memodelkan setiap automata?
Bagaimana Model Checking problem memodelkan petri net, timed-automata, timed-probabilistic automata?
——
(1).
Sepertinya orang menentukan sifat decidablity suatu automata, petri net, atau secara umum sebuah metode formal dengan menggunakan Model Checking.
.
Bagaimana orang menentukan sesuatu metode formal/automata adalah decidable menggunakan model checking?
.
(2).
Sepertinya gagasan utama untuk menerjemahkan sebuah automata atau metode formal ke dalam model checking adalah menerjemahkan automata atau model formal tersebut ke dalam himpunan run.
.
Model checking automata/metode formal = himpunan running dari automata/metode formal dan penurunan semua sifat2 yang mungkin dari himpunan tersebut, lalu pengecekannya.
.
Sepertinya, sebuah automata/model formal dikatakan decideable dalam model checking jika hanya jika setiap run adalah decidable, artinya setiap run dapat ditentukan mencapai target atau mencapai bukan target.
Jika dia tidak dapat ditentukan mencapai target atau tidak di suatu ujung run, maka dia undeciabla.
.
——————————————————————————————
#IDE:
Kita dapat melihat bahwa konsep pohon keputusan adalah konsep untuk mempartisi sebuah gerombolan titik (rekord) di ruang.
Dalam arti lain mempartisi bisa juga diartikan mengklaster.
.
Secara umum, seluruh algoritma mining rule dapat dilihat sebagai algoritma untuk mempartisi segerombolan (crowded) titik di ruang berdimensi n.
Atau sebuah algoritma untuk mem bangun cluster-cluster di ruang berdimensi n.
.
Secara umum kita juga dapat melihat bahwa sebuah himpunan partisi dalam ruang dapat dilihat sebagai berikut:
Himpunan partisi = set rule
Atau:
Himpunan cluster = set rule
.
Tetapi bisa juga:
Himpunan partisi = jaringan syaraf tiruan
sehingga:
Jaringan syaraf tiruan = set rule.
.
Jaringan syaraf tiruan = set rule
menghaislkan suatu pandangan:
Suatu himpunan anteseden diwakili oleh suatu himpunan neuron input.
Suatu himpunan konsekuen diwakili oleh suatu himpunan neuron output.
.
Akan tetapi suatu himpunan neuron input tidak saja mewakili suatu himpunan anteseden suatu rule, tetapi dapat mewakili n buah himpunan anteseden dari n buah rule.
Dalam artian bahwa, jika kita memiliki n buah rule, maka n buah rule dapat diwakili oleh sebuah jaringan syaraf tiruan.
.
Artinya bahwa kita dapat mengumpulan sebuah set rule, kemudian kita dapat mentraining sebuah jarigan syaraf tiruan X, dimana X dapat mewakili seluruh rule dalam set rule.
.
Dengan demikian, kita juga bisa menghitung entropy sebuah jaringan syaraf tiruan.
Ide itu sebagai berikut:
H(neuron input) = -p1i.Log ? + ….
H(neuron output) = -p1o.Log ? + ….
H(jaringan syaraf tiruan) = H(neuron input) + H(neuron output)
.
Jika kita membawa ini kedalam konsep matematika, kita juga menemukan suatu pandangan bahwa sebarang ruang berdimensi n dapat direpresentasikan oleh suatu graph (tree dsb).
atau sebarang manifold berdimensi n dapat direpresentasikan oleh sebuah graph.
.
Nyatakan ruang atau manifold sebagai suatu komposisi dari k buah ruang/manifold, selanjtnya setiap dari k buah subruang itu dapat dibagi lagi dalam k1 subsubruang, dan setersunya, sehingga kita dapat mempresentasikan ruang dalam sebuah tree atau secara umum graph.
.
Ini juga memberi pandangan baru bahwa sebuah jaringan syaraf tiruan dapat merepresentasikan:
sebuah jaringan syaraf tiruan = sebuah ruang berdimensi n atau manifold n.
.
Juga bahwa:
sebuah jaringan syaraf tiruan = sebuah graph.
.
Juga berarti bahwa:
sebuah jaringan syaraf tiruan mewakili set transisi dalam automata.
sehingga:
sebuah jaringan syaraf tiruan = sebuah automata
sebuah jaringan syaraf tiruan = set instruksi
sebuah jaringan syaraf tiruan = sebuah mesin turing
.
Juga berarti bahwa:
sebuah jaringan syaraf tiruan = set rule grammar
sebuah jaringan syaraf tiruan = sebuah bahasa
.
Sehingga sebuah bahasa dapat digenerate oleh sebuah jaringan syaraf tiruan.
Atau sebaliknya bahwa sebuah jaringan syaraf tiruan dapat menjadi parser sebuah bahasa.
.
Kita dapat mengerti bagaimana orang dapat membuat AI (jaringan syaraf tiruan) yang dapat mengenali sebuah manuskrip kuno, misal bahasa Ibrani dan sebagainya pada temuan-temuan arkeologi, dapat menerjemahkan dan sebagainya.
.
Tentang bagaimana jst melakukan deduksi panjang?
Salah satunya mungkin adalah training yang rekursif terhadap suatu jst.
dalam cara pandang rekursif ini, misal dalam skema yang sederhana:
A+noise –> B
B+noise –> C
C+noise –> D
lalu sebuah jst X yaitu x–>y
deduksi X adalah sebagai berikut:
training1:
x=A+noise
y=B
training2:
x=B+noise
y=C
training3:
x=C+noise
y=D
——-
Atau:
training:
x=A+noise
y=B
x=B+noise
y=C
x=C+noise
y=D
.
Tetapi bagaimana jst digunakan untuk melawan pemain catur atau Go?
Bagiamana jst melakukan deduksi?
Bagaimana jst melakukan deduksi panjang secara unisupervised?
Bagaimana jst berhitung probability atau melakukan deduksi probabilistik?
Bagaimana jst melakukan deduski secara fuzzy?
.
#END IDE
.
PSPACE?
Decidablity problem?
——————————————————————————————
SEPUTAR HALING PROBLEM:
——————————————————————————————
Halting problem:
(1).
Sebuah gagasan pembuktian yang sederhana dari http://www.comp.nus.edu.sg/~cs5234/FAQ/halt.html.
Garis besar pembuktian adalah sebagai berikut:
Halting problem diformalkan sebagai sebuah himpunan HALT dimana
HALT={<M,I>| dimana M mesin turing yang halt pada input I}
.
Apakah ada mesin H dimana H dapat menentukan bahwa semua elemen HALT memenuhi sifat bahwa dia bakal halt pada input I atau loop selamanya?
.
karena <M.I> maka orang juga bisa menulis <M,M> yaitu bahwa mesin M menerima M sebagai inputnya (M dienkoding ke dalam string).
ini berarti H dapat menentukan bahwa <M,M> bisa halt atau loop selamanya.
.
pembuktian ini mencoba membuktikan bahwa H tidak dapat membuktikan secara general untuk setiap elemen HALT.
dengan menunjukkan bahwa dia tidak dapat menentukan <M,M>.
.
cara pembuktian http://www.comp.nus.edu.sg/~cs5234/FAQ/halt.html, adalah membawa konteks halting problem ke dalam program, yaitu bahwa menunjukkan tidak ada program yang dapat bersifat sebagai H.
.
beberapa pembuktian lain menggunakan mesin turing.
tetapi bagaimana menggunakan jenis model komputasi lain untuk membuktikan halting problem?
misal menggunakan fungsi rekursif atau lambda calculus atau menggunakan grammar?
ini adalah wawasan yang menarik.
.
(2).
Apakah oracle machine?
mesin yang bisa mensimulasikan mesin lain, atau meta mesin(?), akan tetapi lebih spesifik, yaitu bahwa mesin itu bersifat oracle (bijaksana, memberi keadilan, memberi putusan) bahwa sebuah mesin bisa halt atau loop forever terhadap input yang diberikan kepadanya.
.
oracle machine = mesin yang bisa mengevaluasi mesin lain.
——————————————————————————————
(3).
#Apakah efisien dan tak efisian bagi sebuah algritma atau mesin turing?
Sebuah algoritma atau mesin turin adalah inefisien (tidak efisian) dalam menerima suatu himpunan input jika hanya jika dia mencapai waktu yang kompleksitasnya eksponensial.
.
sebaliknya sebuah algoritma/mesin turin adalah efisien terhadap suatu himpunan input jika hanya jika dia dapat menyelesaikan himpunan input itu dalam komlleksitas waktu yang polinomial biasa (secara aljabar, atau polinom misal a1x1 + a2x^2 + a3x^3 +… dan seterusnya.
.
(4).
#Apakah yang dimaksud problem dalam komputasi?
#Atau bagaimana komputasi merumuskan secara abstrak sebuah problem?
Problem = apakah/bagaimanakah/kapankah/dsb sebuah algoritma/mesin turing yang menerima himpunan n-array string input menghasilkan suatu m-array string output.
.
(5).
#Bagaimana kita melihat sifat general dari cara pembuktian orang akan halting problem dengan menggunakan program yang mengeksekusi dirinya sendiri (loop in self)?
Pada dasarnya ini adalah konsep rekursif,sedang kita telah mengetahui sebelumnya bahwa fungsi rekursif atau konsep rekursif adalah sesuatu yang universal atau sesuatu yang dapat memodelkan komputasi sebagai mesin turing melakukannya, dan bahwa konsep rekursif ekivalen dengan mesin turing.
.
Sehingga menggunakan konsep rekursif untuk membuktikan halting problem adalah ekivalen dengan membuktikannya secara universal.
.
(6).
#Apakah decision problem?
Decision problem = segala problem (seperti konsep problem yang dinyatakan pada point (4)) dimana m-array outputnya adalah (yes,no).
.
#Apakah undecideable?
Undecideable = unsolvable Decision problem. Yaitu tidak ada mesin/algoritma yang dapat menghasilkan (yes,no) untuk decision problem.
.
(7).
#Bagaiaman sebuah jaringan syaraf tiruan X(i1,i2,…,o1,o2,…) dapat merepresentasikan/mensimulasikan sebuah prosesor?
Prosesor = set/graph fungsi logika boolean.
untuk suatu tupel-n input (x1,x2,…,xn) dan suatu tupel-m output (o1,o2,…,om) dari X, dapat dibuat sedemikian rupa untuk merepresentasikan sebuah set fungsi logika dan jejala deduksi yang dibangunnya.
dan suatu tupel-k input (xn+1,xn+2,…,xk) dapat digunakan untuk mempartisi graph jejala fungsi logika.
.
demikian seterusnya dimana deduski dalam suatu partisi ditraining ke X dan partisi lain dengan merubah-rubah nilai tupel-k input (xn+1,xn+2,…,xk).
demikian sehingga secara lengkap merepresentasikan kerja sebuah prosesor.
.
(8).
#Bagaimana sebuah jaringan syaraf tiruan dapat mewakili atau merepresentasikan sebuah RAM atau memory atau juga hardisk?
#Atau bagaimana sebuah jst menyimpan data atau menjadi memory?
Untuk setiap tupel-n input, diberi nilai dengan alamat-alamat sel, jadi neuron2 input menyatakan alamat-alamat sel dalam memory RAM.
kemudian untuk output adalah nilai bit atau informasi yang disimpannya pada alamat tersebut.
jst dilatih untuk menyimpan dengan cara ini.
tetapi dlam konteks jst, sebuah alamat boleh lebih dari 1 yang menyatakan nilai sel yang sama.
.
Sehingga untuk membaca sebuah nilai yang disimpan oleh jst, kita hanya perlu mensuplai alamat sel pada neuron2 input, maka jst memberikan nilai sel pada pada output.
.
Secara umum, beginilah jst menyimpan informasi.
mengingat gambar2 kucing dan mengenalinya.
.
konsep penyimpanan ini lebih baik, karena dapat menyimpan informasi secara abstrak atau dengan batasan yang kabur dan dapat menggunakannya kembali sebagaiaman manusia mengingat.
——————————————————————————————
Bagaimana orang membuktikan halting problem menggunakan mesin turing?
Misalkan terdapat mesin turing H yang menerima input <M,I> dan selalu dapat memberi keputusan yes dan no terhadap seluruh <M,I> dalam himpunan HALT.
.
Tulis H sebagai H(M,I) ketika menerima <M,I>.
.
buat sebuah mesin oracle Z (mesin turing) yang memuat mesin H, Z bekerja dengan cara:
jika Z menerima input M (Z inputnya adalah mesin M) maka M diteruskan ke H sebagai <M,M>, karena H selalu dapat memberi keputusan yes dan no, H memberi keputusan yes untuk input <M,M> maka Z halt jika H memberi keputusan no maka Z loop forever.
.
tetapi <M,I> adalah sebarang dalam HALT, dan <Z,I> mestilah juga bagian dari HALT. Ambil M=Z dan I=Z (M bisa menerima input mesin juga) sehingga diperoleh <Z,Z>.
.
inputkan Z ke dalam mesin Z.
maka Z diteruskan ke H sebagai <Z,Z>.
.
<Z,Z> diterima oleh mesin H, karena H diassumsikan memberi yes dan no bagi setiap <M,I> sebarang maka H juga memberi yes dan no bagi <Z,Z>.
.
misalkan <Z,Z> adalah yes menurut H, maka itu artinya Z halt pada input Z.
tetapi kemudian dalam diri Z, jika H memberi yes maka Z loop forever, berakibat bahwa Z loop forever untuk input Z.
kontradiksi yaitu bahwa Z halt dan juga sekaligus loop forever.
.
misalkan <Z,Z> adalah no menurut H, maka itu artinya Z loop forever pada input Z.
tetapi kemudian dalam diri Z, jika H memberi no maka Z halt, berakibat bahwa Z halt untuk input Z.
kontradiksi yaitu bahwa Z loop forever dan juga sekaligus halt.
.
——————————————————————————————
#Bagaimana orang membuktikan equivalence problem?
——————————————————————————————
#Bagaimana menenkoding H(M,I) ke dalam lambda calculus?
H(M,I) = ?M.?I.(TRUE FALSE)
.
mesin Z?
Z(x) = ?x.(?M.?I.(TRUE FALSE) halt)?
.
——————————————————————————————
Pertanyaan2:
Bagaimana lambda calculus menerjemahkan (enkoding) logika dana aritmetika?
Bagaiamna lambda calculus menerjemahkan mesin turing atau automata?
——————————————————————————————
#Apakah fungsi?
Wawasan pemahaman tentang fungsi adalah sebagai berikut:
fungsi sebagai ekspresi aljabar
fungsi sebagai ekspresi analitik
fungsi sebagai ekspresi jejala logika
fungsi sebagai tabel
fungsi sebagai jejala graph
fungsi sebagai jejala rules
fungsi sebagai sequence sentence dari suatu bahasa
.
#Kapan dua buah program dikatakan sama?
konsep sama atau tidak ini didasarkan pada definisi kesamaan 2 buah fungsi, dengan menganggap bahwa sebuah program adalah sebuah fungsi.
jadi:
2 buah program sama jika hanya jika untuk setiap input yang sama menghasilkan output yang sama.
.
——————————————————————————————
Bagaimana orang membuktikan halting problem menggunakan python atau pascal?
——————————————————————————————Tentang equivalence program:
Apakah ada sebuah program H yang dapat menentukan bahwa H dapat menentukan untuk setiap P dan Q program, H dapat menentukan bahwa P dan Q sama atau tidak.
.
H(P,Q) menghasilkan (yes,no)
.
(?).By:www.cs.bris.ac.uk/history/teaching/algorithms/chapter5.html

To test whether program P halts on input I
——————————————
construct a new program Q like P but
always returning true instead of true-or-false
construct a trivial program T which always returns true
find out whether Q and T are equivalent (on input I)
if so Q halts, otherwise it doesn’t
.
untuk menguji apakah P halt di input I.
buat sebuah program Q serupa P
dan Q selalu mereturn TRUE dari pada TRUE atau FALSE.
dalam hal ini Return(Q)=TRUE.
.
singkatnya:
buat Q=P dimana Return(Q)=TRUE.
.
buat program T sebarang sederhana yang selalu mereturn TRUE juga.
yaitu:
T sedemikan Return(T)=TRUE.
.
apakah Q=T untuk input I yang sama?
.
T halt jika Q halt dan tidak halt jika Q tidak.
.
——————————
Pembuktian yang baik: https://www.cs.rochester.edu/~nelson/courses/csc_173/computability/undecidable.html
——————————————————————————————
#Bagaimana orang membuktikan total problem?
Total problem = terdapat sebuah program H yang dapat menentukan bahwa sebarang program P dengan input di domain P adalah total.
.
Total = sebuah program P adalah total pada input D, jika untuk semua kemungkinan nilai D, P halt di D, atau P terdefinisi di domain P.
.
Teorema:
Tidak ada program H yang dapat selalu menentukan bahwa sebarang program P adalah total.
Bukti:
Misalkan ada H yang demikian, H(P) –> (yes,no)
buat suatu program trivial T
T(i):/*ignores input i*/; Return(T)=P(D);
.
gunakan T untuk membuktikan halting problem sebagai beriktu:
misalkan HALTS(P,D) adalah program yang dapat memberi keputusan (yes,no) adalah eksis (decideable).
HALTS(P,D) dapat dikonstruk sebagai berikut:
HALTS(P,D):
jika H(T) outputnya yes
maka return yes
else return no
.
disini tampak:
konstruksi T perlu karena kita ingin meringkas input (P,D) menjadi P saja, yaitu sebagai T saja, sehingga H yang hanya menerima 1 input bisa ditulis sebagai H(T) bukan H(P,D), input i untuk T mewakili sleuruh input untuk P dalam domain P atau tidak.
.
——————————————————————————————
#Bagaimana orang membuktikan equivalnce problem?
Teromea:
tidak ada program H yang dapat menentukan sebarang program P dan Q adalah ekivalen atau tidak.
Bukti:
Misalkan ada.
H(P,Q) –> (yes,no)
.
maka H dapat menentukan bahwa P dan Q adalah sama atau tidak jika P dan Q dikonstruksikan sebagai berikut (P,Q sebarang sehingga dapat dikonstruksikan semau kita).
P(x):G(x) return(P)=yes, untuk sebarang program G dengan input x dalam domain G.
.
buat Q dimana:
Q(x):return(Q)=yes.
.
konstrukskn H untuk menentukan P,Q ekivalen atau tidak sebagai berikut:
H(P,Q):
if P(x)=Q(x) return true
else return false.
.
misalkan return(H)=true maka P(x)=Q(x)
maka P(x) defined atau eksis.
.
tetapi P(x):G(x) return(P)=yes
adalah sebuah program yang menentukan G adalah total atau bukan.
.
ini berarti program yang bisa menentukan sebuah program G sebarang adalah total atau tidak adalah eksis, bertentangan dengan teorema sebelumnya (teorema tentang total problem) bahwa program total tidak mungkin eksis.
.
maka kontrasdiksi teorema total problem.
.
misal return(H)=false
maka tidak pasti bahwa P eksis atau tidak.
misalkan P eksis maka kontradiksi teorema total problem
misalkan P tidak eksis maka H tidak eksis secara trivial.
.
dari seluruh hasil kontradiksi maka program H tidak eksis atau undecideable.
.
——————————————————————————————
#Apakah computable?
Sebuah fungsi/program adalah computable jika hanya jika selalu halt (memberi jawaban) untuk seluruh inputnya.
.
Berdasarkan teorema total problem, maka tidak ada program/mesin turing yang dapat menentukan bahwa sebuah program/mesin sebarang adalah computable atau tidak.
.
Tidak ada program yang dapat menentukan bahwa sebuah program/mesin adalah computbale untuk input sebarang I, berdasarkan halting problem.
Karenanya jika ada program yang mencoba untuk menentukan itu, maka dia hanya partially computable.
Yaitu bahwa dia hanya bisa halt pada beberapa bagian tetapi tidak untuki seluruh bagian.
.
——————————————————————————————
#Bagaimana membuktikan bahwa mesin/program untuk halting problem adalah partially computable dan untuk mesin/program untuk equivalnece problem adalah tidak computable dan tidak partially computable?
Teorema:
misalkan HALTS(P,D) adalah program untuk halting problem.
konstruk HALTS(P,D):
HALTS(P,D):
P(D) halt then halt
else loop forever.
.
Tetapi himpunan input D dimana P(D) halt dapat dihitung berdasarkan P(D) sendiri sedang P dimana P tidak halt juga dapat dihitung berdasarkan eksistensi P(D) sendiri, yaitu:
COMPUTABLE-P={D | P(D) halt}
unCOMPUTABLE-P=tidak COMPUTABLE-P
dan karena eksitensi P(D) maka COMPUTABLE-P tidak kosong
dan karena teorema halting problem maka unCOMPUTABLE-P tidak kosong
.
ini menunjukkan bahwa HALT(P,D) dapat ditentukan sebagai partially computable.
.
qed.
.
———–
Teorem:
misalkan EQUALS(P,Q) dalam equivalence problem.
maka EQUALS(P,Q) adalah tidak partially computble (ini juga berarti tidak computbale).
bukti:
misalkan EQUALS(P,Q) true.
maka kita harus memeriksa seluruh kombinasi input dimana P dan Q sama.
misalkan x adalah input yang harus diperiksa, akan tetapi kita dapat membuat x dalam infinite kombinasi.
dan tak ada rule yang tetap untuk memeriksa sebagian dari infinite itu adalah menyebabkan P dan Q sama.
sehingga dia tidak partially computable.
.
qed.
.
——————————————————————————————
OK, UNTUK HALTING PROBLEM BISA CUKUP SAMPE DISINI.
——————————————————————————————
APAKAH TEOREMA REKURSIF?
#Apakah fixed point dalam computablity?
(eksplorasi dari https://en.wikipedia.org/wiki/Fixed_point_(mathematics))
Definisi:
c adalah sebuah fixed point bagi f(x) jika hanya jika f(c)=c
atau:
c adalah sebuah fixed point bagi f(x) jika hanya jika f dikomposisikan secara rekursif dengan dirinya sendiri maka dia tetap sama dengan dirinya sendiri pada titik c.
atau:
c adalah sebuah fixed point pada program P jika hanya jika P direkursifkan dengan dirinya sendiri maka return(P^n)=c
dimana P^n = P direkursifkan dengan dirinya sendiri sebanyak n kalu.
atau:
c adalah titik invarian (titik tidak berubah).
c invarian di P = jika c melewati P (sebagai argumen P) maka return(P)=c
.
——————————————————————————————
#Bagaimana orang memperluas konsep fixed point dalam matematika atau komputasi?
fixed poiint diperluas menjadi periodic point.
jika dibawa dalam komputasi:
c adalah periodic point bagi program P dengan periode k jika hanya jika return(P^k)=c
yaitu bahwa nilai c kembali dihasilkan secara periodik oleh P jika hanya jika P direkursifkan sebanyak k kali.
.
fixed point = periodik point dimana panjang periode k=1.
.
Orang membawa konsep ini juga ke geometri.
.
Dari sisi himpunan:
orang mengumpulkan seluruh fixed point dalam suatu himpunan atau field.
misal field of fixed point.
lebih luas lagi:
set of periodic point —> dimana k boleh sama atau k bervariasi.
.
kumpulan set titik fixed atau periodic ini membangun suatu geometri?
.
Dari sisi konsep barisan titik:
orang juga mengumpulkan semua titik yang membentuk barisan rekursif dari fungsi atau program:
barisan yang menarik ini adalah:
x,f(x),f(f(x)),f(f(f(x))),… dst
jika barisan titik-titik ini konvergen mendekati x maka himpunan/barisan titik ini disebut sebagai attractive fixed point.
.
konsep ini bisa juga diperluas ke dalam konsep attractive periodic point.
yaitu:
x,f^k(x),f^k(f^k(x)),f^k(f^k(f^k(x))),… dst.
.
tentunya menarik mempelajari implikasinya dalam komputasi atau geometri.
.
Himpunan x yang membentuk barisan attractive tentunya menjadi ciri khas suatu fungsi atau program. apakah sebuah program memiliki cuma 1 atau 2 atau 3 dst yang membangun barisan attractive?
Tentunya ini mungkihn dapat digunakan untuk menyelidiki kompleksitas suatu program atau algoritma.
.
Tentunya juga ini mungkin dapat digunakan untuk menyelidiki sifat-sifat geometri suatu polinom atau generalisasinya dsb.
.
——————————————————————————————
Pertanyaan2 hari ini:
Bagaimana kemunculan konsep attractor dan hubungannya dengan konsep rekursif dan kompleksitas?
Bagaimana melihat posisi konsep geometeri dari attractor secara analitik atau bukan?
(1).
Konsep attractor adalah bagian dari field sistem dinamis dalam matematika.
but how dynamical system constructed?
.
#Apakah sistem dinamis?
[1]Sistem dinamis dalam cara pandang konsep rekursif:
Kita dapat menggambarkan sebuah sistem dinamis sebagai sebuah gerak sebuah sistem titik ke titik, yaitu sebuah sistem (yaitu f(x)) yang berjalan langkah ke langkah.
langkah pertama adalah x
langkah kedua adalah f(f(x))
langkah ketiga adalah f(f(f(x)))
dan setersunya.
Akan tetapi bileh jadi x mewakili sebuah interval.
sehingga untuk setiap inisial langkah f di interval, grafika sistem dinamis menghasilkan geometri yang khas yang menggambarkan dinamika sistem untuk berbagai kemungkinan titik inisial langkah di interval yang diwakili x.
.
Secara sederhana kita melihat sistem dinamis ini sebagai sebuah sistem rekursif. yang bergerak secara rekursif untuk seluruh x di interval. seluruh titik x diingterval adalah titik inisial dari dinamika sistem.
.
[2]Sistem dinamis dalam cara pandang equation:
Sebagai sebuah equation, sistem dinamis dapat dilihat sebagai sebuah persamaan rekursif.
misal xi =a(xi-1)
dan setersunya.
Akan tetapi ekspresi ini dapat secara umum dinyatakan secara linier atau non linier dengan mengembalikan kebentuknya sebagai polinom.
misal f(x)=P(x) adalah sebuah polinom.
dengam membuat P(P(P(x)))dan setersunya kita membuat sebuah sistem dinamis non linier atau linier dari polinom.
Tetapi secara umum apakah dia polinom, eksponensial, logaritma, trigonometri dsb, kita menulis saja sebagai fungsi f(x1,x2,x3,…)
dan fungsi f dapat digunakan untuk mengkomstruksikan sebuah sistem dinamis dengan membuatnya rekursif untuk seluruh atau sebagian argumennya.
.
[3]Dalam cara pandang komputasi:
Sistem dinamis yang dikonstruksikan oleh f(x1,x2,x3,…) direpresentasikan oleh sebuah fungsi lambda f atau sebuah mesin turing M atau sebuah program P yang dibuat rekursif.
Sehingga secara komputasi, sebuah sistem rekursif juga dapat dibangun.
.
[4]Hubungannya dengan konsep fixed point:
#Apakah arti filosofis dari kehadiran fixed point dalam konteks sistem dinamis?
Konsep fixed point memberikan sebuah konsep yang lebih umum, yaitu bahwa untuk setiap sistem dinamis, disana terdapat sebuah himpunan titik tetap atau cenderung konvergen ke titik tetap, atau titik2 invarian atau cenderung konvergen ke titik2 invarian.
Himpunan titik2 ini melahirkan konsep attractor.
.
Dikatakan attractor secara filosofis artinya bahwa eksistensi titik2 itu menyebabkan sistem dinamis terlihat bervibrasi atau bergetar disekitar titik2 invarian.
menarik sistem di sejumlah titik di setiap waktu sehingga sistem bervibrasi disekitar titik2 itu.
.
Konsep attractor menyebabkan kita dapat meninjau sebarang sistem dinamis sebagai sebuah gelombang atau sebuah osilasi.
.
[5]Bagaiamana hubungan persamaan differensial dengan sistem dinamis?
Kita dapat merumuskan equation untuk sistem dinamis dalam ekspresi persamaan differensial.
misal xt=f(xt-1)
.
ini dapat dibuat sebagai:
xt=f'(xt-1)
dan seterusnya.
.
[6]Bagaimana hubungan persamaan fractal dengan sistem dinamis?
Kita dapat melihat perumusan fractal sebagai perumusan rekursif, sehingga dia adalah merupakan sistem dinamis.
.
#Bagaimana mengkonstruksikan fungsi/program/mesin rekursif secara umum?
#Bagaimana mengkonstruksikan sistem dinamis secara umum?
Kedua pertanyaan ini dapat kita samakan saja.
Konstruksi rekursif secara umum dan sederhana dapat ditulis:
misalkan kita memiliki fungsi f(x). f dapat berupa fungsi analitik, polinom, lambda, program atau mesin turin.
maka kita dapat menyatakan ini secara rekursif dengan menulisnya sebagai:
xt=f(xt-1)
.
secara formal rekursif:
x0=c
xt=f(xt-1)
.
secara sebagai sistem dinamis:
xt=f(xt-1)
dengan melihat bahwa x awal dapat suatu interval sebarang.
.
secara umum konstruksi rekursif atau sistem dinamis adalah:
(x1t,x2t,x3t,…)=f^n(x1t-1,x2t-1,x3t-1,…)
ini mencakup turunan f sehingga ditulis f^n, tetapi tidak harus menggunakan turunan.
.
#Bagaimana membuktikan sebuah fungsi rekursif/program/mesin turing menggunakan induksi?
misal:
xt=f(xt-1)
.
buktikan untuk t=0
yaitu:
x1=f(x0)
.
andaikan bahwa untuk t=n adalah benar:
xn=f(xn-1) adalah benar.
buktikan untuk t=n+1:
xn+1=f(xn)
.
#Bagaimana memperluas konsep rekursif dan sitem dinamis?
untuk rekursif, bentuk:
x0=c
xt=f(xt-1)
diperluas menjadi:
x1.0=c1
x2.0=c2
…
xk.0=ck
x1.t=f1(x1.t-1)
x2.t=f2(x2.t-1)
…
xm.t=fm(x1.t-1)
.
untuk sistem dinamis, bentuk:
xt=f(xt-1)
diperluas smenjadi:
xi.t=fi(xi.t-1) untuk xi di interval ke-i.
.
Secara keseluruhan untuk rekursif dan sistem dinamis, diperluas ke dalam
(x1t,x2t,x3t,…)=f^n(x1t-1,x2t-1,x3t-1,…)
dalam cara yang sama di atas.
.
#Bagaimana orang memperluas konsep pembuktian dengan induksi?
cara pembuktin induksi selama ini, juga seperti diatas sebelumnya, dapat dilihat sebagai induksi di garis linier.
.
bagaimana jika untuk membuktikan fungsi rekursif yang telah diperluas seperti diatas, dimana geraknya tidak linier dalam satu garis lurus tetapi bercabang-cabang membentuk pohon, atau secara umum sebuah graph.
.
ini berarti konsep induksi diperluas untuk pohon atau graph.
ini kita sebut sebagai pohon induksi atau graph induksi.
.
Cara pembuktian dengan pohon induksi mungkin sebagai berikut:
buktikan untuk root, atau titik-titik inisial jika bukan pohon, lalu buktikan untuk seluruh path yang mungkin dalam graph.
.
#Bagaimana pentingnya konsep attractor dalam gagasan chaos?
#Bagaimana mengkonstruksikan struktur chaos?
gagasan attractor memberi pencerahan bahwa pada setiap chaos mungkin disana ada hukum yang ditaati oleh titik2 chaos atau ada titik attractor yang dicendrungi oleh setiap titik2 chaos, atau mungkin kita dapat melihat sifat periodik dalam chaos.
.
——————————————————————————————
but how construct chaos?
chaotic adalah lawan dari kata periodic?
——————————————————————————————
Tetapi apa arti periodic point bagi komputasi?
——————————————————————————————
Apa beda typed lambda dan untyped lambda?
——————————————————————————————
Review:https://en.wikipedia.org/wiki/Attraktor
(1).
A dynamical system is generally described by one or more differential or difference equations. The equations of a given dynamical system specify its behavior over any given short period of time. To determine the system’s behavior for a longer period, it is often necessary to integrate the equations, either through analytical means or through iteration, often with the aid of computers.
.
Sistem dinamis digambarkan secara umum sebagai satu atau lebih persamaan differensial atau difference.
Persamaan bagi sebuah sistem dinamis menentukan perilaku sistem sepanjang waktu.
Untuk melihat perilaku sistem dalam periode waktu yang lebih panjang biasnaya orang menyatukan/menitegrasikan persamaan2 itu.
.
#Apa arti mengintegrasikan persamaan2 sistem dinamis?
Mengintergasikan persamaan2 bisa berarti menytukan dalam runtun iterasi.
misal untuk persamaan1 kemudin diikuti persamaan2 yang mengambil output persamaan1 sebagai input dan setersunya membentuk suatu rantai persamaan yang bersambungan input-output.
.
atau secara umum membentuk saling bersambungan input-ouput antar persamaan dan membangun suatu pohon atau lebih umum lagi sebuah graph dinamis dalam waktu.
.
atau persamaan2 itu secara analitik membangun/membentuk persamaan baru yang cukup persamaan baru itu saja digunakan menggambarkan sistem dinamis.
.
#Apakah dasar fenomena dari sistem dinamis?
Secara umum, gagasan sistem dinamis berbasis pada fenomena disipasi.
fenomena disipasi oleh kehilangan energi termonimaka
fenomena disipasi oleh gesekan
fenomena disipasi oleh kehilangan materi
fenomena disipasi oleh kehilangan energi secara umum.
.
#Apakah ruang fase (phase space) bagi sistem dinamis?
Secara umum:
Sistem dinamis dapat direpresentasikan secara analitik dalam kordinat cartesian berdimens n. tetapi ini disebut juga sebagai ruang fase.
ruang fase = himpunan titik dimana setiap titik menyatakan kordinat yang dibangun dari variabel-variabel yang menyusun sistem dinamis.
.
#Dimana letak actractorr dalam ruang fase sistem dinamias?
attracotr juga adalah himpunan titik tetapi dengan sifat-sifat seperti dijelaskan sebelumnya, bersifat khas, karena dia juga himpunan titik maka dia juga menggambarkan fase dari sistem dinamis, dia adalah suatu subset ruang dalam rung fase.
.
#Tentang konsep titik penting dalam sistem dinamis:
Sebenarnya terdapat 3 konsep titik penting:
titik invarian, titik limit dan attractor.
titik invarian = fixed point
titik limit = titik dimana titik2 lain cenderung konvergen ke titik itu dalam satu atau beberapa sebarang arah sumbu cartesian.
attractor = titik2 limit tetapi hanya titik limit yang mana titik2 lain cenderung konvergen kepadanya dalam arah sumbu waktu, boleh dalam arah sumbu lain tetapi arah sumbu waktu harus ada. (tidak semua titik limit).
.
#Apa perbedaan konsep rekursif dan konsep sistem dinamis?
Konsep rekursif menggunakan indeks rekursif dalam sebarang artian variabel.
misal: xn=f(xn-1)
Sistem dinamis menggunakan indeks rekursif dalam arah waktu.
misal: xt=f(xt-1)
.
——————————————————————————————
#Bagaimana orang merumuskan sistem dinamis secara analitik, terlepas dari atau dalam ekspresi yang lebih umum selain rekursif?
#Bagaimana orang merumuskan konsep attractor secara analitik di atas sistem dinamis yang analitik?
Sebagaimana dari wikipedia, perumusan analitik attractor adaah sebagai berikut:
An attractor is a subset A of the phase space characterized by the following three conditions:
[1]A is forward invariant under f: if a is an element of A then so is f(t,a), for all t > 0.
[2]There exists a neighborhood of A, called the basin of attraction for A and denoted B(A), which consists of all points b that “enter A in the limit t ? 8”. More formally, B(A) is the set of all points b in the phase space with the following property:
For any open neighborhood N of A, there is a positive constant T such that f(t,b) ? N for all real t > T.
[3]There is no proper (non-empty) subset of A having the first two properties.

——————————————————————————————
#Apakah konstruksi geometri dasar sebuah set dari fixed point atau attarctor secara umum?
Sederhana saja, secara intuitif untuk f(x).
Konstruksi geometri himpunan titik fixed point dari f adalah garis f(x)=x.
.
Konstruksi ini dapat diperluas di bidang atau ruang berdimensi n.
.
Secara umum, sebuah attractor dapat memiliki bentuk sebagai sebarang bentuk polyhedron, surface, manifold, atau topological space dsb. Manakala kumpulan attractor tersebut tidak dapat didekomposisikan secara sederhana dalam operasi aljabar himpunan titik2 (unian dan intersect) maka dia adalah sebuah strange attractor.
.
——————————————————————————————
#Apakah trayektori dalam konsep attractor?
Yaitu himpunan attractor yang membangun suatu path garis dalam waktu pada ruang fase (phase space).
.
path garis ini boleh suatu hyperline atau hypercurve dalam ruang berdimensi n atau dalam sebarang manifold.
.
#Apakah limit cycle dalam konsep attractor?
Adalah sebuah trayektori yang membangun hypercurve tertutup, membangun suatu trayektori yang periodik.
Atau membangun suatu trayektori yang berosilasi atau membentuk representasi gelombang.
.
#Apakah limit torus?
Manakalah trayektori membangun suatu hypercurve yang tertutup, maka mestilah nilai-nilai parameter yang membangunnya dalam ruang fase memiliki nilai perbandinngan yang tetap atau rasional antar mereka.
.
Akan tetapi bagaimana jika perbandingan antar parameter itu menjadi irrasional, itu berarti nilai perbandingan menjadi tidak dapat dihitung secara tetap, karena sifat bilangan irrasional yang terus tumbuh dalam hitungan (sebagaimana nilai pi). ini berakibat trayektori yang tertutup dalam bentuk hypercurve dalam sebuah hyperplane menjadi tidak tertutup.
.
tetapi walau demikian, dia hanya tidak tertutup dalam hyperplane, kita dapat membayangkan dia membangun trayektori yang keluar dalam arah tegak lurus hyperplane, yaitu membangun suatu trayektori yang periodik dalam arah hyperspace. trayektori periodik dalam arah hyperspace ini membangun suatu torus atau hypertorus dalam hyperspace.
.
bentuk hypertorus ini tidak selalu sempurna seperti donat, tetapi seluruh bentuk manifold yang secara topologi adalah sama dengan sebuah torus atau hypertorus.
.
#Mengapa pada limit torus dikatakan quasiperiodik?
Karena dia tidak periodik dalam hyperplane, tetapi sekan-akan periodik dalam sebuah hypertorus, walaupun dia tidak periodek beneran dalam hypertorus, tetapi trayektori tidak keluar dari hypertorus, sehingga dia seakan-akan periodik.
——————————————————————————————
END: Konsep attractor sampai disini.
——————————————————————————————
——————————————————————————————
——————————————————————————————
#Bagaimana orang merumuskan konsep sistem dinamis secara lebih umum dan analitik (lepas dari konsep rekursif)?
(1).
#Rumusan analitik:
Perumusan yang sederhana dari sistem dinamis adlah bahwa:
semua sistem yang dapat direpresentasikan sebagai himpunan state dimana tiap-tiap state adalah bergantung waktu.
state dari sistem dinyatakan oleh variabel-variabel yang membangun sistem atau merepresentasikan sistem sebagai sebuah himpunan data.
sistem sebagai himpunan data dari waktu ke waktu, seluruh variabel dan waktu menjadi atribut-atribut dari rekord yang membangun representasi data dari sistem.
.
himpunan state dapat direpresentasikan ke dalam ruang geometri.
.
secara sederhana dan umum, sebuah sistem dinamis dapat ditulis sebagai:
f(t.i,state-i)=(t.i+1,state-i+1)
.
dalam perumusan yang mencakupt turunan:
f^n(t.i,state-i)=(t.i+1,state-i+1)
f^n menyatakan turunan ke-n dan setersunya.
.
atau lebih umum lagi dalam perumusan yang lebih kompleks.
.
dalam perumusan lebih umum, bukan hanya sebuah fungsi tetapi mungkin k buah fungsi yang membangun tensor rank-k fungsi2 atau set fungsi.
.
(2).
#Rumusan evolusi sistem:
evolusi dari sistem = barisam rekrusif dari tiap-tiap nilai inisial dimana di memulai.
akan tetapi konsep evolusi dari sistem dapat dirumuskan secara lebih luas sebagaimana kita merumuskan konsep fungsi rekursif dalam artian yang luas.
.
secara lebih luas lagi:
evolusi berarti statae dari waktu ke waktu, semata berdasar waktu.
state di t lalu state di t-1.
tidak harus dalam pengertian rekursif.
.
Secara umum:
evolusi sistem menyatakan fungsi, program, model komputasi dari sistem dari waktu ke waktu.
.
f(t.i,state-i)=(t.i+1,state-i+1)
dinayatkan sebagai rumus evolusi dari sistem.
.
(3).
#Perluasn sistem dinamis ke stokastik:
Evolusi sebuah sistem dapat diperluas dari deterministik ke stokastik.
secatra lebih luas, waktu ke waktu dari state sistem dapat diperluas ke dinamika yang stokastik. Ada lebih dari 1 pilihan state di masa depan.
.
(4).
#Apa hubungannya dengan ruang fase?
state = fase
sehingga ruang fase = ruang state.
.
(5).
#Perluasan konsep trayektori:
trayektori = himpunan path di hyperline, hyperplane, hypersurface, hyperspace (trayektori membangun sebarang bentuk manifold berdimensi n)
.
misal himpunan trayektori medan vektor di bidang.
——————————————————————————————
Konsep sistem dinamis sementara sampai disini.
——————————————————————————————
#Apakah chaos?
Chaos = sistem dinamis, tetapi dengan inisial point yang sangat sensitif.
sangat sensitif = bila sebuah titik y konvergen ke titik inisial x, maka titik selanjutnya dari y akan sangat divergen terhdapa titik selanjutnya dari titik x.
.
Ini menunjukkan sifat yang tidak periodik atau tidak mendekati periodik.
——————————————————————————————
Selesai untuk konsep chaos.
——————————————————————————————
#Apakah recursion theorem?
Recursion theorem:
Untuk setiap algoritma yang menerima input string I, disana terdapat algoritma yang rekursif yang identik.
.
Pembuktian ini sepertinya berasala dari teorema rekursif dari fungsi analitik.
——————————————————————————————
#Secara umum apakah definisi umum dan formal dari definisi rekursif?
definisi rekursif (untuk fungsi rekursif, program, mesin dan sebagainya) memiliki bentuk dasar:
ada base case
ada inductive case.
.
Pembuktian:
buktikan untuk base case
buktikan untuk inductive case menggunakan konsep induksi.
.
#Bagaimana membuktikan teorema rekursif secara langsung?
Teorema:
Untuk suatu fungsi f:X–>X sebarang dan a elemen X, terdapat sebuah F:N–>X sehingga f bersifat rekursif yaitu dimana:
F(0)=a
F(n+1)=f(F(n))
.
Bukti:
misalkan X<>himpunan kosong:
ambil a elemen X
sehingga b=f(a).
buat pemetaan: F(0)=a, F(1)=b
dengan demikian terbukti bahwa kita dapat membuat F(0)
yaitu F(0)=a.
.
misalkan bahwa disana ada c elemen X, tetapi f:X–>X
sehingga kita dapat membuat d=f(c)
maka dapat dibuat pemetaan F(n-1)=c, F(n)=d
sehinga diperoleh F(n)=f(F(n-1)).
.
karena f:X–>X maka dapat dibuat f(d), tetapi f:X–>X berdasarkan definisi fungsi maka mestilah disana ada suatu
k=f(d) di X, tetapi F:N–>X
sehingga kita dapat membuat pemetaan F(n+1)=k.
maka diperoleh F(n+1)=f(F(n)) eksis.
.
eksistensi fungsi rekursif terbukti untuk X tidak sama dengan himpunan kosong.
.
misalkan X himpunan kosong:
maka setiap x<>x untuk setiap elemen X.
kita dapat membuat ekspresi F(0)<>F(0) sehinga F(0) elemen X
dan kita dapat membuat ekspresi f(F(n))<>f(F(n)) dan F(n+1)<>F(n+1) tetapi sekaligus
bahwa F(n+1)=f(F(n)) tetap benar.
.
untuk pembuktian keunikan, tinggal lihat di wikipedia.
qed.
.
(pembuktian ini masih kurang jelas untuk X himpunan kosong)
.
——————————————————————————————
Review: Lecture 31. Halting problem, CSCI 81 Spring, 2013, Kim Bruce.
(1).
Sebuah himpunan X adalah decideable jika hanya jika X<>himpunan kosong.
.
Misal pernyataan kim:
HTM = {?M,w? | M is a TM which halts on input w} = himpunan kosong karena tak ada mesin yang memenuhi sifat ini (undecideable).
.
(2).
#Bagaimana menyatakan masalah undecideable ke dalam masalah himpunan?
misal masalah P, suatu X memenuhi P adalah undecideable. ditulis dalam permasalahan himpunan:
MASALAH-P={<X>| X memenuhi P(X)}.
.
MASALAH-P adalah undecideable jika hanya jika MASALAH-P himpunan kosong.
.
untuk membuktikan bahwa MASALAH-P decideable, cukup dibuktikan bahwa MASALAH-P adalah tidak kosong.
.
(3).
#Bagaimana mereka biasa memecahkan masalah mesin oleh mesin?
mereka menulis mesin ke dalam string enkoding. simbol mesin yang sudah dienkoding adalah ditulis:
misal M adalah mesin, maka enkoding M adalah <M>
——————————————————————————————
Apakah semidecidable?
Bagaimana orang menggunakan UTM untuk membuktikan semidecideable?
——————————————————————————————

TINJAU SEKILAS KERJA MIRZA

Kerja Mirzakhani:
(1).
#Apakah dasar imajinasi Mirza untuk hampir seluruh kerjanya dalam geometri?
Bismillah:
Pertama:
Mungkin jika diperumum, seluruh kerja Mirza adalah tentang membenamkan dinamika (mekanika) ke dalam geometri non-euclid.
.
Ini seperti setara tentang galileo atau newton yang membenamkan dinamika ke dalam geometri euclid, kemudian diperluas ke ruang vektor (ruang euclid berdimensi tinggi).
.
Kedua:
Dasar imajinasi Mirza bagi mungkin keseluruhan kerjanya adalah:
Dinamika bola bilyard di atas meja datar/datar euclid, kemudian dia memperluas kepada dinamika bola bilyar di atas sebarang meja/non euclid atau euclid (meja secara universal).
.
(2).
Polinomial (univariat atau multivariat) bukan saja digunakan orang untuk membangun shape2 geometri di ruang euclid, tetapi juga menggunakannya untuk membangun ruang2 non-euclid.
.
Secara umum, sebuah kelas ruang non-euclid adalah ruang yang dibangun oleh sebuah polinomial atau sebuah set persamaan/pertidaksamaan polinomial.
.
Cara orang membangun shape geometri dalam ruang eculid:
Shape P(x1,x2,x3,…,xn) = {(x1,x2,x3,…,xn)| dimana (x1,x2,x3,…,xn) memenuhi P(x1,x2,x3,…,xn)}
atau:
Shape P = {(x1,x2,x3,…,xn)| dimana (x1,x2,x3,…,xn) memenuhi set P(x1,x2,x3,…,xn)}
.
demikian pula bahwa Shape dapat dilihat sebagai sebuah ruang non-eculid.
dan kita dapat menyebut P(x1,x2,x3,…,xn) sebagai hyperpolynomial.
.
(3).
#APAKAH MANIFOLD?
Manifold = secara intuitif adalah hyperpolygon yang mendekati sebuah hypersurface.
.
Mungkin bisa dinyatakan sebagai:
Bahwa setiap hyperplane yang menyusun atau membangun hyperpolygon adalah sebuah ruang euclid.
.
Atau:
Terdapat sebuah homeomprhisme antara antara hyperplane tersebut dengan hyperspace euclid.
.
Atau:
Manifold :
fold = hyperplane
Many = banyak
Manifold = himpunan hyperplane.
.
Atau :
Manifold:
fold = chart = kartu yang memuat atlas atau bagian atlas dari hypersurface.
Many = banyak.
Manifold = himpunan chart.
.
Atau :
Manifold = Atlas = himpunan chart yang disambung-sambung.
.
#APAKAH DIMENSI MANIFOLD?
Dimensi ruang sebuah manifold = dimensi ruang fold nya atau dimensi ruang chartnya atau dimensi ruang dari hyperspace euclid yang homeomorphic dengan chart manifold.
.
#BAGAIMANA MANIFOLD MENDEKATI SEBUAH HYPERSURFACE YANG MULUS?
Adalh dengan memperkecil fold/chart menjadi sebuah hyperball sedemikain ruap dimana jari-jarinya limit mendekati nol, akan tetapi hyperball itu masih tetap homeomorphic dengan sebuah hyperspace euclid.
.
Seakan-akan memperkecil chart menjadi sebuah titik/dot yang sangat kecil (infinitisimal) sehingga manifold seakan dibangun oleh titik2 kontinu.
.
#APAKAH ABSTRACT SURFACE ATAU ABSTRACT SPACE?
Yaitu setiap surface/hypersurface atau space/hyperspace yang dapat dirumuskan atau dimodelkan menjadi manifold.
.
So, manifold adalah sebuah abstrak.
.
Akan tetapi sepertinya juga orang merumuskannya sebagai surface/hypersurface yang tidak bisa diembed/dibenamkan ke dalam ruang euclid, tanpa mengalami self-intersection.
.
self-intersection = jika terdapat ruang berdimensi n-1 memotong/beririsan dengan ruang berdimensi n-1 lain dalam ruang berdimensi n.
.
Sebuah ruang dapat di embed ke dalam ruang yang lain, jika terdapat homeomorphisme anatar kedua ruang tersebut.
.
#MENGAPA JIKA TERJADI SELF-INTERSECTION MAKA TIDAK DAPAT DIEMBED?
Ruang X dapat di embed ke ruang Y jika terdapat homeomorphhisme antara X dan Y.
Akan tetapi jika terjadi self-intersection dalam Y, maka terdapat titik pada Y yang memiliki dua titik asal yang berbeda pada X, yaitu dimana dua subruang tidak beririsan di X tetapi peta kedua subruang itu beririsan di Y.
Maka X tidak dapat diembed di Y.
.
Akan tetapi jika menilik pada fold dari manifold maka setiap fold dapat membangun homeomorhisme dengan ruang euclid sebab fold itu sendiri diassumsikan/dipostulatkan datar.
.
#PERTANYAAN2:
Bagaimana aljabar geometri mengkonstruksikan surface/hypersurface?
Bagaimana topologi mengkonstruksikan surface/hypersurface?
Bagaimana geometri differensial mengkonstruksikan surface/hypersurface?
Apa arti bahwa dua space are connected? definisinya apa?
.
#BAGAIMANA TOPOLOGI DI KONSTRUKSIKAN?
Topologi adalah sebuah geometri dengan dasar konstruksi geometri adalah sebagai berikut:
Segala ruang dan shape adalah sebuah koleksi himpunan buka.
.
Ini analogi dengan manifold, bahwa setiap shape adalah sebuah hyperpolygon, suatu kumpulan datar yang membangun bentuk, akan tetapi topologi menggunakan open set, bisa juga open set dilihat sebagai hyperball buka, akan tetapi secara universal dia boleh bentuk sebarang asal dia open.
.
Diatas koleksi open set ini, dikonstruksikan struktur topologi.
.
dengan menerjemahkan open set sebagai node, maka diperoleh topologi dalam bentuk graf, koneksi antar open set terganti menjadi koneksi antar node.
Akan tetapi bagaimana melihat open set sebagai node? apa definisi open dalam graf?
Apakah mungkin?
.
#APAKAH DEGREE OF FREEDOMS?
Yaitu jumlah arah (variabel) dimana hanya dengan kombinasi arah2 itu, seluruh gerak titik dapat direpresentasikan, tak ada gerak yang tidak dapat diurai ke dalam komposisi nilai2 variabel degree of freedom tersebut.
.
Akan tetapi ini diperluas oleh lagrange, dengan mengganti gerak titik ke titik menjadi gerak state ke state.
.
sehingga himpunan var2 yang menyatakan degree of freedom tidak melulu berarti variabel2 sumbu sistem kordinat.
.
keseluruah degrree of freedom itu dapat mengambil sebarang bentuk sistem kordinat, bisa, cartesian, bola, tabung dan lain sebagainya, yang penting bahwa segala gerak dapat dinyatakan ke dalam komposisi var2 degree of freedom.
.
#BAGAIMANA PEMETAAN BIJECTIVE DIBANGUN ANTARA RUANG?
Dasar imajinasi untuk ini adalah:
Pemetaan bola rienmann kepada bidang kompleks, dimana untuk setiap titik pada bola ditarik garis lurus yang jatuh tepat memetakan satu titik di bola dengan tepat satu titik di bidang kompleks, kecuali pada titik kutub atas, yang terpetakan ke tak hingga titik di bidang.
.
Ini diterapkan ke imaji ruang eculid. pemetaan suatu surface atau space ke bidang euclid adalah mengikuti cara tersebut, jika berhasil maka surface atau space itu adalah homeomorphic ke bidang atau ruang euclid.
.
#MENGAPA BOTOL KLEIN ATAU SURFACE TERTENTU TIDAK DAPAT HOMEOMORPHIC DENGAN BIDANG EUCLID?
Dengan menggunakan cara pemetaan rienmann di atas:
mengapa suatu surface atau botol klein tidak dapat homeomorphic ke bidang atau ruang euclid? ini karena jika kita menarik garis sinar atau garis lurus dari satu titik di botol klein atau surface, maka pastilah dia akan memotong bagian yang lain dari botol klein atau surface sehingga terdapat lebih dari satu titik (2,3,4, dst titik) yang terpetakan ke satu titik di bidang euclid atau ruang euclid.
.
#DIMANAKAH POSISI METRIC SPACE TERHADAP EUCLID SPACE, TOPOLOGI SPACE?
METRIC SPACE = generalisasi dari euclid space, sehingga secara otomatis, non eculid space juga adalah tercakup dalam metric space, bahkan diskrit space, kontinu space dsb.
.
Secara umum, jika kita dapat merumuskan suatu space sebagai suatu metric space maka dia mengandung unsur universality yang berada di atas euclid, non euclid, diskrit atau non diskrit space.
.
TOPOLOGICAL SPACE = merupakan generalisasi dari metric space.
.
Universalitas geometri dari topologi adalah berada di atas euclid, non euclid, diskrit, kontinu, metric space.
.
#BEDA VEKTOR SPACE DAN METRIC SPACE?
Metric space = ada dalam cara pandang ruang geometri
Vector space = ada dalam cara pandang ruang aljabar.
.
akan tetapi orang menggunakan vektor space untuk merepresentasikan berbagai ruang geometri. Ini berarti orang menggunakan:
ruang vektor untuk merepresentasikan ruang euclid, ruang non euclid, metric space, topologi.
.
#DIMANA POSISI RUANG HASIL KALI DALAM?
ruang hasil kali dalam = ada dalam cara pandang ruang aljabar.
ruang hasil kali dalam adalah generalisasi atau analogi ruang metric di dalam cara pandang aljabar.
.
#BAGAIMANA KONSEP OPEN SET DI GENERALISIR DI TOPOLOGI?
Bismillah:
Pertama:
Pada mulanya, open set pada ruang euclid atau lebih umumnya lagi yaitu pada ruang metrik, sebuah open set adalah sebuah himpunan titik dimana untuk setiap titik di dalamnya selalu dapat dibuat bola dimana bola itu seluruhnya termuat dalam ruang metrik.
.
bola itu sendiri tidak dapat dikatakan buka atau tutup, atau apa saja, yang penting dia adalah bola yang selalu dapat dibuat dan termuat dalam himpunan titik yang dimaksud.
.
Kedua:
Generalisasi open set tidak lagi berdasar konsep titik2 kontinu atau diskrit, atau mulus dan sebagainya, akan tetapi yang dimaksud open set dalam topologi adalah sebarang set yang memenuhi aksioma2 topologi.
.
Atau:
X open set jika X adalah topologi.
dan X terdiri dari open set juga yang tertutup terhadap operasi gabung
dan tertutup terhadap operasi irisan yang berhingga.
.
Karena itu dapat dipahami mengapa sebuah node dalam graf dapat dilihat sebagai open set, sebuah graf dapat dilihat sebagai topologi, dan sebagainya, karena tak ada lagi pandangan kontinuitas bagi open set, gak masalah mau diskrit, mau kontinu, yang penting memenuhi aksioma topologi.
.
#BAGAIMANA CLOSED SET DIDEFINISIKAN DALAM TOPOLOGI?
Closed set, tanpa pengertian kontinuitas juga dapat langsung di definisikan hanya sebagai complement open set.
.
Demikian pula clopen set, dikonstruksikan cukup dengan premis2 dari aksioma topologi.
.
#BAGAIAMAN HIMPUNAN2 DIKONSTRUKSIKAN DALAM TOPOLOGI?
Yaitu cukup dengan menggunakan operasi gabung atau irisan terhadap open set.
contoh dasar:
konstruksi open set sebagai gabungan open set atau irisan open set.
konstruksi closed set sebagai complement open set.
konstruksi clopen set.
.
X adalah clopen set jika hanya jika X dan complement X adalah sama2 topologi.
.
#APA ARTI HAKIKI TOPOLOGI?
Bismillah:
Pertama:
Topologi adalah term yang mengeneralisasi term open set.
Bukan sebuah nama ruang, atau term yang setara dengan nama ruang.
Dia hanya sekedar sebuah himpunan yang mengeneralisir open set dalam ruang metrik.
.
Jadi:
Bola buka adalah sebuah topologi.
Interval buka adalah sebuah topologi.
.
Jika kita melihat bola buka adalah sebuah topologi maka :
bola buka sendiri adalah sebuah topologi, himpunan kosong dalam bola buka juga adalah topologi.
subset2 buka dalam bola buka jika digabung maka juga menghasilkan subset buka dalam bola buka.
subset2 buka jika diriskan secara berhingga maka juga menghasilkan subset buka dalam bola buka.
.
dengan demikian terlihat generalisir term topologi terhadap term open set.
.
dengan demikian memenuhi juga bahwa sbuah node adalah sebuah topologi.
.
Jadi:
Term Topologi adalah term yang setara open set, tetapi generalisirnya.
.
#APAKAH TOPOLOGICAL SPACE?
yaitu ruang dimana seluruh open set di dalamnya adalah topologi.
Atau:
Ruang dimana di dalamnya dapat di definiskan topologi.
.
Atau:
Ruang yang dibangun oleh himpunan topologi akan tetapi mungkin boleh juga bahwa ruang ini di dalamnya terdapat bukan topologi.
.
HOW?
.
#APA HUBUNGAN ISTILAH ANTARA TOPOLOGY DAN TOPOLOGICAL SPACE?
Hubugan kedua istilah ini adalah bersifat rekursif. Taitu sebagai berikut:
.
Topological space = dibangun oleh sebuah himpunan topology.
tetapi Topology = Sebuah topological space.
.
#MENGAPA MANIFORLD ADALAH SEBUAH TOPOLOGY?
Karena setiap fold atau chart adalah sebuah topology atau open set, kemudian himpunan topology ini membangun topological structur yang bernama manifold.
.
Sehingga manifold bisa diartikan sebagai manitopologi.
.
Tetapi dengan sifat dasar bahwa, tiap2 topology komponen (fold) adalah homeomorphic terhadap ruang euclid berdimensi n.
.
#BAGAIMANA IDE KUNCI ATAU DASAR PENERAPAN TOPOLOGY ATAU CARA PANDANG TOPOLOGY BAGI GEOMETRI?
Bismillah:
Pertama:
Topology bisa dilihat sebagai terletak di puncak geometri, atau merangkum seluruh geometri.
.
Kedua:
Kunci atau ide dasar bagaimana topology merumuskan geometri adalah:
Sebarang shape, sebarang ruang, sebarang himpunan titik dalam geometri sebarang adalah sebuah topology. Yaitu topolgy yang diterjemahkan sebagai manifold.
.
Atau:
Sebarang shape adalah manifold.
Sebarang space adalah manifold.
Sebarang himpunan titik adalah manifold.
.
Sehingga:
Geometri = ilmu tentang sifat2 manifold.
.
#APA ARTI Stone’s representation theorem for Boolean algebras?
Yaitu bahwa pada dasarnya setiap aljabar boole adalah sebuah topologi.
.
#IDE 1:
TErdapat kemungkinan bahwa komputasi dapat dilihat saja sebagai sebuah teori tentang topology.
.
Bagaimana melihat mesin turing secara topology?
.
Jika kita dapat menunjukkan bahwa sebuah sistem yang disusun berdasarkan aljabar boole, dalam hal ini dia adalah sebuah aljabar boole maka sistem itu mestilah sebuah topologi.
Akan tetapi jika sistem itu turing complete maka dia adalah sebuah UTM sekaligus juga dia dalah sebuah topologi.
#END IDE 1.
.
#IDE 2:
Generalisasi manifold, dimana untuk setiap foldnya adalah sebarang topologi, sebarang orientasi, dan sebarang homeomorphic pada suatu yang lebih umum atau beda dari ruang euclid, bisa ruang non euclid, lebih umum ruang metrik, atau lebih umum lagi suatu topologi, atau malah homeomorphic pada suatu manifold yang lain untuk setiap foldnya.
#END IDE 2.
.
#IDE 3:
Representasi sebuah partikel elementer sebagai sebuah manifold atau topologi.
#END IDE 3.
#IDE 4:
Perumusan ruang kuantum dengan menambahkan sebuah postulat pada set postulat topologi.
Dan tentang bagaimana merumuskan dinamika sebuah partikel di dalam ruang kuantum.
#END IDE 4.

CATATAN KERJA AGUSTUS 2017

Apa yang hendak dikerja hari ini?
InShaa Allah:
(1).
#IDE 1:
Cari tau semua ide clustering yang pernah ada, kalau ada yg sama dengan ide kamu tentang unseprvised clustering yang mirip k-mean maka berhenti. jika tidak maka lanjutkan, rencanakan publikasi di telkomnika atau ijece.
.
ide ini generalisir fungsi keanggotaan suatu titik bukan hanya berdasar jarak tetapi bisa juga nilai grayscale dan sebagainya fungsi.
.
perluas jika fungsinya berupa vektor fungsi, analogi vektor RGBA.
.
perluas gagasan jika dia dibawa ke dalam konsep fuzzy.
.
perluas gagasan ini untuk konstruksi rule, dengan mendefinisikan fungsi keanggotaan adalah conditional probability suatu titik terhadap titik yang lain.
dalam gagasan ini, rule=cluster sehingga konstruksi konstruksi cluster secara unsupervised berarti konstruksi rule secara unsupervised.
Tetapi dalam 1 cluster bisa terjadi lebih dari satu rule sehingga lebih tepatnya:
1 DAG = 1 Cluster
dalam 1 DAG dapat dibuat n buah rule yang dapat membangun inferensi.
.
fungsi keanggotaan=fungsi yang menentukan kapan sebuah titik berteman dengan titik yang lain dalam suatu rantai pertemanan, dan tentukan bahwa untuk setiap fungsi memiliki radius keanggotaan, yaitu nilai maksimum fungsi yang diijinkan untuk permit pertemanan.
.
perluas gagasan ini untuk fungsi pertemanan=relasi pertemanan biner menjadi fungsi kenaggotaan untuk relasi pertemanan n-ner, yaitu bahwa setiap titik maksimum dapat mengambil teman sebanyak n sekaligus.
.
perluas gagasan ini untuk titik terbobot, bahwa kontinen titik dibagi dalam m area, setiap area memiliki bobot kekuatan pertemanan, misal w adalah bobot pertemanan maka w.f adalah fungsi yang tela dikalikan bobot untuk mengakuisisi pertemanan.
.
perluas ini bahwa setiap bobot titik memenuhi suatu persamaan, sehingga bobot cukup ditentukan dengan menghitung persamaan itu terhadap variabel independen tertentu (misal posisi atau kecepatan dan sebagainya).
Jika gagasna ini dibawa ke konstruksi rule tentunya menjadi lebih kompleks, yaitu menghasilkan DAG yang lebih kompleks.
.
InShaa Allah, jika dasar atau fondasi ide selesai dibangun, coba kamu baca2 ide2 dalam social network theory dan teori networking pada umumnya, juga PSO, adakah sesuatu yang baru dapat kita konstruksikan?
.
#END IDE 1?
OK SEMENTARA SELESAI!
#IDE 2:
Bagaiaman membangun compiler untuk bahasa dengan multitypegrammar?
solusi:
untuk tahapan verifikasi token, gunakan ide bahwa tiap2 token atau kata dibentuk oleh suatu alphabet A1, berupa kumpulan karakter, dan pembentukannya diatur oleh suatu gramatika reguler (himpunan gFSA).
.
untuk verifikasi token ini, konstruksikan mesin turing universal untuk gFSA, yang memverifikasi token dan memetakan ke simbol2 baru (terdapat peta pemetaan ke simbol2 baru, simbol yang hanya berupa 1 karakter, jadi 1 kata atau 1 token yang telah diverifikasi dipetakan ke 1 simbol baru).
.
lalu sebuah meta-kata (kumpulan simbol baru hasil penerjemahan kata-kata yang valid) terbentuk dan mengalir masuk ke mesin parser.
sebuah mesin parser adalah sebuah mesin turing universal yang dapat mensimulasikan seluruh bahasa bebas konteks.
meta-kata yang masuk adalah sebuah kalimat yang diatur oleh sebuah bahasa bebas konteks (cgf).
mesin turing universal ini memverifikasi setiap meta kata, jika telah selesai maka setiap meta kata dipetakan ke meta simbol baru, yaitu sebuah simbol berupa 3-tupel atau 4-tupel (sesuai konteks).
buat sejumlah rule yang memeriksa keabsahan semantik, buat mesin turing yang mengeksekusi rule2 itu.
.
dan setersunya. ide ini dapat diteruskan jika kita memiliki bahasa yang multitype-grammar dan hierarkis ke atas.
.
jika kita merepresentasikan setiap UTM dalam kompiler sebagai RBS (rule base system, kita dapat memperoleh sebuah RBS universal untuk gFSA dan RBS universal untuk cgf, dan setersunya.
#END IDE 2.
——————————————————————————————

CATATAN KERJA LAIN SAMPAI MARET 2018

——————————————————————————————
Mekanika Lagrange:
Bagaimana lagrange membangun mekanika di atas mekanika newton/klasik?
Apa assumsi2 atau postulat2 dasar lagrange?
Apa persamaan (hukum) mekanika pertama/utama lagrange?
Bagimana keduanya (set persamaan hukum newton dan set persamaan hukum lagrange)?
Ide-ide baru apa saja (mungkin tentang kebebasan cara pandang sistem kordinat, karena newton dapat dianggap hanya berpijak pada geometri euclid, dan diteremahkan secara panjang ke dunia moderen adalah dalam tradisi kordinat cartesian, sedang dalam masa lagrange telah dikenal sistem2 kordinat lain dan juga sistem kordinat kurvalinier sebagai genrelisasi kordinat, sehingga terlihat bahwa lagrange hendak mengeneralisir mekanika newton dalam cara pandang sistem2 kordinat tersebut dan dalam cara pandang yang lebih umum yaitu gagasan transformasi kordinat, dimana pada masa newton mungkin tidak terlalu diperhatikan. pada masa hamilton, orang telah mengenal ruang vektor bahkan dalam gagasan tensor, sehingga orang mencoba reformulasi gagasan mekanika lagrange dalam gagasan ruang vektor dan objek tensor, termasuk gagasan transformasi kordinat) yang dibenamkan lagrange?
—
——————————————————————————————
Review: https://en.wikipedia.org/wiki/Lagrangian_mechanics
(1).
Lagrangian mechanics is a reformulation of classical mechanics, introduced by the Italian-French mathematician and astronomer Joseph-Louis Lagrange in 1788.
.
(2).
In Lagrangian mechanics, the trajectory of a system of particles is derived by solving the Lagrange equations in one of two forms, either the Lagrange equations of the first kind,[1] which treat constraints explicitly as extra equations, often using Lagrange multipliers;[2][3] or the Lagrange equations of the second kind, which incorporate the constraints directly by judicious choice of generalized coordinates.[1][4] In each case, a mathematical function called the Lagrangian is a function of the generalized coordinates, their time derivatives, and time, and contains the information about the dynamics of the system.
.
Kerja utama dan pertama dalam menjawab seluruh persoalan mekanika klasik adalah menjawab masalah trayektori sistem partikel.
.
problem dan solusi masalah trayektori partikel ini menjadi basis bagi seluruh problem solving mekanika klasik dalam dunia mekanika lagrange.
.
lagrange merumuskan solusi ini dalam satu bentuk persamaan yaitu PERSAMAAN LAGRANGE.
.
persamaan lagrange mengambil dua bentuk, (keduanya ekivalen?) tetapi memiliki jalan solusi matematika dan imajinasi yang berbeda.
.
Persamaan lagrange ini bertindak set persamaan yang ekivalen atau analogi dengan set persamaan newton (hukum2 newton) dalam bangunan mekanika lagrange.
.
constrain?
lagrange multiplier?
generalized coordinat?
.
dimana posisi euler-lagrange equations?
dimana posisi neother’s theorem?
.
(3).
Lagrangian density = cara lagrange untuk merumuskan field.
.
#Apakah dynamic particle?
partikel dinamis = partikel yang sedang bergerak tetapi mengalami gaya2 mekanika, sehinga mekanika partikel dinamis adalah mekanika benda2 bergerak, bukan mekanika benda2 diam yaitu benda yang sedang diam tetapi mengalami gaya2 mekanika.
.
Itulah sebabnya perumusan atau permodelan pertama mekanika partikel dinamis afalah pada suatu kurva, dimana kurva menggambarkan gerakan atau dinamika, bukan pada garis datar dimana bendanya diam.
.
Itulah juga sebabnya mekanika lagrange sangat baik menjelaskan mekanika yang disebabkan oleh gaya2 konservatif. yaitu gaya2 yang bekerja pada partikel2 atau sistem dinamis, karena formulasi lagrange berpusat/origin pada imajinasi atau gambaran mental partikel dinamis. bukan pada benda diam yang mengalami gaya tarik atau gaya non-konservatif seperti gaya friksi pada benda diam.
.
#Bagaimana mekanika lagrange digeneralisir pada keseluruhan fisika?
Berdasarkan analogi gaya mekanika pada jenis gaya2 lain di fisika.
bentuk analogi ini dengan mengganti makna variabel gaya atau variabel2 lain, atau mengganti massa dengan gelombang (pada mekanika kuantum) dan sebagainya.
.
#Mengapa perumusan pertama atau standar mekanika lagrangian pada partikel dimulai dengan sistem kordinat polar atau kaleng?
ini karena gambaran mental pertama lagrange adalah partikel dinamik
berarti partikel bergerak.
berarti partikel di kurva.
tetapi gerak partikel kebanyakan (mungkin) atau yang menjadi gambaran mental lagrange adalah gerak seperti gerak elips, bola, spiral dan sebagainya secara umum gerak polinom dalam space atau hyperspace.
.
karena gerak kurva2 polinom dalam space atau hyperspace ini adalah lebih cocok dengan menggunakan kordinat bola atau kutub atau kaleng, maka sistem kordinat ini yang pertam digunakan.
.
selebihnya lagrange mungkinmenerjemahkan dalam konsep transformasi untuk sistem kordinat lain seperti cartesian atau secara umum sistem kordinat kurvalinier atau generalized coordinat.
.
——————————————————————————————
Bismillahirrahmanirrahim:
#Fuzzy C-Means Clustering:
Review: https://home.deib.polimi.it/matteucc/Clustering/tutorial_html/cmeans.html
.
(1).
Fuzzy c-means (FCM) is a method of clustering which allows one piece of data to belong to two or more clusters.
one piece of data = 1 rekord
to belong to two or more clusters = termasuk ke dalam satu, 2 atau lebih data.
.
frequently used in pattern recognition = pattern adalah himpunan klaster. jadi sebuah objek dikenali polanya berarti dikenali susunan klasternya.
.
#IDE
Kita dapat membagi dua cara penggunaan klasterisasi k-mean atau fuzzy c mean untuk mengenali pola objek, yaitu sebagai berikut:
[Pengenalan metaobjek, yaitu metaobjek = dataset]:
Sebuah dataset memodelkan fenomena atau objek, lalu misal ditanyakan, apa pola atau pattern dari fenomena/objek tersebut?
Itu ekivalen dengan merumuskan bahwa sebuah fenomena/objek/dataset adalah ekivalen dengan suatu susunan klaster.
.
Sehingga misal kita memiliki n buah objek, misal:
objek 1,2,5,7 dikenali memiliki susunan klaster yang sama atau profil klaster yang sama, maka objek 1,2,5,7 adalah ekivalen secara pattern, dengan demikian mereka dikenali sebagai objek tertentu yng sepadan.
dan seterusnya.
.
[Pengenalan objek, yaitu objek = rekord dataset]
akan tetapi ini bisa dilihat secar internal sebagai berikut:
sebuah dataset dicari patternnya atau susunan profil klasternya, setelah ditemukan, jika datset itu membengkak atau bertambah, maka semua rekord2 tambahan itu bisa dikenali atau diklaster ke dalam susunan klaster yang sudah ada. Sehingga rekord bari dinamakan dikenali ke dalam satu klaster tertentu.
#END IDE
—————
(2).
Di atas ide fuzzy c means ini orang merumuskan fungsi optimasi klaster sebagai berikut:
Sebuah fungsi optimasi J berdasarakan nilai m>1, adalah Jm, dimana:
uij= nilai_fuzzy_keanggoataan_rekord_i_terhadap_klaster_j
xi = rekord ke i
cj = centroid ke j
Jm = jumlah_seluruh_dalam_i [jumlah_seluruh_dalam_j uij(norm(xi-cj))^2]
.
Filosofi fungsi di atas adalah:
hitung kuadrat jarak (norm) sebuah rekord (misal rekord ke-i) ke sebuah klaster (misal klaster ke j), lalu kalikan kuadrat jarak itu dengan nilai fuzzy rekord tsb ke klaster, sebut hasilnya adalah kuadrat_jarak_ij, lalu untuk seluruh klaster (seluruh j), jumlahkan seluruh kuadrat_jarak_ij itu.
.
misal hasilnya adalah total_kuadrat_jarak_ij_untuk_suatu_i_tertentu.
.
lalu hitung untuk tiap-tiap rekord yang lain (i yang lain).
.
lalu jumlahkan seluruh total_kuadrat_jarak_ij_untuk_suatu_i_tertentu untuk seluruh i.
.
diperoleh Jm.
——
(3).
Filosofi rumus hitung ulang centroid ke-j yaitu cj:
cj adalah sebuah vektor, dimana jumlah entrinya/atributnya adalah sama dengan jumlah entry/atribut rekord dataset.
.
sehingga rumus cj=…. adalah rumus persamaan vektor.
.
sehingga rumus c1=…. menyatakan vektor centroid 1.
Yaitu:
c1 = (
nilai_fuzzy_rekord_1_terhadap_klaster1 x rekord1+
nilai_fuzzy_rekord_2_terhadap_klaster1 x rekord2+
nilai_fuzzy_rekord_3_terhadap_klaster1 x rekord3+
.
.
.
nilai_fuzzy_rekord_N_terhadap_klaster1 x rekordN)/total_seluruh_nilai_fuzzy_untuk_1
.
misal
uij/tot = nilai_fuzzy_rekord_1_terhadap_klaster1/total_seluruh_nilai_fuzzy_untuk_1
kalikan.
.
C1 =
uij/tot x vektor_x1 +
uij/tot x vektor_x2 +
uij/tot x vektor_x3 +
.
.
.
uij/tot x vektor_xN +
————————————————————————————–
REVIEW: http://cs.umw.edu/~finlayson/class/fall15/cpsc326/
.
http://cs.umw.edu/~finlayson/class/fall15/cpsc326/notes/17-recursion-theorem.html
.
(1).
#Mengapa pembuktikan halting problem menggunakan mesin yang berlaku rekursif?
Ini menunjukkan sebuah fondasi elegan dan kuat bagi pembuktian halting problem, yaitu pembutian dibangun diatas teorema rekursif.
.
(2).
#Bagaimana standar pembuatan mesin turing yang bersifat rekursif?
Sebenarnya mungkin tidak ada standar tetapi ini adalah yang paling sederhana dan memenuhi teorema rekursif. Konstruksi itu sebagai berikut:
pertama:
mereka membuat deksripsi mesin turing yang bernama SELF
(sebenarnya secara umum sebut saja M).
.
SELF: takes no input, but prints its own description.
tidak menerima input tetapi hanya mencetak deskripsi dirinya sendiri (enkoding dirinya sendiri)
.
kedua:
ada yang berbeda dalam konsep rekursif dalam teorem rekursif dalam matematika sebelumnya:
yaitu bahwa:
untuk setiap fungsi f:X->X maka disana mesti ada F:N->X dimana f bersifat rekursif di aatas seluruh nilai F secara berurut.
.
tetapi konsep teorem rekursif dalam situs ini:
untuk setiap mesin turing, maka mesin turing itu dapat memproduksi dirinya sendiri.
.
dimana perbedaaanya?
coba lihat Kleene’s recursion theorem, apa maksud teorema ini.
.
(3).
On review: https://saadquader.wordpress.com/2013/02/07/kleenes-recursion-theorem/
#Apakah partially computable?
partially computable = hanya computable (HALT) pada beberapa input saja tetapi tidak semua.
.
demikian pula pengertian partial function.
.
#Apakah partial function dan total function?
partial function = fungsi yang terdefinisi pada sebagian domain atau pada sebagian input saja, tetapi tidak semuanya.
total function = fungsi yang terdefinisi pada seluruh domain atau pada seluruh input, tak bersisa.
.
jika diterpakan pada himpunan bilangan natural:
partial function = hanya terdefinisi pada sebagaian bilangan natural.
total function = terdefinisi pada seluruh bilangan natural.
.
#Kenapa kita menggunakan himpunan bilangan natural?
karena konteks kita adalah komputasi yang bekerja dalam wawasan computable bilangan natural.
.
#Apakah fungsi dalam komputasi?
sebuah fungsi adalah sebuah program P.
jika fungsi menerima input n, maka P juga menerima input n
jika m adalah output fungsi, maka P juga mengeluarkan output m.
.
——————————————————————————————
#Tentang posisi partial computable function terhadap computable TM (runut ulang pembuktian mereka):
Lemma:
Setiap partial computable function adalah computable oleh sebuah TM.
(Artinya bahwa terdapat TM yang dapat mensimulasikan partial function dimana TM itu computabe)
Bukti:
Buat M turin machine dimana M:
misal f(x) adalah partial function.
M = “untuk input (f,x):
1. bila f defined di x maka output M adalah yes
2. bila f undefined di x maka output M adalah no.
3. Halt.”
.
.
qed.
.
teorema ini tidak berlaku jika dia bukan partial computable tetapi hanya partial, yaitu misal dia partial function diatas himpunan bilangan rill bukan bilangan asli.
.
#Tentang posisi partial computable TM terhadap UTM (runut ulang pembuktian mereka):
lemma:
Setiap partial computable TM adalah computable di UTM.
Bukti:
karena telah diketahui lebih dulu bahwa TM halt di beberapa I, tertentu (sebut IH) dan loop forever di beberapa nilai I yang lain maka dapat dibuat UTM.
UTM= “untuk input <TM,I>:
1. Jika I adalah IH, maka output UTM adalah yes
2. Jika TM loop forever di I, maka output UTM adalah no.
3. Halt”
.
qed.
.
catatan:
ini tidak melanggar halting problem, karena TM tekah diketahui sebelumnya (dengan percobaan sejumlah beberapa kali atau tinjauan sederhana) bahwa TM halt di IH, tetapi tidak diketahui di seluruh I.
artinya bahwa jika tidak diketahui bahwa TM partially computable terhadap I, maka tak ada UTM yang bisa menentukan bahwa TM halt di I atau tidak.
.
ini analogi atau ekivalen dengan sebuah TM yang sudah diketahui terhadap suatu I, maka otomatis sebuah UTM dapat dibuat untuknya.
.
#Mengapa partial function dikatakan juga orang sebagai partial computable function dan untuk total function orang juga menyebutnya total computable function?
partial fuction = f yang terdefinisi sebagian di atas sebarang himpunan.
partial computable function = f yang terdefinisi sebagian di atas himpunan bilangan natural.
.
total function = f total di atas sebarang himpunan
total computable function = f total di atas himpunan bilangan natural.
.
———————————
#Bagaimana orang membuktikan teorema S-m-n?
Teorme S-m-n menyatakan:
untuk setiap fungsi rekursif parsial p(m,n), terdapat sebuah fungsi computable total f(m) sedemikian sehingga fungsi p(m,n)=p(f(m),n).
Secara intuitif kita dapat membuktikan teorema ini didahului dengan konsep berikut:
.
#Tentang sebarang fungsi dengan argumen bilangan natural:
Sebarang fungsi dengan argumen bilangan natural atau tupel bilangan natural adalah sebuah fungsi pengindeks.
misal p(m,n) maka p mengindeks menggunakan (m,n), misal: p:NxN–>X
maka p mengindeks X menggunakan (m,n).
.
atau misal F:N–>X, maka F mengindex X.
.
Secara intuitif jika X diindeks ke dalam (m,n) maka X dipetakan ke sebuah matriks berukuran MxN. ini seumpama memetakan bilangan rasional ke bidang bilangan pecahan.
.
akan tetapi menurut argumen cantor, kita dapat membuat pemetaan f(m) yang dapat memetakan 1-1 bidang bilangan tersebut (jika digambar dalam cara zig-zag) sehingga sebuah index dalam cara (m,n) adalah setara dengan indeks dalam arah (n) saja menggunakan f(m).
.
———————————
(4).
#Apakah computable function?
f computable function = disana ada algoritma yang bisa menghitung f.
.
#Bagaimana kedudukan konsep computable function dalam komputasi?
computable function adalah abstrak daari semua model komputasi (mesin turing, mu function, lambda calculus, post machines dan register machines).
.
artinya bahwa computable function dapat diekspresikan secara formal oleh model2 komputasi itu. dan ekspresi itu setara satu sama lain antar model komputasi.
.
#Bagaimana orang menyetarakan/mengekspresikan computable function dengan model komputasi?
sumber: https://en.wikipedia.org/wiki/Computable_function.
Formally speaking, a partial function f : N k ? N {\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} } f:{\mathbb N}^{k}\rightarrow {\mathbb N} can be calculated if and only if there exists a computer program with the following properties:
1). If f ( x ) {\displaystyle f(\mathbf {x} )} f({\mathbf x}) is defined, then the program will terminate on the input x {\displaystyle \mathbf {x} } \mathbf {x} with the value f ( x ) {\displaystyle f(\mathbf {x} )} f({\mathbf x}) stored in the computer memory.
2). If f ( x ) {\displaystyle f(\mathbf {x} )} f({\mathbf x}) is undefined, then the program never terminates on the input x {\displaystyle \mathbf {x} } \mathbf {x} .
———————–
#Bagaimana perbedaan pendefinisian bahasa recursive [enumerable] menggunakan computable function dan mesin turing?
Dalam versi mesin turing:
Sebuah bahasa L adalah recursive (computable) jika hanya jika ada mesin turing M dimana untuk input w, M HALT pada accept state jika w elemen L dan M berakhir pada non-accept state jika w bukan elemen L.
.
Sebuah bahasa L adalah recursive enumerable jika hanya jika ada mesin turing M dimana untuk input w, M HALT pada accept state jika w elemen L dan M HALT pada non-accept state atau loop forever jika w bukan elemen L.
.
Dalam versi computable function: perhatikan saja kesetaraan berikut:
recursive = computable
enumerable = countable, terbilang, tercacah.
defined = halt pada accept state = [f(w)=1] atau halt pada non-accept state [f(w)=0]
undefined = loop forever [f(w) undefined].
.
Sehingga untuk computabel function cukup dinyatakan:
L recursive jika ada computable f, f(w)=1 jika w elemen L dan f(w)=0 jika w bukan elemn L.
L recursive enumerable jika hanya jika f(w) defined untuk w elemen L.
————————————————————————–
semi decideable = recursivly enumerable.
————————————————————————–
sktesa bukti P=NP
misal sebarang persoalan adalah NP
artinya bahwa terdapat TM yang bisa meneyesaikannya dalam kompleksitas langkah2 NP.
.
tetapi misalkan disana dapat dibuktikan terdapat TM lain yang ekivalen, sedang TM itu bekerja dalam langkah2 P, maka P=NP.
————————————————————————–
#Apakah cutting edge dari penelitian komputasi sekarang?
Orang sedang berpikir untuk membangun model komputasi yang beyond mesin turing.
.
#Apakah hakikat computable function?
Computable function = fungsi yang dapat diselesaikan dalam sejumlah langkah di atas kertas menggunakan pensil dan kertas, ornag menyebut ini sebagai effective procedure.
.
Akan tetapi secara moderen ini berkembang menjadi:
computable function = fungsi yang dapat diselesiakan oleh sebuah algoritma atau terdapat algoritma yang sepadan untuk menyelesaikannya, secara umum, terdapat model komputasi (mesin turing, mesin register, lambda calculus, dan sebagainya) yang bisa menyelesaikannya.
.
#Bagaiamana orang mengerjakan atau menerjemahkan computable function ke model komputasi?
Yaitu dengan menjadikannya input pada model komputasi tertentu.
untuk menjadikannya input, prinsip yang paling fundamental adalah:
menerjemahkannya (melakukan enkoding) fungsi tersebut (batang tubuh fungsi berseta inputn outputnya) ke dalam alphabet yang diterima oleh model komputasi tersebut.
.
#Mengapa mefreka mengatakan bahwa disana ada countably computable function yang bisa di modelkan oleh model komputasi tertentu?
Bukti:
setiap computable function dapat dienkod ke alphabet atau bilangan.
akan tetapi setiap hasil enkod itu bisa dilihat sebagai sebuah kombinasi string.
akan tetapi jumlah kombinasi string yang bisa dibentuk banyaknya adalah countable.
sehiangga benar bahwa jumlah ynag mungkin (maksimal) adalah countable.
qed.
.
#Apakah finitary functions?
finitary functions = fungsi yang menerima finite argumen.
infinitary functions = fungsi yang menerima infinite argumen.
.
Ini perluasan dari:
finitary operation = operator yang mengoperasikan finite operand.
infinitary operation = operator yang mengoperasikan infinite operand.
.
Ini diperluas lagi menjadi:
finitary proposition = proposition yang memeiliki finite anteseden.
infinitary proposition = proposition yang memeiliki infinite anteseden.
.
selanjutnya ini diperluas lagi ke logika orde-n.
.
#IDE:
Bagaimana kita menerpakan uncertanity pada fondasi matematika analisis?
salah stunya dengan menerapkan probability pada fondasi definisi pemetaan dan fungsi.
.
misal:
x=y ==> f(x)=f(y)
diperluas menjadi:
P(x=y)=*a ==> P(f(x)=f(y))=*b
.
dst.
.
atau kita menerapkan konsep fuzzy pada fondasi analisis.
dst.
#END IDE.
.
#Mengapa Busy beaver adalah contoh fungsi yang uncomputable?
karena dia dapat dibawa ke persoalan halting problem yang undecideable.
.
#Mengapa kolmogorov complexity juga dikategorikan sebagai contoh fungsi yang uncomputable?
karena dia dapat dikembalikan pada persoalan halting problem.
ini karena tidak ada TM yang dapat menentukn bahwa program yang telah dibuat adalah sudah merupakan program terpendek untuk mengeksekusi suatu string.
.

MESIN TURING (TURING MACHINE)

Bismillah:
Urutan gagasan dalam topik ini adalah:
Turing -> Shanon -> Minsky -> Yuri -> Wolfram:
——————————————————————————————
(1).
Mengapa ukuran maksimal jumlah instruksi mesin turing adalah mxn
dimana m jumlah state dan n jumlah color atau label transisi atau simbol input.
.
berdasarkan argumen bahwa untuk setiap state adalah dapat memiliki n color.
.
sehingga untuk setiap kemungkinan color itu, mesti dibuat transisinya atau rulenya.
.
Tetapi bagaimana jumlah kombinasi sederhana mxn itu dapat menyatakan atau mensimulasikan semua mesin turing?
.
(2).
Halting problem untuk m state dan n color adalah memiliki arti:
dimulai dengan pita kosong, apakah mesin turing (m,n) akan halt?
.
Halting?
Halt jika mesin turing mencapai suatu kombinasi state-color yang didefinisikan atau ditentukan.
Pada dasarnya hal adalah keputusan, yang berarti halt adalah saat mesin turing mengambil keputusan.
.
——————————————————————————————
#Tentang Godel Number:
Godel number digunakan untuk memetakan sebuah mesin tuirng standar kepada sebuah himpunan bilangan yang terurut.
.
Secara umum, sebuah godel number adalah sebuah 2-tupel (N,f*)
dimana N adalah bilangan positif dan f* fungsi yang memetakan/encode bilangan positif tersebut.
.
Setiap mesin (simbol dan state) yang dinyatakan ke dalam bialngan ini, maka himpunan bilangan ini adalah enkoding mesin tersebut ke dalam godel number.
——————————————————————————————
#Mesin abstrak:
Adalah himpunan bilangan godel number yang menyatakan enkoding sebuah mesin.
——————————————————————————————
Review:On the Notion of Universality of Turing Machine
By: A. NOZAKI
(1).
* Here the word “total state” means a combination (s, a, n) of an internal state sofa machine M, a sequence a of symbols on its tape and a position n of the read-write head of the machine.
.
total state = a combination (s, a, n) of an internal state s of a machine M.
total state = just (s, a, n)? or all (s, a, n) for untuk sebuah s?
.
(2).
** Here, the number 0 is added to the range of f to indicate machine-stops; if the machine
stops at a total state w, then the value of/(w*) of/at w* is defined to be 0.
.
f menyatakan simbol di pita.
N suatu bilangan positif yang menomori posisi pita, sehingga f(x) dimana x elemen N adalah berarti isi dari pita.
.
Atau f menyatakan nilai pita, dimana x pada f(x) adalah sebuah total state?
.
(3).
internal state = s
total state = (s,a,n)
.
f(x)=y
maka y adalah sebuah nilai di pita.
x adalah total state.
f memetakan total state ke nilai di pita.
.
total state bukanlah state dari turing machine, tetapi abstract machine.
s bukanlah state dari turing machine, tetapi state dari abstract machine.
f(x) bukanlah suatu nilai di pita pada turing machine, tetapi suatu nilai dalam himpunan tupel (N,f) yang merepresentasikan abstract machine.
.
tak ada istilah pita mesin, tetapi yang ada adalah mirip pita, yaitu image f.
pada image f terdapat 0 sebagai tanda stop atau halt.
.
pertanyaannya, bagaimana abstract machine bersifat umum dia atas turing machine? atau bagaimana dia ekivalen?
.
apakah abstract machine?
.
cara kerja abstract machine sederhana saja, yaitu:
ada himpunan state, ada fungsi f yang memetakan total state ke image f. SELESAI.
.
w* = adalah total state yang dienkoding ke godel number.
f* = adalah image f yang sudah dienkoding ke godel number.
.
(4).
Apakah (N,f*)?
Yang jelas bahwa (N,f*) adalah inti cara menyatakan mesin abstrak.
.
abstract machine = representasi mesin tuirng ke dalam sistim bilangan (sistem bilangan yang menggunakan bilangan godel), analogi dengan sistim bilangan jam 2, jam3, biner, dsb sistem bilangan, sehinhga pada dasarnya, ini juga menyatakan secara implisit bahwa sebuah sistem bilangan adalah sebuah mesin abstrak.
.
tetapi mengapa ada sistem bilangan dibangun dengan mendefinisikan sebuah fungsi?
ini karena sistem bilangan godel dibangun dari bilangan bulat positif. sehingga sebuah bilangan bulat dipetakan secara bijective ke sebuah bilangan lain yang dinamakan godel number.
.
mengapa godel number dinyatakan dalam tupel (N,f*) ini karena godel number dibangun dari bilangan bulat positif, sehingga menyebut bilangan godel adalah ekivalen dengan menyebut bilangan positif domainnya dengan hasil pemetaanya ke godel number.
.
———
factor = partikel penyusun, bilangan penyusun, misal 9 faktornya adalah 3 yaitu bilangan penyusunnya adalah 3 karena 3 dikali 3 adalah 9 atau membangun 9. kalu dibawa ke mesin berarti mesin penyusun, ini karena jika mesin dinyatakan ke dalam sistem bilangan maka ada kemungkinan sebuah sub himpunan bilangan yang juga membangun mesin atau menyatakan mesin sehingga ini berarti mesin di dalam mesin atau mesin factor.
.
factory = pabrik, yaitu tempat dimana partikel2 dirakit membangun materi, atau komponen2 dirakit membangun sistem.
.
konsep factor ini membawa kepada konsep integer factorization.
yaitu analisa terhadap faktorisasi bilangan2 bulat.
secara mendasar hanya dibatasai pada bilangan bulat positif.
.
integer factorization mengantar kepada ide composit number dan prime number dan unit number.
composite number = bahwa sebuah integer dibangun oleh 1 dan dirinya sendiri dan paling sedikit satu bilangan bulat lain yang bukan 1 dan dirinya sendiri.
prime number = sebuah integer yang dibangun oleh hanya 1 dan dirinya sendiri.
unit number = sebuah integer yang hanya dibangun oleh 1.
.
proses menemukan factor sebuah integer mungkin dinyatakan dalam sebuah algoritma, proses ini disebut proses dekomposisi.
algoritma ini mencari semua factor dari sebuah integer.
.
contoh algoritma:
berdasarkan bahwa composit integer selalu dapat dinyatakan sebagai factorisasi ke dalam bilangan2 prima, maka pencarian dimulai dengan cara:
mulai bagi dengan 2, teruskan sampai semua 2 diperoleh.
lalu dengan 3, teruskan sampai semua 3 diperoleh.
dan seterusnya untuk bilangan prima berikut sampai tercapai sang komposit integer.
algoritma ini berdasarkan kenyataan teorema fundamental aritmetika:
Bahwa setiap bilangan bulat adalah selalu merupakan hasil kali dari 1 dan bilangan2 prima dan bahwa ekspresi hasil kali ini atau factorisasi ini adalah unik.
.
#TENTANG TEOREMA FUNDAMENTAL ARITMETIKA
atau:
Teorema fundamental aritmetika:
setiap bilangan bulat adalah merupakan string factorisasi unik dari 1 dan bilangan2 prima.
.
konsep factorisasi bilangan bulat ini menghasilkan bentuk standar kanonik dan bentuk standar yang infinite, infiniote yaitu bahwa setiap bilangan bulat adalah selalu merupakan perkalian bilangn prima yang jumlahnya tak berhingga mulai dari prime terkecil hingga tak terhingga.
.
pernyataan bilangan bulat ke dalam bentuk kanonik menghasilkan konstruksi bilangan rasional dalam bentuk kanonik juga yaitu dengan membolehkan pangkat negatif pada bentuk kanonik bilangan bulat.
.
divisor = adalah konsep yang muncul sebagai ekivalen dari factor, factor adalah penyusun, divisor adalah pembagi, sebuah factor adalah juga pembagi, artinya hanya factor dialah yang bisa membagi habis bilangan bulat karena factor adalah penyusun sempurna.
.
#TENTANG COMMON DIVISOR:
common divisor = common factor
common factor = jika terdapat bilangan2 bulat b1,b2,b3,…,bn, maka mesti ada paling sedikit 1 factor bersama diantara n buah bilangan bulat tersebut, boleh jadi ada m buah factor bersama.
.
greatest common divisor/factor/measure (gcd/gcf/gcm) = highest common factor/divisor/measure (hcf/hcd/hcm)
= diantara common factor dari bilangan2 bulat b1,b2,b3,…,bn, maka mesti ada common factor terbesar atau maximum.
.
least common divisor/factor/measure (lcd/lcf/lcm) = lowest common factor/divisor/measure
= diantara common factor dari bilangan2 bulat b1,b2,b3,…,bn, maka mesti ada common factor terkecil atau minimal.
.
gagasan gcf dan lcf memicu lahirnya konsep max dan min, lowest/lower bound, higher/highest bound dan sup/inf pada interval di bilangan/garis rill.
dan itu kemudian memicu gagasan limit cauchy, kontinu, differensial, kalkulus, geometri differensial, dsb.
.
#TENTANG COMMON FACTOR POLYNOMIAL:
ini adalah generalisasi gcd pada bilangan bulat.
.
mengapa polynomial dipandang sebagai generalisasi bilangan bulat?
ditinjau dari sisi klasik:
karena pada masa itu fungsi yang paling pertama kali dikenal adalah polynomial, menyatakan sebuah polynomial di atas himpunan bilangan bulat adalah berarti menyatakan sebuah sub himpunan bilangan bulat yang memenuhi polynomial tersebut.
.
sehingga pandangan generalisasi adalah menjadi:
sebuah bilangan bulat —> sebuah himpunan/subhimpunan bilangan bulat (yg memenuhi suatu polynomial tertentu).
.
ditinjau dari sisi moderen:
karena segala fungsi yang memiliki turunan, adalah dapat dinyatakan sebagai sebuah deret dalam bentuk polynomial.
sehingga perumuman menjadi:
sebuah bilangan bulat —> sebuah fungsi sebarang (polynomial)
.
semua gagasan ini memicu lahirnya berbagai algoritma untuk menghitung gcd/lcd, dan yang menjadi basic adalah algoritma euclid untuk polynomial yang digeneralisir dari untuk menghitung gcd/lcd dari bilangan bulat.
.
#REDUCING FRACTIONS:
ide ini berdiri di atas konsep common divisor (cd).
misal suatu bilangan rasional dinyatakan oleh a/b
tetapi divisor a adalah a1,a2,a3,…,an
divisor b adalah b1,b2,b3,…,bm
dan gcd(a,b)=ai=bj
maka reduksi a/b = (d.ai)/(g.bj) = d/g
.
#COPRIME NUMBER:
ide coprime dapat dilihat sebagai perluasan konsep bilangan prima kepada tupel bilangan bulat.
misal:
tupel (a,b) a dan b bilangan bulat, maka (a,b) adalah coprime jika hanya jika gcd(a,b)=1
.
#GEOMETRIC VIEW (ARTI GEOMETRI):
ide ini dibawa orang kepada pandangan dasar geometri sebagai berikut:
misal sebuah area dalam bidang euclid yang dinyatakan luasnya oleh bilangan bulat a dan b
yaitu memiliki luas axb, maka area lain yang dapat menutupi seluruh luas axb hanyalah area yang luasnya dinyatakan oleh common divisor (a,b), misal c adalah common divisor, maka suatu area seluas cxc=d dapat menutupi area axb dengan cara mengalikan d dengan suatu bilangan bulat k.
area terbesar yang dapat menutupi axb adalah gcd(a,b)xgcd(a,b) dan area terkecil yang dapat menutupi axb adalah lcd(a,b)xlcd(a,b).
.
secara umum:
suatu hyperspace euclid/noneuclid yang berukuran [a] dan [b] dimana [a] dan [b] adalah perluasan bilangan bulat ke dalam sistem bilangan tertentu, maka hyperspace itu dapat ditutupi oleh common factor [a] dan [b], penutup terbesarnya adalah gcd([a],[b]), penutup terkecilnya adalah lcd([a],[b]).
.
#PERLUASAN BILANGAN BULAT KE MODULO:
tentang bagaimana sifat2 bilangan bulat dibawa ke modulo adalah sebagai berikut:
sifat common factor juga berusaha dibawa orang ke dalam bilangan modulo.
sehingga otomatis juga sifat gcd dan lcd.
sehingga otomatis juga sifat coprime, prime.
sehingga otomatis juga geometric viewnya.
sehingga otomatis juga genetralisasi polinomial dan sifat2nya.
dan seterusnya.
.
#BAGAIMANA DIA MENJADI UNIVERSAL PADA PENERAPANNYA?
oleh karena bahwa beberapa sistem di alam semesta (fisika, kimia, biologi, kompleksitas, dsb) dapat dinyatakan secara mendasar kedalam modulo, maka konsep2 bilangan bulat dapat diterapkan pada sistem tersebut.
.
#BAGAIMANA KONSEP2 BILANGAN BULAT SECARA LEBIH LUAS DITERAPKAN KE GEOMETRI?
ide ini berpijak pada polinomial, ketika ide polinomial memperluas sifat2 bilangan bulat sebagai suatu himpunan tertentu yang berperilaku tertentu dalam artian sebuah polinomial.
akan tetapi bentuk2 dasar geometri seperti garis, reactangular, kubus, dst, dst dapat dinyatakan sebagai sebuah ekspresi polinomial di cartesian atau tanpa cartesian.
.
ini berarti deduksi2 sifat bilangan bulat adalah berarti juga deduksi2 sifat2 geometri benda2 tersebut atau sebaliknya. inilah sebabanya mengapa beberapa teorema tentang bilangan bulat dipecahkan dengan menggunakan geometri.
.
semesta ide ini diperluas orang untuk bialngan rill dan kompleks, yaitu bahwa orang membangun geometri yang sepadan dengan perumusan sifat2 bilangan rill atau kompleks.
demikian untuk bilangan quaternion, dan seterusnya.
.
#EUCLID ALGORITHM:
ide dasar : gcd(a,b)=gcd(b,sisa) dan seterusnya.
.
#TENTANG BAGAIMANA ORANG MENGHITUNG GCD:
#1:
dengan cara diagram venn.
#2:
dengan euclid algorithm.
kunci dasar algoritma euclid adalah:
gcd(a,a)=gcd(a,a-a)=gcd(a,0)=a
gcd(a,b)=gcd(a-b,b) if a>b
gcd(a,b)=gcd(a,b-a) if b>a
redefinisi konsep ini diperluas dengan menggunakan aritmetika modulo.
#3:
.
#LONG DIVISION:
ide pembagian yang biasa kamu pelajari waktu SD.
.
ada beberapa cara long division, mungkin berbeda di beberapa negara tetapi ini adalah bentuk umum dan standar saja.
.
#POLYNOMIAL LONG DIVISION:
sama long division tetapi diterapkan ke polynomial.
.
secara umum ini dapat diterapkan ke berbagai sistem bilangan.
.
#EUCLEDIAN DIVISION FOR POLYNOMIAL:
adalah polynomial long division.
.
#QUOTIENT, REMAINDER, DIVINDEN, DIVISOR:
P(X)=A(X).Q(X) + R(X)
DIVINDEN=P(X)
DIVISOR=A(X)
QUOTIENT=Q(X)
REMAINDER=R(X)
.
#FINDING TANGENTS TO POLYNOMIAL FUNCTIONS:
untuk suatu x=r, maka remainder yang diperoleh dengan membagi polynomial berpangkat tertinggi n dengan (x-r)^(n-1) adalah sebuah kurva/garis tangent yang melewati titik x=r.
.
#CARA FAKTORISASI POLYNOMIAL:
tentukan akar2nya, minimal 1 ditemukan maka pemfaktoran dapat dilakukan dengan metode polynomial long division.
KALAU TIDAK DIKETAHUI MAKA YANG DIPEROLEH ADALAH BENTUK REMAINDER.
.
P(X)=A(X).Q(X) + R(X), A(X) dan Q(X) adalah masing merupakan faktor dari P(X) jika hanya jika R(X)=0.
.
#MONIC:
bentuk polynomial univariate dengan koefisien leading term nya adalah 1.
.
#DENOMINATOR:
misal a=b/c
maka c=denominator.
.
#SYNTETIC DIVISION:
teknik2 pembagian polinomial menggunakan tangan atau untuk keperluan membuat algoritma program yang melakukan pembabian polinomial, dapat dilihat di wikipedia saja.
.
arti penting ide2 disini adalah pada sisi paraktisnya untuk mendeduksi berbagai gagasan dalam pandangan aritmetika polynomial.
.
#CYCLIC REDUNDANCY CHECK:
Adalah sebuah bangunan konsep besar yang didasarkan pada ide remainder dari polynomial. untuk mengecek keabsahan signal setelah terganggu oleh noise.
ide ini merepresentasikan bit ke dalam polynomial lalu mengeceknya dengan menggunakan polynomial.
.
——————————————————————————————
#COMPLEXITY
(1).
DECISION PROBLEM = semua masalah yang jika dijawab maka jawabannya adalah yes atau no, atau semua masalah yang dapat dimodifikasi sehinga dapat direpresentasikan oleh masalah yang hanya membutuhkan jawaban yes atau no.
.
DECIDABLE = sebuah decision problem adalah decidable jika hanya jika terdapat algoritma atau set instruksi mesin turing atau set instruksi automata yang dapat memberi jawaban yes atau no.
NON DECIDABLE = jika tak ada algoritma yang dapat memberikan jawaban yes atau no.
.

——————————————————————————————
#APAKAH NUTM?
NUTM = sebuah mesin turing yang memiliki n buah prosesor dan m buah pita, m>=n, n buah prosesor artinya ada n buah start state(?).
——————————————————————————————
#STRUKTUR ALJABAR:
WAWASAN:
Algebraic structures
Group-like
Semigroup / Monoid
Racks and quandles
Quasigroup and loop
Abelian group
Magma
Lie group
Group theory
Ring-like
Ring Semiring
Near-ring
Commutative ring
Integral domain
Field Division
ring
Ring theory
Lattice-like
Lattice Semilattice
Map of lattices
Lattice theory
Module-like
Module
Group with operators
Vector space
Linear algebra
Algebra-like
Algebra
Associative
Non-associative
Composition algebra
Lie algebra
Graded
Bialgebra
——————————————————————————————
#TENTANG OPERASI:
operasi = kombinasi n-ary operand (input, argument) menjadi sebuah output (result, value).
finitary operation = operasi n-ary dimana n berhingga.
infinitary operation = operasi n-ary dengan n tak berhingga.
.
#Bagaimana caranya orang mengkonstruksikan operasi?
dengan menggunakan definisi pemetaan.
suatu operasi * n-ary didefinisikan sebagai:
*:S1xS2xS3x…xSn —-> S
dimana S1=S2=S3=…=Sn
.
An operation ? is a function of the form ? : V ? Y, where V ? X1 × … × Xk. The sets Xk are called the domains of the operation, the set Y is called the codomain of the operation, and the fixed non-negative integer k (the number of arguments) is called the type or arity of the operation.
.
ini sebabnya mengapa orang mendefinisikan transisi dalam automata sebagai sebuah monoid atau secara umum struktur aljabar, karena sebuah transisi dapat dinyatakan sebagai sebuah operasi n-ary, T:QxS—>Q
.
#Generalisasi operasi
generalisasi operasi adalah sebagai berikut:
input dan output operasi = bilangan, set, transformasi geometri, state, string, true, false, dsb.
.
#Dasar2 postulasi operasi
associative, commutative, anticommutative, idempotent, dan lain sebagainya adalah sifat2 universal yang mungkin dipostulatkan sebagai sifat operasi yang melekat kepada operasi bila digunakan.
.
#Perbedaan operator dan operation
Operator = operation.
hanya secara teknis memiliki perbedaan penhggunaan.
jika mementingkan hasil dan operand secara eksplisit dalam jejala deduksi maka digunakan operasi.
misal 2 + 3 = 5, dimana disini 5 penting ditulis dalam alur deduksi, demikian juga 2 & 3.
jika mementingkan proses, maka digunakan operator, artinya bahwa hasil dari kombinasi input tidak perlu eksplisit dalam urai deduksi, misal +(2,3), +(2,3) terus terbawa tanpa perlu menulis 5.
.
#Hubungan arti antara operasi dan relasi:
dari definisi:
? : V ? Y, where V ? X1 × … × Xk
k-ary operation = k+1-ary relation, karena relasi mencakup output juga, sedang operasi hanya mencakup input.
.
#Order of operations
sebuah himpunan rule yang digunakan untuk merangking derajat sejumlah operasi ketika digunakan mengevaluasi sebuah ekspresi matematika.
.
himpunan rule ini boelh kesepakatan universal, boleh dipostulatkan oleh user ketika hendak menulis sejumlah ekspresi matematika.
.
#Hyperoperation:
Generalisasi operasi jumlah ke kali lalu ke eksponen dan seterusnya.
ini seperti tensor bagi susunan bilangan yaitu suatu susunan rank n, maka hyperoperation adalah operasi rank n.
atau analogi dengan ide cantor yang mengeneralisir bilangan tak hingga ke dalam konsep bilangan cardinal.
.
ada beberapa teori yang dikemukakan orang untuk mendefinisikan hyperoperation.
.
hyperoperation untuk saat ini sepertinya hanya diterapkan untuk konstruksi large number.
.
yang menarik dari konstruksi bilangan menggunakan hyperoperation adalah bagaimana menerapkan aritmetika di atas himpunnan bilangan yang dikonstruksi oleh hyperoperation, bagaimana ide komputasi di atasnya? bagaimana kompleksitas kalkulasinya? dsb.
.
SELESAI.
——————————————————————————————
#ABSTRACT ALGEBRA?
Abstract algebra = the study of any kinds of structure algebra.
Abstract algebra = moderen algebra.
.
#UNIVERSAL ALGEBRA?
universal algebra = algebra where the object or element is an structure algebra.
.
#PREFIX NOTATION:
contoh a+b, prefix notationnya adalah +ab
——————————————————————————————
#MONOID?
(1).
a monoid is an algebraic structure with a single associative binary operation and an identity element.
.
Monoid = structur algebra –> set + 1 opetrasi biner + postulat asiosiatif + postulat identity.
.
monoid = semigrup + postulat identity
.
kompleksitas struktur aljabar dalam urutan adalah sebagai berikut:
magma/grupoid>semigrup>monoid>grup>abeliangrup>
.
tetapi ada dua jalur struktur yang terbentuk dari magma:
magma>semigrup>monoid>grup
dan
magma>quasigrup>loop>grup
.
total gambaran:
>semigrup>monoid>
magma> > grup
>quasigrup>loop>
dan berbagai kombinasi lain yang mungkin dengan memainkan postulat-postulat struktur.
.
#SECARA UMUM STRUKTUR ALJABAR (ALGEBRA STRUCTURE):
ada banyak struktur yang membangun suatu jejala struktur dengan struktur root/tertinggi adalah magma.
yang hanya memiliki postulat clousure.
.
secara umum, variasi-variasi struktur setelah magma hanyalah variasi2 postulat yang dimilikinya. yang menjadi topik yang menarik disini adalah bagaimana menggunakan struktur2 ini untuk membangun matematika aksiomatik yang merupakan aljabar di alam.
.
#TUJUAN PRINSIP DARI KONSTRUKSI IDE STRUKTUR ALJABAR:
yaitu adalah usaha untuk mengidentifikasi semua struktur aljabar abstrak yang mungkin, yaitu semua struktur yang dibangun dari sebuah atau lebih set dengan sebuah atau beberapa operasi di dalamnya.
.
#BENTUK UMUM STRUKTUR ALJABAR:
struktur aljabar =<(S1,S2,S3,…,Sn),(O1,O2,O3,…,Om),(P1,P2,P3,…,Pk)>
ditulis lebih lengkap sebagai :
struktur aljabar abstrak =<(S1,S2,S3,…,Sn),(O1,O2,O3,…,Om),(P1,P2,P3,…,Pg)>
dimana :
Si adalah set atau struktur aljabar ke-i
Oj adalah operasi atau operator ke-j
Pk adalah postulat/axiom ke-k
.
#GENERALISASI STRUKTUR ALJABAR:
Oj adalah sebuah n-ary operation.
.
cara konstruksi n-ary operation.
misal Oj adalah n ary operation maka konstruksi Oj:
Oj:(S1,S2,S3,…,Sn)1x(S1,S2,S3,…,Sn)2x…x(S1,S2,S3,…,Sn)g —-> (S1,S2,S3,…,Sn)
.
misal S=(S1,S2,S3,…,Sn)
ditulis singkat:
Oj:SxSxSx…xS —> S
.
secara praktis, ditulis sebagai prefix notation:
Oj(a1,a2,a3,…,am)=a
.
ditulis secara explisit dalam bentuk string:
a1a2a3…an=a
.
#CARA MENERAPKAN SECARA UMUM KE FISIKA, KIMIA, BIOLOGI, BAHASA, KOMPUTER, DSB:
konstruksi praktis:
tulis semua kombinasi string sehingga menghasilkan sebuah himpunan relasi.
misal:
a1a2a3…an=a
a2a1a3…an=b
a3a2a3…an=c
maka terbentuk himpunan relasi R={a1a2a3…an=a,a2a1a3…an=a,a3a2a3…an=a}
sehingga jika hendak menggunakan operasi Oj pada sebuah set, maka seluruh hasil operasi Oj pada set sudah terdaftar pada R, tinggal cari di R lalu temukan hasil operasi itu.
.
secara praktis kita juga dapat menggunakan tabel yang mendaftar seluruh kemungkinan operasi pada Oj di atas set.
jika diterapkan ke fisika:
misal suatu percobaan atau eksperimen, menghasilkan hasil2 percobaan antara beberapa kombinasi partikel yang dapat di representasikan sebagai string, jika semuanya di jadikan plasma, maka diperoleh hasil2 kombinasi dalam sebuah tabel.
tabel yang diperoleh dari eksperimen adalah sebuah tabel operasi Oj.
.
demikian pula pada string2 reaksi kimia, sebuah reaksi kimia direpresentasikan oleh string atom2 yang bereaksi dan juga hasilnya.
tabel dari semua kombinasi string adalah sebuah operasi Oj.
menggunakan operasi Oj adalah berarti menggunakan tabel tersebut.
.
SECARA PRINSIP, PENERAPAN INI MEMILIKI ARTI ADALAH BAGAIMANA CARA MEMBANGUN ALJABAR DI SEGALA TEMPAT DI ALAM SEMESTA VISIBLE, ATAU BAGI KESELURUHAN ALAM SEMESTA SENDIRI.
.
#BAGAIMANA MENGGUNAKAN UNIVERSAL ALJEBRA?
universal aljabar = struktur universal, dimana set nya adalah sebarang set atau struktur algebra dan operasinya adalah sebuah n-ary operation.
n ary operation dalam artian bukan seperti di atas sebelumnya, dimana Oj, operasi yang jika ditulis dalam bentuk prefix Oj(a1,a2,a3,…,an) sebagai n-ary operation seperti di atas.
tetapi n-ary operation disini adalah: (Oj1,Oj2,Oj3,…,Ojg), disana terdapat sebuah operasi yang didefinisikan sebagai tupel.
.
jika ditulis singkat aja sebagai berikut:
Universal algebra =<(S1,S2,S3,…,Sn),(O1,O2,O3,…,Om),(P1,P2,P3,…,Pg)>
dimana:
Si adalah set atau struktur algebra.
Ok adalah sebuah n-ary operasi,ex: O1=(O11,O12,O13,…,O1g),seperti (Oj1,Oj2,Oj3,…,Ojg)
Pj adalah postulat ke-j
.
dengan cara yang sama struktur aljabar untuk diterapkan, kita mungkin dapat membangun alajabr universal sebarang di alam semesta.
dengan membangun tabel operasi seperti di atas untuk suatu eksperimen yang telah dilakukan, atau tabel operasi dipostulatkan sehingga membanun suatu teori yang berbentuk struktur aljabar atau universal algebra.
.
kita mungkin juga bisa melihat penerapan ini pada topology.
dimana kita berusaha membangun universal algebra di atas topologi.
sebagai contoh:
kita memiliki n buah transformasi geometri yang berbeda pada topologi, n buah transformasi itu dapat kita definisikan sebagai n-ary operation pada universal algebra.
kemudian himpunan postulat mungkin dapat dikonstruksikan bagi n-ary operation tersebut.
.
#BISAKAH MEMPERUMUM LAGI UNIVERSAL ALGEBRA?
bisa:
Ok didefinisikan sebagai sebuah tensor rank n dari susunanan operasi2.
.
#BAGIAMANA ORANG MENGGUNAKAN STRUKTUR ALJABAR ATAU UNIVERSAL ALJABAR PADA TOPOLOGI?
mungkin dengan mendefinisikan pemetaan2 geometri transformasi2 di manifold, dsb) sebagai operasi-operasi dari struktur aljabar atau unievrsal aljabar, kemudain ternyata itu dapat digunakan untuk memodelkan atau membangun teori tentang sifat2 atau pola2 geometri dari suatu bagian atau seluruh bagian dari topologi.
.
jika pemetaan2 topologi itu atau transformasi2 geometri itu dirumuskan dari hukum2 fisika, maka dia menjadi penggunan struktur aljabar/universal aljabar ke dalam perumusan teori2 fisika.
.
#SAMPAI DIMANA GENERALISASI UNIVERSAL ALGEBRA SEKARANG?
Category theory, Operad theory, Partial algebra, and Model theory adalah teori2 yang dibangun sebagai beyond atau generalisasi dari universal algebra.
.
demikian pula Lie algebras(?) and hyperbolic quaternions(?), adalah generalisasi universal algebra.
.
——————————————————————————————
#BAGAIMANA MELIHAT BAHWA BAHASA ADALAH SEBUAH UNIVERSAL ALGEBRA?
dengan melihat bahwa setiap aturan produksi pada gramatika adalah sebuah n-ary operation dalam pengertian struktur algebra.
.
dan dengan melihat bahwa himpunan aturan atau gramatika secara keseluruhan adalah sebuah n-ary operation dalam pengertian universal algebra.
.
sehingga suatu gramatika adalah sebuah tabel operasi atau n-ary gramatika dalam pengertian universal algebra.
.
dalam hal ini, wujud operasi dihilangkan, tetapi hanya bentuknya saja yang diambil, misal:
a + b = c menjadi ab -> c atau dibalik sebagai c –> ab
.
sebuah 0 ary operation struktur algebra: c
sebuah 1 ary operation struktur algebra: c –> a
sebuah 2 ary operation struktur algebra: c –> ab
sebuah 3 ary operation struktur algebra: c –> abA
..
sebuah n ary operation struktur algebra: c –> abcdKGmn
dst
.
himpunan {c, d–>a, f–>ab, g–>abA, t–>abcdKGmn} adalah sebuah n-ary operation dalam pengertian universal algebra.
.
kemudain ini diperluas dengan melihat bahwa:
sebuah aturan produksi dalam gramatika adalah equation n-ary operation:
misal:
aAc —> adB
atau bcD —> ab | abH | gf
yang merupakan penulisan singkat dari 3 equation.
dan setrusnya.
.
#ARTI PENTING ALJABAR BAGI BAHASA:
representasi monoid atau magma dalam string dan operasi string, ini memberikan visi yang luas tentang penerapan struktur aljabar secara umum, universal algebra, perluasan universal algebra seperti teori category dan seterusnya ke dalam konsep bahasa.
.
mungkin di masa depan kita dapat menemukan gagasan bahasa yang sophiticated dengan penerapan atau permodelan besar2an struktur aljabar, universal aljabar, dan seterusnya ke dalam bahasa.
.
#ARTI PENTING ALJABAR BAGI KOMPUTASI:
penerapan aljabar ke dalam bahasa, adalah juga berarti penerapan ke pada automata dan mesin turing.
.
ini memberi pandangan bahwa setiap automata atau mesin turing adalah sebuah struktur aljabar, atau universal aljabar atau perluasannya.
.
ini juga memberi visi yang luas bagaimana jika semua konsep aljabar itu diterapkan ke dalam komputasi.
.
#ARTI PENTING ALJABAR BAGI FISIKA, BIOLOGI DAN KIMIA:
masukanya representasi aljabar ke dalam bahasa dan komputasi ini membuka visi yang luas juga bagi penerapan dari pintu masuk yang berbeda kepada fisika, biologi dan kimia.
.
secara umum kepada berbagai bidang ilmu pengetahuan.
.
——————————————————————————————
SURVEI PAPER:
Review:
Principle of Rule-Based Expert System
By: Bruce G. Buchanan and Richard O. Duda
.
Apa prinsip2 Rule based expert system?
.
(1).
Algoritma inferensi sangat berkaitan erat dengan cara representasi rule. Sehingga ketika hendak mmebuat algritma inferensi maka:
Buat postulat ekspresi rule.
.
(2).
Rule memiliki arti yang universal dibanding proposisi.
proposisi adalah null order logic
tetapi rule bisa:
rule = null order logic
rule = first order logic
secara umum:
rule = n order logic.
.
lebih umum lagi:
rule = sebarang bentuk formal.
.
bentuk formal bisa kalimat, graf, instruksi automata/mesin turing, kartu frame, geometri dan sebagainya.
.
(3).
contoh rule dalam bentuk first order logic:
Has(x, feathers) OR (Able(x, fly) & Able(x, lay-eggs)) –> Class(x, bird)
.
kita dapat mengekspresikan rule ke dalam ekspresi operator2 logika pada level n order logic.
.
(4).
karena itu, perbedaan definisi ekspresi rule tentunya menghasilkan algoritma yang berbeda-beda untuk memicu rule.
.
forward chaining mestinya dapat digeneralisir untuk ekpresi rule higher order logic.
.
(5).
secara umum.
forwardchaining hanyalah algoritma.
secara umum kita dapat mengenarlisir kata untuk memicu rule, yaitu algoritma.
algoritma(set rule)=set solusi.
.
set solusi bisa set anteseden, set konsekuen, set antesedn-konsekuen, atau graf anteseden-konsekuen, dan sebagainya.
.
(6).
Secara umum bentuk rule dapat ditulis sebagai:
bagian anteseden THEN bagian konklusi.
bagian anteseden = set premis dalam bentuk n order logic atau bentuk formal secara umum
bagian konklusi = set premis/action dalam bentuk n order logic atau bentuk formal lain atau prosedur aksi.
.
dalam cara pandang bentuk umum ini, forward chaining dapat dilihat secara universal.
.
FINISH UNTUK PAPER INI.
——————————————————————————————
——————————————————————————————
——————————————————————————————
#REVIEW:
On Review:A NEW APPROACH TO IMAGE RETRIEVAL USING MULTI-LEVEL GENERALIZED FINITE
AUTOMATA. A. Soliman, M. Moniri and C. Chibelushi, Staffordshire University, UK.
#Bagaimana mereka mengenkoding gambar ke dalam automata?
pertama:
mereka membuat paritisi pada ladang pixel dari gambar.
lalu tiap2 sub ladang dibangun suatu hubungan, mungkin tentang similiarity antar sub ladang.
misal dengan menghitung nilai rata2 suatu fungsi pixel untuk tiap ladang dan selisih antar rata2 mengukur similiaritynya.
.
Tetapi apakah state dan apakah input dalam konsep itu?
.
Sepertinya yang dimaksud dengan state disana adalah state partisi, sebab proses partisi gambar langkah ke langkah berikut dilihat sebagai perubahan state ke state.
misal state1 = konfigurasi partisi1
state2 = konfigurasi partisi2 setelah partisi1
state3 = konfigurasi partisi3 setelah paritsi2 dan seterusnya.
.
apakah input?
sepertinya input menyatakan elemen partisi yang hendak dipartisi lagi.
.
contoh:
misal gambar I.
maka state partisi adalah S0, lalu masuk input I.
maka I kemudian dipartisi dalam 4 bagian, sehingga state partisi menjadi S1. dimana pada S1, I=(I0,I1,I2,I3) yautu terbagai 4 partisi.
kemudian S1 bercabang 4 ke 4 state lain.
jika input I0 maka S1 pindah state ke S10
jika input I1 maka S1 pindah state ke S11
jika input I2 maka S1 pindah state ke S12
jika input I3 maka S1 pindah state ke S13
dan seterusnya.
.
#Mengapa gFSA menjadi lebih minim state jika digunakan?
karena input gFSA bisa menjadi sebuah konfigurasi partisi, bukan saja sebuah partisi.
misal pada FSA, input adalah I0, sebuah pecahan partisi dari seblumnya.
maka gFSA bisa jadi I0I1, dua sub partisi sekaligus, dan seterusnya. sehingga hanya memerlukan lebih sedikit state.
.
#Secara umum apa keuntungan dari gFSA dibanding FSA?
gFSA memerlukan lebih sedikit partisi dibanding FSA dalam suatu pandangan yang global.
jika kita mengenaralisir gFSA menjadi gTM maka sebagai berikut:
gTM memiliki jumlah instruksi yang lebih sedikit dibanding TM standar.
.
#Seberp banyak representasi FSA atau gFSA di atas sebuah image?
adalah sebanyak cara atau path partisi bisa dilakukan di atasnya.
misal partisi dilakukan secara konsentris menghasilkan gFSA1 atau FSA1
atau dilakukan secara linier menghasilkan gFSA2 atau FSA2.
dan seterusnya.
#END REVIEW.
——————————————————————————————
#Bagaimana memodelkan proses bisnis ke dalam automata?
Pertama:
State = proses bisnis X atau subproses bisnis Xi dst
input = data atau dsb.
.
Kedua:
Misalkan sebuah proses bisnis X, state0.
kemudian sebuah data1 masuk, maka state0 berpindah ke state01 yaitu sebuah prosesbisnis01
jika data2 masuk, maka state0 berpindah ke state02 yaitu sebuah prosesbisnis02
.
misalkan data11 masuk saat state01, yaitu prosesbisnis01.
maka state01 berpindah ke state 011 yaitu prosesbisnis011.
dan seterusnya.
.
Ketiga:
Ini bisa kita generalisir ke fungsi. jadi sebagai berikut:
state = fungsi (bisa merupakan koding)
input = data
.
atau kita generalisir ke modul (bisa koding)
state = modul
input = data
.
atau kita generalisir ke program (bisa koding)
state = program atau subprogram
input = data.
.
keempat:
bahkan sebuah strategi politik atau militer dapat kita rumuskan kedalam sebuah automata sbb:
state = kebijakan politik atau perang
input = data
.
Kelima:
kita dapat mengeneralisir permodelan ini ke gFSA atau gTM.
.
Keenam:
dalam kasus citra.
state = prosedur partisi atau fungsi pixel sebarang
input = citra hasil state sebelumnya.
.
Ketujuh:
Kita dapat mengeneralisir ini ke dalam sistem kontrol sebagai berikut:
State = konfigurasi kontrol, orang juga menyebutnya location.
input = data atau hasil konfigurasi kontrol sebelumnya.
.
sehingga sebuah automata mengekspresikan kerja sebuah mesin kontrol dari waktu ke waktu.
.
Kedelapan:
kita dapat mengeneralisir ini untuk memodelkan dinamika partikel sebagi berikut:
state = konfigurasi partikel
input = konfigurasi partikel sebelumnya
dan lain sebagainya kemungkinan.
.
Kesembilan:
#Bagaimana kita mengeneralisir konsep celluar automaton?
Pertama:
Pada dasarnya sebuah celluar automaton dapat direpresentasikan oleh sebuah FSA.
mungkin kita dapat melihatnya sebagai berikut:
state0 = posisi ubin awal pada arah horisontal, ini bisa dilabel sebarang
state1 = posisi ubin berikutnya terhadap posisi ubin pada arah horisontal. ini juga bisa dilabel sebarang.
dan setersunya.
.
atau:
state = konfigurasi posisi ubin
input = posisi ubin sebelumnya di state sebelumnya.
.
cellular automaton ini mmeiliki arah ke bawah dalam membentuk state-statenya (konfigurasi horisontal ubin-ubin selanjutnya) dan state didefinisikan dalam satu langkah horisontal dari ubin-ubin.
atau bahwa ubin-ubin merubah state untuk ubin-ubin terdekat dengan ubin sebelumnya atau lingkungan tetangga ke-1. dan informasi titik ubin adalah tunggal sebagai input.
.
generalisasi 1:
Kita dapat mengeneralisir ini dalam sebarang m arah dan langkah tetangga ke-n.
dan k posisi ubin sebelumnya.
.
generalisasi 2:
kita dapat melihat kebalikan bahwa sebuah cellular automaton (CA) dikonstruksikan oleh sebuah FSA.
berdasatkan ini, kita dapat membuat sebuah generalisasi:
sebuah CA dikonstrusikan oleh sebuah himpunan FSA.
.
generalisasi 3:
sebuah CA digeneralisasikan oleh sebuah set FSA, dimana untuk setiap FSA, inputnya adalah sebuah cluster ubin dalam ketetanggan-n sebarang tertentu, dalam m arah.
.
generalisasi 4:
sebuah CA digeneralisasikan oleh sebuah set FSA, dimana untuk setiap FSA, inputnya adalah sebuah cluster ubin berdimensi-k dalam ruang berdimensi-g dalam ketetanggan-n sebarang tertentu, dalam m arah.
.
generalisasi 5:
sebuah CA digeneralisasikan oleh sebuah set gFSA, dimana untuk setiap gTM, inputnya adalah sebuah cluster ubin berdimensi-k dalam ruang berdimensi-g dalam ketetanggan-n sebarang tertentu, dalam m arah.
.
generalisasi 6:
sebuah CA digeneralisasikan oleh sebuah set gTM, dimana untuk setiap gTM, inputnya adalah sebuah cluster ubin berdimensi-k dalam ruang berdimensi-g dalam ketetanggan-n sebarang tertentu, dalam m arah.
.
generalisasi 7:
sebuah CA digeneralisasikan oleh sebuah set probabilistik-gTM, dimana untuk setiap probabilistik-gTM, inputnya adalah sebuah cluster ubin berdimensi-k dalam ruang berdimensi-g dalam ketetanggan-n sebarang tertentu, dalam m arah.
.
generalisasi 8:
sebuah CA digeneralisasikan oleh sebuah set quantum-gTM, dimana untuk setiap quantum-gTM, inputnya adalah sebuah cluster ubin berdimensi-k dalam ruang berdimensi-g dalam ketetanggan-n sebarang tertentu, dalam m arah.
.
generalisasi 9:
sebuah CA digeneralisasikan oleh sebuah set register machine atau set probabilistik-register machine, dimana untuk setiap set register machine atau set probabilistik-register machine, inputnya adalah sebuah cluster ubin berdimensi-k dalam ruang berdimensi-g dalam ketetanggan-n sebarang tertentu, dalam m arah.
.
generalisasi 10:
sebuah CA digeneralisasikan oleh sebuah set model komputasi atau set probabilistik-model komputasi, dimana untuk setiap set model komputasi atau set probabilistik-model komputasi, inputnya adalah sebuah cluster ubin berdimensi-k dalam ruang berdimensi-g dalam ketetanggan-n sebarang tertentu, dalam m arah.
.
GENERALISASI 11:
sebuah graf network dikonstruksikan oleh sebuah set model komputasi atau set probabilistik-model komputasi, dimana untuk setiap set model komputasi atau set probabilistik-model komputasi, inputnya adalah sebuah cluster node atau pasangan node dan edge berdimensi-k dalam ruang berdimensi-g dalam ketetanggan-n sebarang tertentu, dalam m arah.
.
GENERALISASI 12:
dengan cara generalisasi di atas, kita dapat membawa konsep automata atau mesin turing agau CA ke dalam geometri yaitu topologi. bahkan ke teori bilangan dalam konteks konstruksi bilangan dan sebagainya.
.
#Bagaimana menerjemahkan set FSA atau gFSA atau gTM ke dalam program termasuk UTMnya?
Bismillah:
Pertama:
setiap state X = sebuah fungsi X
dimana:
nama fungsi dinamai menurut nama label state dan input yang boleh diterimanya
tetapi dalam kasus gFSA, nama fungsi adalah label state dan nama bahasa yang diterimanya, sedang di lokasi memory lain tersimpan kamus kata bahasa tersebut.
.
kemudian dalam body fungsi:
fungsi memiliki potongan kode yang melakukan aksi, aksi apa saja.
aksi minimal atau default adalah menulis string yang hendak ditulis di memory internalnya.
memiliki memory internal sebagai tempat menulis hasil aksinya.
.
fungsi menulis nama statenya di memory internalnya.
.
fungsi memiliki memory internal yang mencatat input yang masuk. (jika input lebih dari satu, misal dia gFSA yang menerima string suatu bahasa dan bahasa itu memiliki lebih dari satu string)
.
fungsi memiliki argumen yang menerima masukan input, terutama jika dia menerima suatu bahasa.
.
fungsi memiliki pencabangan if untuk setiap jenis input yang masuk, artinya bahwa:
memetakan setiap input ke aksi yang sesuai.
.
aksi fungsi boleh jadi adalah merubah suatu konfigurasi di memory utama, atau merubah suatu konfigurasi perangkat keras, ataumenjalankan sejumlah rule, dan sebagainya.
.
time atau clock bisa dimiliki oleh fungsi.
dia mencatat clock awal atau akhir dan sebagainya dalam aksi dan melakukan sinkroniasi dengan clock UTM atau progam luar.
.
fungsi ini adalah fungsi API X.
.
Kedua:
sebuah timed-FSA atau timed-gFSA atau timed-gTM ditulis sebagai sebuah himpunan fungsi API yang menggambarkan himpunan state dan inputnya.
.
sehingga jika sebuah UTM hendak mengeksekusi sebuah timed-FSA atau timed-gFSA atau timed-gTM maka dia memanggil kelompok fungsi2 API tersebut lalu mengeksekusinya.
.
Ketiga:
UTM adalah program utama yang mengeksekusi set fungsi API yang merepresentasikan sebuah timed-FSA atau timed-gFSA atau timed-gTM.
dia memiliki sejumlah memory (pita) menggunakan pita2 itu untuk mengatur, mengekskeusi, dan mensikronisasi antar fungsi API.
dia memiliki clock dalam bekerja yang membatasi kerja dia dalam mengeksekusi timed-FSA atau timed-gFSA atau timed-gTM.
clock UTM harus sinkron dengan clock timed-FSA atau timed-gFSA atau timed-gTM.
.
ALHAMDULILLAH, ALLAH MEMBERI PENGETAHUAN DAN MEMUDAHKAN, TAK ADA KEMUDAHAN KECUALI APA YANG DIMUDAHKANNYA.
——————————————————————————————
PEKERJAAN BERIKUT:
Konstruksi timed-gFSA
.
Konstruksi UTM atau timed-UTM untuk timed-gFSA
.
Konstruksi gTM
Konstruksi timed-gTM
Konstruksi UTM atau timed-UTM untuk timed-gTM
.
Konstruksi timed-FSA:
state = state seperti biasa, tetapi boleh ditambahkan suatu invarian (constrain waktu) dalam state.
transisi = input seperti biasa, hanya input simbol biasa tanpa time dari ekspresi stringnya. misal string (a,2)(a,3)(b,4) maka sebagai input hanyalah aab.
Sedang pada label transisi ini ada cosntrain berupa guard dan reset.
.
time pada (a,2)(a,3)(b,4), dipakai ketika dalam ekspresi run.
misal run: <S1,v1>–a/2–><S2,v2>–a/3–><S1,v3>–b/4–><S2,v4>
dimana v menyatakan time valuation yang menghitung guard, invarian, dan timed string, time string itu adalah time pada (a,2)(a,3)(b,4).
.
dengan cara ini kita dapat megkonstruksikan time-gFSA sebagai berikut?
pada graph gFSA, state boleh memiliki invarian, pada label transisi ada guard dan reset.
tetapi pada run dari gFSA,
run: <S1,v1>–aaac/2–><S2,v2>–baada/3–><S1,v3>–bbdb/4–><S2,v4>
dan proses perhitungan time valuation pada dasarnya sama tetapi mungkin juga memperhitungkan time dalam bahasa antar transisi itu.
.
Akan tetapi dalam suatu timed-automata, dapat diberikan lebih dari 1 clock, tetapi sebuah himpunan clock.
Sehingga sebuah time valuation v dapat merupakan sebuah himpunan clock, atau bisa juga kita menyebutnya vektor.
Misal clock {x,y,z}
maka vi bisa kita tulis vi=[x,y,z], atau vi=(x,y,z).
.
Sehingga suatu operasi valuasi v di setiap konfigurasi atau state, adalah operasi terhadap semua clock secara bersamaan atau sinkron.
.
Sebuah timed-gFSA dapat memiliki arti sebagai sebuah timed-automaton yang memiliki n buah clock, dan valuasi adalah sebuah vektor clock yang dioperasikan secara sinkron.
Operasi guard dan reset dalam suatu transisi atau invarian, dapat terjadi untuk k buah clock, dimana k=<n.
.
Definisikan run untuk timed-gFSA, dan demonstrasikan sebuah run di dalamnya.
Tetapi apakah arti jika bahasa yang ada dalam transisi adalah timed-L?
mulai dengan kasus sederhana:
(w,t)=(a,t1)(b,t2)(c,t3) dimana t1=t2=t3=t
.
Sekarang pertanyaanya adalah bagaimana mendemosntrasikan run untuk timed-gFSA?
.
——————————————————————————————
#REVIEW:
Fundamental Study A theory of timed automata*
Rajeev Ah-** and David L. Dill***
.
(1).
#Mengapa Rajeev menamakan timed transition table untuk gagasan fundamentalnya tentang timed-automata?
Ini karena bahwa selain sebuah timed transition table dapat dinyatakan dalam sebuah graph.
Pada hakikatnya dapat juga dinyatakan dalam sebuah tabel transisi.
.
Sebuah tabel transisi:
nama-nama kolom tabel adalah sebuah 5-tuple <s, s’,a, lambda, delta>
dan nama-nama vertikal sebagai nama-nama baris adalah state-state.
.
(2).
time valuation = clock interpretation atau some clocks interperation.
.
tetapi mengapa ada operasi aritmetik dasar, v+t dan t.v untuk interpretasi ini?
.
Penjelasna sebenarnya sebagai berikut:
sebenarnya Rajeev membangun konsep clock interpretation.
v adalah clock interpretation yang memetakan setiap clock ke bilangan ril.
akan tetapi jumlahan (misal v+t) atau perkalian secara aritmetik (misal t.v) terhadap waktu maka itu juga adalah clock interpretation.
yaitu:
misal v(x) |-> c interpretasi x yaitu v memetakan x ke c, maka v(x)+t atau t.v(x) adalah juga interpretasi x.
.
(3).
dikatakan bahwa v memenuhi konstrain delta jika hanya jika constrain delta adalah true jika mengunakan nilai waktu yang diberikan oleh v.
.
(6).
#Bagaimana kita melihat sifat general dari gagasan Rajeev tentang timed automata?
#Kuatkah landasan matematika dari “menggunakan framework timed-automata dari Rajeev” untuk merumuskn timed-gFSA?
Pertama:
Term “timed-automata”, sepertinya dimaksudkan untuk seluruh jenis graph automata. Tidak terbatas pada FSA.
Ini berarti Rajeev mengemukakan konsep ini secara general untuk seluruh jenis automata, baik itu FSA, PDA, LBA atau automata dari mesin turing.
Bahkan untuk automata nondeterministik, probabilistik, fuzzy dan kuantum.
.
Ini dapat dimengerti mengapa ada orang menggunakan paper Rajeev ini untuk menganalisa real time system menggunakan PDA.
.
Tetapi orang mengemukakan cara yang berbeda-beda untuk menganalisa reachability dari timed automata ini, misal reachability timed-automata untuk FSA, reachability untuk timed automata PDA, dan sebagainya. Masing-masing orang itu mengemukakan konsep region automaton yang berbeda bahkan berbeda dari yang diusulkan Rajeev, untuk menganalisa sifat reachability dari timed automata yang mereka buat.
.
Ini memberikan alasan matematika yang kuat bahwa timed-gFSA dapat dirumuskan dalam cara Rajeev, dengan melihat bahwa framework yang diusulkan Rajeev ini berlaku untuk seluruh jenis timed automata.
Artinya bahwa kita cukup menggunakan framework itu untuk merumuskan timed-gFSA
.
#Item-item formal apa yang disiapkan oleh Rajeev untuk membangun gagasan timed automata?
Pertama:
Item0: Ada sebuah himpunan clock X, dimana untuk setiap x elemen X maka x adalah clock dalam timed automata.
Ingat ini bukan clock dalam string input.
String input memiliki masing-masing time sendiri, yang bukan merupakan time dari timed automata.
.
Item1: Clock constrain, Rajeev mengemukakan sintaks formula dasar untuk constrain.
Yaitu:
d sebuah ekspresi constrain jika hanya jika ekspresi d adalah sebagai berikut:
d = true | false | x=<c | c=<x | d | d1 dan d2
.
Item2: Time valuation atau clock interpretation.
misal v adalah clock interpretartion dari x elemen X himpunan clock.
maka v memetakan x ke nilai rill.
sintaks dari clock interpretation x adalah sebagai berikut:
v = v(x) | v+t | t.v | [Y->t]v
.
Item2: Definisi formal Timed transition table, formalisme ini sepertinya bertumpu pada bentuk FSA. Kita mungkin dapat memperluas ini untuk sebarang bentuk untuk PDA, LBA, TM, UTM, gFSA.
.
Item3: Definisi run untuk timed automata. Konstruks definisi run juga untuk timed-gFSA.
.
#Apakah sebenarnya arti filosofis dan sekaligus praktis dari konsep time valuation atau clock interpretation dari Rajeev?
Time valuation v = nilai clock pada suatu state ketika terjadi run.
Ini memberikan suatu imajinasi bahwa himpunan clock itu berubah-ubah dari state ke state ketika terjadi run, dan nilai-nilai perubahan itu adalah time valuastion v atau clock interpretation v.
.
#Bagaimana kita melihat konsep timed transition tables adalah sebuah himpunan rekord semata atau sebuah tabel semata sebagaimana dalam konsep basisdata. Sebuah pandangan yang berbeda dengan konsep tabel transisi state yang biasa dimana nama2 kolom adalah iput dan nama-nama baris adalah state?
Pertama:
Kita pada dasarnya dapat melihat gagasan timed transition tables sebagai benar-benar tabel biasa dalam konsep basis data, sehingga sebuah tabel (timed transition tables) adalah benar-benar tabel memodelkan sebuah sistem, sebuah real time system, sebuah timed automata, tetapi juga sebuah graph automata.
.
Kedua:
Sebuah timed transition tables pada dasarnya diekspresikan oleh Rajeev sebagai:
tabel ini dinamai sebagai 5-tupel yatu <Sigma, S, S0, C, E> dimana
Sigma adalah finite alphabet
S adalah finite state
S0 subset S
C adalah finite set dari clock
E adalah himpunan relasi 5-tupel yaitu E subset SxSxSigmax2^cxSetConstrain
yaitu <s,s’,@i,lambda,delta>
.
Rekord = transisi
Rekord = <s,s’,@i,lambda,delta>
Tabel transisi = Himpunan rekord = Himpunan transisi = Himpunan <s,s’,@i,lambda,delta>
.
Ketiga:
Jadi berdasarkan pandangan ini, sebuah timed automata hanyalah sebuah himpunan rekord transisi.
Himpunan rekord ini menyatakan mekanisme timed automata secara lengkap.
.
Keempat:
dengan pandangan yang sama kita dapat merumuskan suatu generaliasi pandangan:
Automata = himpunan rekord transisi.
timed-Automata = himpunan rekord timed-transisi.
FSA = himpunan rekord transisi FSA
gFSA = himpunan rekord transisi gFSA
PDA = himpunan rekord transisi PDA
LBA = himpunan rekord transisi LBA
TM = himpunan rekord transisi TM
.
kita dapat melihat seluruh automata itu sebagai himpunan rekord semata, atau seluruh mesin itu sebagai himpunan rekord semata.
Ini memberi pandangan yang berbeda bahwa automata atau mesin adalah himpunan instruksi.
.
Hasil ini dapat kita generalisir lagi sebagai:
Sebarang model komputasi hanyalah himpunan rekord transisi semata.
.
Kelima:
#IDE:
Kita dapat melihat bahwa sebuah himpunan mesin atau himpunan automata dapat dimodelkan sebagai sebuah model data, dan kemudian dapat kita rumuskan sebagai sebuah basisdata dimana padanya mungkin dapat kita konstruksikan gagasan relasional antar mesin.
.
Contoh konstruksi basisdata yang memodelkan sebuah himpunan mesin:
Ada tabel transisi untuk mesin 1
Ada tabel transisi untuk mesin 2
Ada tabel clock untuk semua mesin
Ada tabel constrain untuk semua mesin
Ada tabel state
Ada tabel input
Dan sebagainya.
.
Kita mungkin dapat menggunakan gagasan relasional dalam basisdata untuk membangun sejumlah mesin yang bekerjasama secara relasional.
.
Kita dapat membangun suatu definisi sebagai berikut:
DU buah mesin bekerja secara bersama-sama relasional jika hanya jika terdapat hubungan relasional antar keduanya sebagai hubungan relasional dua buah tabel.
.
Kita juga mungkin dapat mendefinisikan bahwa:
Sebuah run dalam basisdata ini adalah sebuah query terhadap sebuah mesin atau sejumlah mesin.
#END IDE.
.
(5).
#Apa arti ekspresi time valuation v yang ditulis RAjeev sebagai [yi->0](vi+t.i+1-t.i)
v adalah [yi->0](vi+t.i+1-t.i)
yaitu sebagai berikut:
Semua clock yang tidak mendapat constrain atau tidak disebut dalam constrain adalah direset ke 0, sedang yang mendapat constrain tapi juga mendapat reset maka tetp direset, sedang yang constrain dan tidak reset maka dihitung menggunakan (vi+t.i+1-t.i).
Sedang v adalah clock interpretation untuk semua clock dalam timed automata.
.
(5a).
#Apa arti ekspresi time valuation v yang ditulis RAjeev sebagai [yi->0](vi+t.i+1-t.i)?
[yi->0](vi+t.i+1-t.i) memiliki arti sebagai berikut:
pada awal run, semua clock direset ke 0 pada state awal. yaitu [yi->0].
.
kemudian pada state berikutnya ketika run berjalan clock berjalan menjadi (vi+t.i+1-t.i).
.
setelah clock berjalan atau diinterpretasikan sebagai (vi+t.i+1-t.i), maka dilakukan evaluasi yaitu bahwa hasil interpretasi (vi+t.i+1-t.i) harus memenuhi atau konsisten dengan constrain (invarian dan guard) dan reset.
.
Selama (vi+t.i+1-t.i) berada dalam invarian atau guard maka dia tetap pada hitungan (vi+t.i+1-t.i). Jika berbeda maka yang diambil adalah nilai minimum atau maksimum (vi+t.i+1-t.i) yang memenuhi guard atau invarian.
Jika dia terkena reset maka nilai yang diperoleh dari (vi+t.i+1-t.i) harus direset.
.
Sebuah baris clock yang dinterpretasikan dalam suatu run, state ke state misal ada 2 clock yaitu clock y1 dan y2:
[0,0] -> [2,3] -> [4,5] -> ….-> [0,3] dst
ini disimbolkan sebagai berikut:
[yj->0] –> [vj1 + t1-t0] –> dst
Lalu ditulis saja:
[yi->0](vi + t.i-t.i-1)
.

(6).
#Apa yang dimaksud dengan nested looping pada graph automata?
pertama:
Secara sederhana, sebuah nested looping pada graph automata adalah sebuah state dengan transisi ke dirinya sendiri.
.
Kedua:
Secara umum, sebuah nested looping dalam graph automata adalah sebuah path transisi atau run dalam automata yang membentuk siklus transisi.
jadi misal state A memiliki transisi ke B, tetapi pada B terdapat transisi ke A kembali. Maka state A dan B membangun suatu nested looping.
.
Ketiga:
Kompleksitas sebuah nested looping yang tidak bercabang dalam dirinya atau maksimal ada 1 nested looping lagi dalam dirinya, misal ada n looping tersarang ke dalam dirinya, maka komlpleksitasnya adalah O(x^n), jika terdapat pencabangan looping dalam dirinya sehingga terdapat lebih dari satu nested looping dalam dirinya maka kompleksitasnya adalah logaritmik.
.
Keempat:
#Bagaimana cara menghitung kompleksitas automata (FSA dsb)?
dengan menganalisa jumlah nested looping dalam dirinya dan pencabangan dan sebagainya.
misal terdapat nested1 dengan kompleksitas x^3 lalu disebelahnya ada nested2 lain dengan komlleksitas x^2 lalu berikutnya ada transisi dengan kompleksitas x lalu 3 buah transisi unik ke yang lain maka FSA ini memiliki kompleksitas O(x^3 + x^2 + x + 3).
.
#Bagaima cara menghitung kompleksitas dalam mesin turing atau UTM?
Akan tetapi jika kita mensimulasikan FSA ini atau sebarang automaton ke sebuah UTM, maka kompleksitas ruang dan time bisa dihitung dalam cara mesin turing.
Cara hitung kompleksitas dalam mesin turing adalah sebagai berikut:
jika sebuah automata dapat diselesiakan dalam satu pita maka dia polinomial
jika bercabang dalam 2 pita atau 3 pita atau n pita secara sekali maka dia logaritmik.
jika bercabang dalam n pita setersunya untuk setiap pecahan bercabang m lagi maka kompleksitasnya adalah eksponensial.
jika pencabangan itu bersifat nondeterministik maka itu berrati dia nondeterministik polinomial.
.
SELANJUTNYA BEBERAPA HAL RUMIT TENTANG TIMED AUTOMATA DARI RAJEEV?
Apakah yang dia maksud dengan language?
Mengapa dia menggunakan TBA untuk mendefinisikan language?
mengapa bukan FSA saja?
Apa kelebihan TBA?
Apa kelebihan TMA?
Tinjau mulai dari awal lagi:
(1).
Modal logics and w-automata for qualitative temporal reasoning about concurrent
systems have been studied in great detail.
.
Ini menggambarkan latar belakang gagasan timed automata dari Rajeev.
Latar belakang gagasan timed automata = Modal logics and w-automata for qualitative temporal reasoning about concurrent systems.
.
#Tentang mengapa di timed?
ini mestinya berkaitan dengan term “temporal” sebagai bentuk penalaran dalam memahami concurrent system.
.
#Tentang mengapa dia menggunakan language L yang infinite?
L infinite yang diamksud adalah language L yang setiap stringnya adalah memiliki panjang infinite.
.
#Mengapa string L harus infinite?
Ini berkiitan dengan penalaran temporal.
Penalaran temporal = modal logic yang dikonstruksikan bersama term waktu untuk suatu penalaran yang runtun waktu.
tetapi waktu itu infinite ke depan.
Dalam hal ini, Rajeev harus memandang sebuah real time system yang mencoba untuk bekerja terus menerus dalam waktu.
Bekerja terus menerus dalam waktu itu berarti menerima input terus menerus dalam waktu.
Menerima input terus menerus dalam waktu itu berarti menerima input string yang panjangnya infinite.
Menerima input yang panjangnya infinite, itu berarti sebuah real time system haruslah dilihat sebagai sebuah w-automaton, yaitu sebuah TBA atau TMA (timed buchi automaton atau timed muller automaton).
Ini menjawab pertanyaan:
#Mengapa Rajeev menggunakan infinite L (regular) dan mengapa TBA atau TMA?
Karena sebuah real time system lebih cocok dimodelkan oleh sebuah TBA atau TMA dengan panjang input infinite yaitu menggunakan bahasa timed-L regular yang infinite.
.
Itulah sebabnya postulat timed menggunakan sifat monoton dan sifat selalu ada t>Nt (sifat terus menerus atau infinite).
.
#Bagaimana kita membawa ide Rajeev ini ke disertasi?
#Apa perbedaan ide timed dalam disertasi dan dalam ide Rajeev ini?
Dalam ide Rajeev:
Gagasan timed ditujukan kepada real time system sebagai mesin yang berputar atau bersiklus atau hidup terus menerus, sehingga mestilah menerima input string yang panjangnya infinite dari suatu bahasa regular yang infinite.
.
Pada disertasi, input adalah suatu yang finite karena diberikan oleh manusia sebagai kata yang panjangnya finite yang diberikan kepada mesin AR. Manusia tidak mungkin memberikan input infinite kepada mesin AR.
Sehingga postulat waktu dari Rajeev dibatasi hanya kepada sifat monoton naik, tidak kepada sifat t>Nt (terus menerus).
Juga dibatasi kepada automata FSA, bukan kepada w-automaton (TBA dan TMA).
ini berarti pengembangan timed-automata disertasi dalam wawasan:
timed-automata untuk FSA, bukan w-automata
timed-automata untuk gFSA, bukan generalized w-automata (timed-gBA dan timed-gMA)
timed-automata untuk gTM, bukan sebuah TM yang automatanya adalah w-automata.
dan UTM pun dibangun untuk timed-FSA, timed-gFSA, timed-gTM, bukan untuk w-automata.
.
Akan tetapi kita dapat menempatkan ide RAjeev ini tentang w-automata pada bagian akhir disertasi sebagai pengembangan gagasan, tetapi bukan dimaksudkan untuk menerima input user sebagai bahasa interaksi. karena bahasa interaksi manusia-mesin pada kenyataanya tidak mungkin infinite (manusia tidak abadi untuk memberi input terus menerus).
.
Konsep timed-L yang dibangun dalam bahasa adalah bukan timed-L yang stringnya infinite. tetapi finite. Tetapi konstruksikan saja bahasa yang finite atau infinite (boleh infinite) dan tak terbatas regular tetapi diseluruh tipe bahasa Chomsky.
.
(2).
Modal logics and w-automata for qualitative temporal reasoning about concurrent
systems have been studied in great detail.
.
#Mengapa Rajeev perlu mengemukakan ide timed-automata sedang orang telah mengemukakan gagasan yang rinci tentang modal logics dan w-automata untuk qualitative temporal reasoning, dimanakah letak gap nya?
Pertama:
modal logics dan w-auotama yang dikemukakan orang sebelumnya tidak benar-benar menghitung waktu dalam penalarannya, tetapi semata tempo yang qualitatif (qualitative temporal reasoning ).
Kebanyakan digunakan untuk menalar representasi automata yang bukan timed, tetapi dinalar dalam qualitative temporal reasoning .
.
Rajeev mengemukakan gagasan yang stright pada gagasan waktu dalam arti yang quantitatif, sebagai hitungan bilangan waktu.
Yaitu dengan memperkenalkan bahasa yang timed dan automata yang timed.
kemudian orang boleh membangun gagasan yang analogi qualitative temporal reasoning diatasnya. Yaitu dengan membangun modal logics dan w-automata diatas konsep timed language dan timed-automata.
.
Lebih gamblang yaitu:
Rajeev menerapkan gagasan timed-language dan timed-automata kepada w-automata.
Lalu kemudian siap dinalar menggunakan modal logic baik dalam arah linier time atau tree dsb.
.
#Penjelasan yang lebih tentang gap ide sehingga Rajeev terinspirasi mengemukakan ide timed automata:
Pertama:
Dimasa sebelumnya, orang memodelkan sistem dalam berbagai cara (kebanyakan mungkin bukan dengan automata, karena automata lebih banyak ditujukan kepada komputasi, sedang sistem secara umum pengertiannya tidak ditujukan sebagai mesin komputasi atau komputer, tetapi secara umum, mesin disebut sebagai sistem kontrol atau sistem saja atau real time system aja).
.
Akan tetapi setiap sistem itu jika bekerja maka dikatakan mengeksekusi input yang diberikan kepada sistem.
.
Secara umum, perilaku sistem secara umum hanyalah kumpulan eksekusi input sepanjang waktu.
eksekusi = run = trace atau jejak jalannya mesin.
.
Secara umum:
sistem = himpunan trace eksekusi.
.
akan tetapi untai trace eksekusi menghasilkan untai input yang sepadan sehingga secara hakiki, setiap sistem (sistem kontrol) menghasilakan himpunan string.
Ini berarti setiap sistem adalah sepadan dengan sebuah language atau bahasa.
Jika sistem dianggap bekerja terus menerus sehingga dianggap menghasilkan string yang panjangnya tak hingga, maka languag L yang dihasilkan sistem adalah infinite L (L dengan string2 yang infinite).
Tetapi boleh juga sistem menghasilkan bahasa yang finite.
.
Tetapi, karena sistem kontrol sepadang dengan sebuah bahasa L, maka masuk akal bahwa spesifikasi dan verifikasi sistem kontrol pada sistem kontrol adalah ekivalen dengan spesifikasi dan verifikasi terhadap bahasa L.
Kan tetapi spesifikasi dan verifikasi terhadap bahasa L adalah dengan menggunakan automata.
Sehingga spesifikasi dan verifikasi sistem kontrol dapat secara ekivalen dilakukan dengan menggunakan semata automata.
Ini adalah pandangan yang berbeda dimana orang-orang sebelumnya menggunakan modal logic dan w-automata untuk spesifikasi dan verifikasi secara langsung ke sistem kontrol.
.
(3).
#Apakah sebenarnya pengertian model dalam model checking?
Model dalam model checking adalah:
sistem = himpunan trace eksekusi.
model adalah graph dari trace eksekusi itu.
.
Sehingga model checking adalah checking terhadap trace eksekusi tersebut.
.
Persoalan dasarnya mungkin adalah sebagai berikut:
Bagaimana memeriksa reachability setiap node dalam graph model?
.
Orang-orang sebelumnya melakukannya dengan merambatkan pernyataan modal logic didalamnya, sehingga true dan false setiap node dapat ditinjau.
.
tetapi Konsep Rajeev menggunakan timed-automata, dia tidak perlu merambatkan pernyataan modal logika pada trace tersebut. tetapi cukup memeriksa sifat reachability dari timed-automatanya maka itu sepdaan dengan tinjauan reachbility pada model trace.
.
#Bagaimana konsep model dalam gagasan Rajeev dibanding konsep model checking?
model dalam model checking adalah graph himpunan trace, dan reachbility untuk tiap node dalam graph diperiksa dengan modal logic.
.
tetapi model itu pada dasarnya adalah sebuah bahasa L, sedang bahasa L dapat direpresentasikan oleh automata.
maka model dalam model checking dapat direpresentasikan oleh automata, sehingga segala tinjauan reachbility pada graph eksekusi (model) adalah sepadan dengan tinjauan reachbility pada automata.
.
Kemudian jika model merepresentasikan perilaku sebuah sistem yang finite-state pada trace eksekusinya, maka automata yang sepadan dengan model adalah finite state automata (FSA).
.
Kemudian jika model merepresentasikan perilaku sistem yang infinite-state pada trace eksekusinya, maka orang menggunakan w-automata.
.
Kemudian jika model merepresentasikan perilaku sistem yang real time, maka Rajeev menggunakan timed-automata.
.
#Bagaimana kita meringkas cara verifikasi sistem menggunakan timed-automata?
Sebuah sistem kontrol K hendak diverifikasi.
Konstruksikan bahasa L yang menghimpun seluruh trace eksekusi K.
Buat timed-automata tM yang menerima L.
Periksa reachbility tM dengan cara membuat region automaton tM.
Periksa recahbility region automaton tM.
Selesai.
.
#Dimana letak perbedaan penggunaan timed-automata dalam paper Rajeev dengan penggunaan timed-automata pada disertasi?
timed-automata pada Rajeev digunakan untuk melakukan verifikasi sistem kontrol atau sebarang sistem.
.
timed-automata pada disertasi digunakan untuk interpreter atau compiler bagi bahasa interaksi.
.
#Mengapa dalam konsep verifikasi dan konsep Rajeev adalah penting meninjau tentang kelas-kelas bahasa?
Ini karena setiap model (set trace eksekusi) dari sistem kontrol atau sistem secara umum dipandang sebagai suatu bahasa.
Sehingga analisis model menjadi semata analisis bahasa.
Analisis bahasa tentunya meliputi:
Emptiness sebuah bahasa L (apakah bahasa ini kosong atau tidak?)
Kelas-kelas bahasa atau dikelas mana suatu bahasa (yang juga berarti dikelas mana suatu model atau sistem kontrol)
Kelas dibuat berdasarkan jenis automata yang menerimanya sehingga dengan mengetahui kelas maka automata ekivalennya lebih mudah untuk dikonstruksikan.
Kompleksitas komputasi dari model adalah dengan menghitung kompleksitas dari automata ekivalen yang menerima bahasa representasi model.
.
#Mengapa mereka fokus menyelidiki w-regular languages?
Karena dari semua penelitian-penelitian mereka, pada umumnya mungkin seluruh bahasa yang dihasilkan oleh sebuah sistem kontrol atau representasi model adalah termasuk dalam kelas w-regular language.
w-regular language dapat diterima oleh suatu TBA atau TMA.
Itulah sebabanya teori-teori verifikasi berkembang dalam arah eksplorasi kelas bahasa w-regular language.
.
Itulah juga sebabnya Rajeev menerapkan gagasan timed-automata di atas w-regular language dan w-automata (TBA dan TMA).
.
#Bagaimana rumusan dasar Rajeev pada paper ini dalam mengemukakan gagasan timed-automata?
Yaitu sebuah framework teori timed-automata yang dibangun diatas w-language (infinite string) dan w-automata.
disingkat:
timed-w-language (timed-w-L)
timed-BA (TBA) dan timed-MA (TMA)
.
Disini tampak jelas bahwa framework timed-automata ditujukan kepada kelas bahasa w-regular language, sebagai trend dalam penelitian, mungkin trend dalam penelitian model checking.
.
Yaitu framework timed automata ditujukan untuk memverifikasi model (set trace eksekusi) yang membangun w-regular language.
.
(4).
Although the decision to abstract away from quantitative time has had many
advantages, it is ultimately counterproductive when reasoning about systems that
must interact with physical processes; the correct functioning of the control system of
airplanes and toasters depends crucially upon real-time considerations.
.
Ini menunjukkan sebuah gap dimasa sebelumnya bahwa konsep time dalam sistem kontrol tidak terlalu bagus jika sistem kontrol itu berinteraksi secara real time dengan yang lain. Yaitu bahwa konsep time itu hanya ditujukan banyak kepada sistem kontrol yang bekerja sendiri dalam waktu.
.
We would like to be able to specify and verify models of real-time systems as easily as qualitative models.
.
Tetapi telah ada yang meninju model yang real time yaitu menggunakan qualitative mode (modal logic).
.
Our goal is to modify finite automata for this task and develop a theory of timed finite automata, similar in spirit to the theory of o-regular languages. We believe that this should be the first step in building theories for the real-time verification problem.
.
Rajeev menawarkan quantitative mode untuk real time system, dan membawanya atau menggunakannya juga kepada analisis w-regular language.
.
(5).
For simplicity, we discuss models that consider executions to be infinite sequences
of events, not states (the theory with state-based models differs only in details). Within
this framework, it is possible to add timing to an execution trace by pairing it with
a sequence of times, where the ith element of the time sequence gives the time of
occurrence of the ith event. At this point, however, a fundamental question arises:
what is the nature of time?
.
#Apa langkah filosofis pertama dari Rajeev dalam mengkonstrusikan teorinya?
Tentunya kembali pada dasar permasalahan atau dasar problem solving. Dasar problem solvingnya adalah:
Memebangun analisis real time pada model maka itu berarti membangun timing pada model, sehingga pertanyaan awal bisa dirumuskan sebagai berikut:
“Bagaimana memberi timing pada setiap trace dalam model?”
.
Rajeev pertama kali merumuskan trace sebagai:
consider executions to be infinite sequences of events, not states (the theory with state-based models differs only in details).
Yaitu bahwa:
executions = infinite sequences of events, bukan infinite sequences of states.
perbedaanya sebagai berikut:
event = tupel dari state dan timing, jadi node dari pada trace adalah sebuah 2-tupel yaitu <state,time>.
dikatakan event atau peristiwa karena ada waktu, waktu secara filosofis menyatakan peristiwa.
timed disini adalah nilai (interpretasi waktu) dari semua clock yang ada dalam sistem (automata).
secara umum, dalam konsep infinite sequences of events, yaitu run sebagai event to event atau peristiwa ke peristiwa.
.
jika dikatakan infinite sequences of states, itu berati run sebagai state to state.
.
#Apa perbedaan konsep run Rajeev dengan konsep run model checking sebelumnya?
Lihat paragraf di atas sebelumnya, disinilah perbedaan kosep run dari Rajeev dengan konsep run pada konsep modal logic pada model checking sebelumnya.
.
(6).
When the systems are finite-state, as many are, we can use finite automata, leading to effective constructions and decision procedures for automatically manipulating and analyzing system behavior.
.
#Pertanyaan 1:
Bagaimanakah sebenarnya mereka menggunakan finite state automata untuk for automatically manipulating and analyzing system behavior?
Apakah yang dimaksud dengan memanipulasi system behaviour?
Apakah itu berarti memanipulasi trace?
Menambah atau mengurangi input? itu berarti memanipulasi bahasa L (representasi model)?
Menambah atau mengurangi state? itu berarti memanipulasi automata?
Secara umum mestilah berarti memanipulasi automata representasinya, yang bisa merujuk juga kepada perubahan bahasa L nya.
.
analyzing system behavior?
Adalah berarti memeriksa reachabilitynya.
dan kompleksitas langkah-langkah kerja sistem, apakah dia bisa menyelesaikan suatu pekerjaan dalam kompleksitas PSPACE atau tidak?
.
eading to effective constructions and decision procedures?
Itu berarti bahwa langkah2 manipulasi itu disusun dalam suatu tata cara konstruksi dan prosedur decision yang effectif (dalam suatu langkah2 yang algoritmik, suatu meta-algoritma).
.
(7).
The universal acceptance of finite automata as the canonical model of finite-state computation can be attributed to the robustness of the model and to the appeal of its theory.
In particular, a variety of competing formalisms – nondeterministic Biichi automata,
deterministic and nondeterministic Muller automata, w-regular expressions, modal
formulas of (extended) temporal logic, and second-order formulas of the monadic
theory of one successor (SlS)- have the same expressiveness, and define the class of
w-regular languages.
.
Bagian ini menjelaskan bahwa FSA yang merupakan model kanonik (konsisten) dari finite-state computation mencukupi untuk melakukan verifikasi dan spesifikasi model.
.
Tetapi terdapat beberapa formalisma yang mirip yang berkompetisi yaitu:
nondeterministic Biichi automata, deterministic and nondeterministic Muller automata, w-regular expressions, modal formulas of (extended) temporal logic, and second-order formulas of the monadic theory of one successor (SlS).
.
Secara sederhana formalisma2 ini pada ujungnya membangun suatu kelas bahasa yang sama. Yaitu kelas bahasa w-regular language.
.
Itulah sebabnya orang banyak mendasarkan teori verifikasinya pada kelas bahasa w-regular language, sebagai bentuk sepadan dari teori-teori sebelumnya.
.
Ini dapat kita pahmi sebagai berikut, misal:
nondeterministic Biichi automata (NBA), deterministic and nondeterministic Muller automata (DMA dan NMA), w-regular expressions (w-regex), modal formulas of (extended) temporal logic (TL), and second-order formulas of the monadic theory of one successor (SlS).
Maka jika secara berturut-turut mereka membangun bahasa L(NBA), L(DMA), L(NMA),
L(w-regex), L(TL) dan L(S1S) maka:
{L(NBA), L(DMA), L(NMA), L(w-regex), L(TL), L(S1S)} = kelas w-regular language
.
Ini menyebabkan orang mengeneralisir gagasan verifikasi menjadi sebarang formalisma yang membangun kelas w-regular language.
.
(8).
Modal logics and w-automata for qualitative temporal reasoning about concurrent systems have been studied in great detail.
.
#Modal logics and w-automata for qualitative temporal reasoning?
Ini menjelaskan bahwa konsep modal logics digunakan bersama-sama dengan w-automata untuk membangun qualitative temporal reasoning.
Disini perbedaan w-automata dalam konteks modal logics dengan w-automata dalam konteks quantitatif Rajeev.
Rajeev menggunakan w-automata untuk mengkonstruksikan analisis yang quantitatif (time) terhadap sistem kontrol.
.
(9).
Modal logics and w-automata for qualitative temporal reasoning about concurrent systems have been studied in great detail. These formalisms abstract away from time, retaining only the sequencing of events. In the linear time model, it….
.
Ini memiliki arti bahwa formalisma yang menggunakan modal logics + w-automata telah dikembangkan orang sangat jauh, yang tersisa tampaknya hanya pada bagaimana cara melakukan sequencing of events.
Salah satu cara sequencing of events adalah linier time model.
Rajeev sepertinya menjadikan ini sebagai batasan teorinya. atau tempat awal mula pertumbuhan teorinya. Selanjutnya mungkin bisa dibangun untuk selain linier time model.
.
#Akan tetapi yang menjadi pertanyaan:
Bahasa apakah yang dibangun oleh model jika bukan linier time model?
Tetapi secara umum, mestilah dia membangun suatu bahasa dalam berbagai tipe atau salah satu tipe dari bahasa chomsky.
.
#Mengapa Rajeev secara intrinsik berpendapat bahwa real time systems tidak cukup dianalisa menggunakan qualitatif model atau qualitatif temporal reasoning?
Ini karena term “real time” sudah merujuk kepada nilai rill dari waktu.
Nilai rill waktu adalah quantitatif, bukan qualitatif. Sehingga perlu dibangun FSA atau w-automata yang dilekatkan hitungan quantitatif waktu di dalamnya.
Untuk itulah Rajeev merasa perlu membangun gagasan quantitaif yang disebutnya timed-FSA atau timed-w-automata.
.
Langkah pertama Rajeev dalam menyusun model yang quantitatif adalah dengan mendefinisikan ulang konsep trace yang membangun model yaitu timed-trace.
.
#Bagaimana memperluas gagasan Rajeev untuk diluar linier time model?
Yaitu cukup dengan menggunakan timed-node untuk mengkonstruksikan graph eksekusi.
Graph eksekusi boleh linier, boleh membentuk pohon eksekusi dan sebagainya graph eksekusi. Akan tetapi node nya adalah timed-node.
.
Kemudian mengembangkan time-L yang dibangun diatas timed-grammar untuk seluruh bahasa dalam tipe bahasa dari chomsky.
.
Selanjutnya menjadi pertanyaan penting bagi Rajeev adalah bagaimana merumuskan waktu pada model?
#Bagaimanakah sebenarnya natur atau sifat alami dari waktu?
Rajeev perlu memahami ini karena dia ingin menggunakannya sebagai dasar filosofi untuk membangun postulat dasr waktu bagi model.
Misal natur waktu yang dia postulatkan secara implisit atau eksplisit adalah:
1. Waktu t adalah bilangan rill (t elemen R+)
2. Waktu monoton naik terus menerus.
3. Untuk setiap bialngan asli N yang ditetapkan, selalu ada waktu t dimana t>N.
.
Tredapat 2 model watu yang dirumuskan orang:
discrit time, fictious time dan dense time.
Rajeev memilih dense time karena lebih natural sedang yang lain dengan mudah dapat dimanipulsi, dihilangkan sehingga seakan2 akan sistem tak perlu mempertimbangkan waktu.
Dalam paper ini dijeklaskan bagaimana discrit time dan fictious time dengan mudah dapat dihilangkan dalam trace eksekusi.
.
Untuk iniliha Rajeev membangu teori timed yang diharapkannya lebih natural dan sesuai.
.
(10).
#Pertanyaan 2:
bahasa apakah sebenarnya yang dibangun model?
Maksudnya string apakah yang dia bangun?
Apakah string state?
Ataukah string input?
.
Sepertinya ini string state atau secara umum string events.
Karena string seperti ini menggambarkan dengan jelas behaviour dari sistem, bagaimana events ke events sistem bekerja.
.
(11).
#Mengapa Rajeev terinspirasi mengemukakan ide untime?
Sepertinya ini terbawa dari kebiasaan untuk menghilangkan waktu pada permodelan waktu discret time atau fictious time. Rajeev mencoba mengeneralisir konsep untime pada discret time dan fictious time ke dense time, tetapi dengan cara pandang yang berbeda atau lebih luas.
.
(12).
#Bagaimana overview atau pandangan global dari usulan teori Rajeev?
Pertama:
[1]DASAR GENERALISASI TIMED AUTOMATA: timed automata adalah perluasan w-automata dengan cara memberi w-automata timing.
.
[2]INPUT TIMED AUTOMAT: timed automata menerima timed words (sebelumnya belum pernah ada gagasan tentang automata yang menerima timed words, kecuali hanya sebatas pemberian constrain dalam transisi dan sifat-sifatnya).
.
[3]FISIK TIME AUTOMATA: timed automaton dalah sebuah FSA + finite clocks.
.
[4]SIFAT CLOCK: clock bersifat dapat direset (contoh reset x=0, x adalah clock) dan elapsed time (selisih waktu) adalah terpelihara dalam track atau transisi ke transisi (ii dinyatakan dalam rumus vi + t.i-t.i-1).
Nilai atau interpretasi clock menaati constrain waktu yang ada di tiap transisi (konsep invarian sepertinya tidak dikenal dalam gagasan timed automata, tetapi itu mungkin dengan memodifikasi rumus elapsed time yang mempertimbangkan invarian)
.
[5]TIMED AUTOMATA MENGCAPTURE KONSEP: features such as liveness, fairness, and nondeterminism; and quantitative features such as periodicity, bounded response, and timing delays.
.
[6]SIFAT TRANSISI: transisi bersifat taat constrain waktu.
.
[7]DASAR FORMALISMA: teori timed automata Rajeev adalah formal language theory. Ini memiliki arti bahwa teori Rajeev mengarahkan konstruksi postulat2 dan teorema2 yang koheren dan meniru sifat2 atau teorema2 yang ada dalam formal language theory.
.
[8]CAKUPAN TINJAUAN TEORI: deterministic dan nondeterministic.
.
[9]ACCEPTENCE CRITERIA DARI AUTOMATA: buchi dan muller conditions.
.
[10]SIFAT2 YANG POPULER DIKONSTRUKSIKAN SEBAGAI BAWAAN DARI FORMALISMA LANGUAGE THOERY:
sifat closure, closed, boolena operations, union, interscetion dan emptiness.
.
[11]SIFAT-SIFAT LAIN YANG UMUM UNTUK KOMPUTASI YANG DITURUNKAN:
secara umum adalah sifat-sifat dalam decision problem dan kompleksitas.
.
[12]HASIL PRAKTIS DARI TEORI ADALAH:
algoritma untuk melakukan verifikasi (algoritma yang dibangun diatas pandangan teori timed automata).
algoritma yang digunakan untuk membuktikan correctness suatu finite-state real-time systems sebarang.
.
[13]KONSEP BAWAAN DARI PENELITIAN SEBELUMNYA YANG DIGENERALISIR KE DALAM TEORI:
konsep untime.
konsep ini berasal secara implisit dari berbagai teori yang dikembangkan sebelumnya tetapi menggunakan model waktu discret time atau fictious time. digeneralisir ke dalam konsep dense time. dense time adalah model waktu yang digunakan oleh timed automata.
.
[14]HUBUNGANNYA DENGAN GAGASAN MODAL LOGIC DALAM VERIFIKASI SISTEM SEBELUMNYA:
teori Rajeev adalah perluasan gagasan qualitatif modal logic menjadi gagasan yang qualitatif sekaligus quantitatif dengan menambhakn nilai quantitatif waktu (time) pada trace eksekusi dari model.
.
[15]KETERBATASAN TEORI RAJEEV:
dia hanya membangun teori ini untuk cara pandang linier time model pada model yang dihasilkan oleh suatu finite state real time system.
kita mungkin dapat memperluas teori ini untuk sebarang graph time model.
.
#Apakah qualitatif reasoning dan quantitatif reasoning?
qualitatif reasoning = deduksi yang aturan2nya didasarkan pada aturan2 qualitatif. seperti: rule-rule logika (rule2 dasar yang dibentuk dari modal logic dan sebagainya), spesifikasi-spesifikasi formal yang ditulis secara qualitatif (proposisi2 logika atau ekspresi n-order logic), dan sebagainya.
.
quantitatif reasoning = deduksi yang aturan2 deduksinya didasarkan pada aturan2 quantitatif. misal didasarkan pada ekspresi2 numerik, aritmetika dan sebagainya.
elapsed timed dalam timed automata (vi+t.i-t.i-1) adalah aturan yang merupakan ekspresi aritmetika.
dan rajeev menggunakan ekspresi aritmetika ini untuk menalar trace eksekusi.
.
#Pertanyaan 3:
Dimanakah posisi w-regular language? di awal sebagai input atau diakhir sebagai representasi tarce eksekusi?
Dimanakah posisi w-automata? diawal sebagai representasi sistem kontrol atau sebagai kosntruk padananan dari w-regular languge yang merepresentasikan model?
.

#Dimanakah posisi teori Rajeev diantara teori2 lain (tinjaun related work)?

#END REVIEW.
——————————————————————————————
#REVIEW:
Revisiting Reachability in Timed Automata
Karin Quaas°, Mahsa Shirmohammadi:, James Worrell.
.
(1).
#Pertanyaan1:
Bagaimanakah mereka membangun gagasan untuk menganalisa Reachability suatu timed-automata?
Apa gagasan dasarnya?
.
Pertanyaan tentang Reachability = pertanyaan tentang decideablity.
Reachability = suatu analogi dari halting problem.
.
Halting problem = Apakah dapat diputuskan dengan algoritma/mesin bahwa suatu program akan halting atau tidak untuk input string yang diberikan kepadanya?
Tetapi ini undecideable.
.
Reachability problem = Apakah terdapat suatu algoritma yang dapat memutuskan bahwa setiap state dalam sebuah automata adalah tercapai? [rumusan ini masih belum jelas].
.
(2).
#Apakah binary reachability?
binary reachability = (yes,no) reachability atau (0,1) reachability.
ini mungkin juga memiliki arti bahwa ketika timed automaton diterjemahkan ke region automaton untuk menghitung reachability, tiap-tiap region itu dinyatakan kedalam komninasi biner.
Misal region A = 111001
dan sebagainya.
.
#Apakah region-automaton?
Jika dalam timed-automaton, konfigurasi dinyatakan oleh tupel state dan time, tepatnya time valuation, yaitu <S,v>.
Maka dalam region-automaton, konfigurasi dinyatakan oleh tupel state dan region, tepatnya time region, yaitu <S,[time-region]>
.
.
(3).
#Apakah sebenarnya yang menginspirasi gagasan Rajeev untuk menyusun konsep timed-automata?
yaitu gagasan automata yang merepreesentasikan sebuah sistem kontrol dimana:
state = konfigurasi kontrol
input = output dari konfigurasi kontrol sebelumnya.
kemudian menjadi pertanyaan bagaimana jika konfigurasi kontrol itu bersifat real time atau dikendalikan dalam waktu.
.
(4).
We revisit a fundamental result in real-time verification, namely that the binary reachability relation between configurations of a given timed automaton is definable in linear arithmetic over the integers and reals.
.
Konsep binary reachability = gagasan yang fundamental dalam konsep verifikasi real time.
.
verifikasi real timed = verifikasi terhadap timed-automata.
verifikasi bukan real time = verifikasi terhadap automata
.
Bagaimana mereka memverifikasi automata?
.
#Bagaimana memverifikasi sistem?
Sebarang sistem mungkin dapat direpresentasikan ke dalam automata atau mesin turing.
Sehingga verifikasi terhadap sistem adalah verifikasi terhadap automata atau mesin turing.
Sehingga verifikasi sebuah sistem yang real time adalah verifikasi timed-automata representasinya?
.
#Pertanyaan 2:
Bagaimana mereka menerjemahkan sebuah real time system ke timed-automata?
Atau bagaimana mereka menerjemahkan sistem ke dalam automata?
.
#Bagaimana memverifikasi mesin turing?
Untuk memverifikasi mesin turing, terjemahkan dulu mesin turing ke dalam representasi graph automata atau ekspresi automata, lalu lakukan verifikasi.
.
#Apakah binary reachability relation?
binary reachability relation = untuk suatu reachbility dari suatu konfigurasi ke konfigurasi lain pada dasarnya membangun suatu relasi, sebut relasi itu sebagai relasi reachbility. Jika reachbilitynya dinyatakan secara binary maka disebut sebagai binary reachbility.
.
#Pertanyaan 3:
Bagaimana mereka mengekspresikan binary reachability relation?
Bagaimana ekspresi itu jika dalam bentuk linier arithmatic dari integer dan real?
Bagaimana mereka menggunakan matriks dalam analisis ini?
.
#Bagaimana mengekspresikan automata ke dalam matriks?
Buat :
kepala kolom dari matriks = barisan horisontal state dari automata
nama barisan matriks = kolom vertikal state dari automata
entry matriks = 1 jika terjadi transisi dari nama state baris ke nama state kolom
entry matriks = 0 jika tidak terjadi transisi dari nama state baris ke nama state kolom
atau entry matriks diisi dengan nilai label dari transisi.
.
(5).
Kerangka paper ini:
Memberikan bukti akan : a fundamental result in real-time verification,namely that the binary reachability relation between configurations of a given timed automaton is definable in linear arithmetic over the integers and reals.
.
Pembuktian melibatkan term-term berikut:
the well-known reachability analysis of timed automata involving difference
bound matrices.
Using this new proof, we give an exponentialspace procedure for model checking the reachability fragment of the logic parametric TCTL. Finally we show that the latter
problem is NEXPTIME-hard.
.
(6).
Teorema yang menyatakan suatu argumen bahwa:
the reachability problem for timed automata is The PSPACE-completeness.
Adalah teorema yang menyatakan bahwa timed-automata memiliki kompleksitas yang PSPACE-completeness.
.
This theorem was established by Alur and Dill.
.
tetapi paper ini membangun teorema yang lain menyangkut “binary reachability problem”.
.
(7).
#Pertanyaan 4:
Bagaimana mereka memahami PSPACE-completness?
Bagaimana mereka melihat PSPACE-completness dalam reachability analysis?
Bagaimana juga dengan binary reachability?
.
(8).
Cara pembuktian Alur:
Dia meninjau “reachability between control states (also called locations)”
melihat timed-automata sebagai:
state = control state (location).
.
(9).
Comon and Jurski juga mengemukakan teorema tentang reachbility ini dalam 40 halaman pembuktian. teorema Comon and Jurski adalah:
the reachability relation of a given timed automaton is effectively definable by a formula of first-order linear arithmetic over the reals augmented with a unary predicate denoting the integers. Importantly, this fragment of mixed linear arithmetic has a decidable satisfiability problem, e.g., by translation to S1S.
.
Paper ini pada dasarnya menyederhanakan pembuktian teorema ini (hard karena 40 halaman pembuktian).
But how?
.
(10).
Tebakan cara mereka membuat teorema-teorema itu:
Mereka terlebih dahulu membuat suatu algoritma (mesin turing atau sebarang model komputasi atau hanya program) yang dapat menghitung reachbility.
Kemudian mereka menghitung kompleksitas dari algortima tersebut.
.
(11).
#Apakah flat timed automaton?
timed-automata yang tidak memuat nested loop dalam graphnya.
.
#Pertanyaan 5:
Bagaimana paper ini membuktikan bahwa sebarang timed-automata dapat direpresentasikan oleh sebuah flat timed-automata?
Apakah parametric model checking?
.
#Bagaimana mereka merumuskan algoritma untuk menghitung reachability?
Pertama:
Mereka membangun formula yang menyatakan relasi reachbability antar state (control)
.
Kedua:
mereka membangun algoritma untuk menghitung formula terebut.
.
Algoritma itulah yang dimaksud sebagai penghitung reachability.
.
#Pertanyaan 6:
Bagaimana mereka merumuskan formula untuk reachability antar state/control?
Apa hubungan antara “algoritma untuk menghitung formula reachability” dan “model checking problem”?
Apakah karena algoritma diturunkan menggunakan metode-metode dalam gagasan model checking?
Apakah counter machine?
Bagaimana dia merumuskan region automaton menggunakan counter machine?
.
#Tambahan informasi tentang cara mereka membangun formula untuk reachability atau algoritma:
Yaitu menerjemahkan terlebih dahulu timed-automaton ke region-automaton.
.
#Mengapa dia menggunakan model checking problem?
Penggunaan model checking problem adalah untuk merumuskan formula reachability bagi konfigurasi dalam bentuk parametric model checking, kemudian membangun suatu algoritma yang menghitung bentuk parametric itu. Algoritma itu dibangun dalam metode-metode untuk pemecahan masalah model checking.
.
(12).
Apa hubungan difference constrain dengan reachability relation?
.
yang jelas bahwa difference constrain menyatakan region yang sebenarnya. misal a<t<b, ini suatu constrain tetapi juga menyatakan region.
.
Demikian juga bahwa partisi menyatakan region, yang berarti juga partisi dinyatakan oleh constrain.
.
Tetapi hanya mempertimbangkan bagian pecahan dalam menyatakan region, adalah berarti hanya mempertimbangkan bagian pecahan dari waktu dalam merumuskan constrain.
.
#Mengapa constrain penting?
Karena berdasatkan set constrain ini region automaton dibuat.
.
#Bagaiama paper ini mengekspresikan constrain yang berbeda-beda menggunakan kombinasi boolean?
Berbeda dengan Dang yang menggunakan pattern untuk mengekspresikan constrain2 itu. Sebenarnya ini juga berarti menggunakan pattern atau kombinasi bolean dalam mengidentifikasi atau menamai region-region.
.
#Bagaimana mereka menganalisis constrain?
Constrain pada dasarnya menyatakan region, dan mereka menentukan tipe-tipe constrain yang juga menentukan tipe-tipe region.
.
#Bagaimana mereka menentukan tipe-tipe region?
.

 

#END REVIEW.

 

 

 

 

 

 

 

 

 

Forensik, satelit, drone, tunneling, buffer overflow

Bismillah:
#Bagaimana orang membuat tool2 forensik?
Pertama:
Kumpulkan semua data forensik. Meliputi semua data log di komputer dan semua capture paket data jaringan.

Kedua:
Buat parser yang bekerja pada file2 log, dan buat parser yang bekerja pada paket data.
Parser memiliki requirements utama adalah menerjemahkan tiap item data dalam file log atau sebuah paket data menjadi tiap rekord dengan field2 nya adalah field2 header data.

Dan terakhir juga menerjemahkan payload data, yaitu payload data terakhir yang tidak mengandung lagi header protokol lain.

Ketiga:
Konstruksikan basisdata dengan cara sebagai berikut:
Definisikan tabel2 berdasarkan jenis file log.
Misal tabel untuk log antivirus punya symantec.

Definisikan tabel2 berdasarkan jenis protokol yang terbawa pada paket data.
Sehingga:
Terdapat tabel http, tabel tcp, tabel ip, tabel udp, dan sebagainya jenis protokol dalam seluruh stack tcp/ip, atau jenis platform protokol lain.

Tiap2 tabel protokol, untuk tiap kolom/field tabel adalah menyatakan suatu field header dari header paket data suatu protokol tertentu.

Definisikan tabel khusus untuk memuat payload terakhir, yaitu payload pada paket data yang tidak memuat lagi header protokol lain, atau sudah tidak mengenkapsulasi lagi protokol lain.

Keempat:
Jika basisdata forensik telah dikonstrusikan, maka kita telah memperoleh sebuah data set bahkan mungkin sebuah big data, dikarenakan aliran paket bersifat streaming dan terus menerus.

Kelima:
Konstruksikan datamining di atasnya, atau berbagai tool cerdas buatan atau sistem pendukung keputusan atau tool2 statistik diatasnya.

Keenam:
Tool2 analisis selesai.

Ketujuh:
Seluruh tool dibuat dan digunakan untuk tujuan pemetaan pada model analisis forensik.

Kedelapan:
Model analisis forensik dinyatakan sebagai sebuah tabel dengan kolom2 atau field2 adalah meliputi kolom What, Why, Who, How, When, dan seterusnya jenis peranyaan dasar.
Dapat juga dibuat sebagai kartu-kartu case base reasoning, sehingga tiap2 kartu adalah kartu analsisi forensik.

Dimana dalam satu kartu analisis forensik memiliki anatomi sebagai berikut:
Kepala kartu = berisi pertanyaan2 forensik seperti What, Why, Who, How, When.
Badan kartu = berisi parameter2 yang dibuat sesuai konteks dan dihasilkan oleh tool2 analisis sebelumnya.
Solusi = berisi solusi yang telah diuji kebenarannya.

Selanjutnya kita dapat membangun sebuah sistem cerdas buatan yang lebih besar dengan set pengetahuannya adalah set kartu-kartu analisis forensik. Sehingga dimasa depan mesin forensik dapat digunakan untuk melakukan analisis forensik secara otomatis.
————————————————————————————————
#Masihkah memungkinkan orang menegakkan skema serangan buffer overflow pada program2 sekarang yang mungkin memisahkan antara ruang data dan ruang kode pada memory?
Kenol:
Buffer overflow memiliki arti sebenarnya sebagai buffer atau penampung data atau variabel yang isinya melampaui ukuran yang didefinisikan. Akan tetapi jika alamat memory data menyatu dengan alamat kode maka kelebihan data itu menimpa alamat kode sebagian sehingga boleh jadi kelebihan itu dianggap sebagai kode, sehingga dieksekusi oleh prosesor.

Skema buffer overflow hanyalah salah satu skema injeksi kode. Memanfaatkan kondisi address data dan kode yang menyatu.

Masa sekarang mungkin sulit menemukan program yg menyatukan kode dan data, akan tetapi mungkin banyak atau terjadi pada subrutin atau fungsi atau modul, dimana variabel bersifat lokal dan mungkin ditulis bersama dengan kode, sehingga misalkan subrutin ut login, sangat mungkin skema buffer overflow dapat dijalankan.

Pertama:
Secara global, mungkin bahwa tiap2 aplikasi membagi set data dan set kode pada ruang alamat yang berbeda akan tetapi secara lokal boleh jadi mungkin masih menyatu.

Kedua:
Fungsi atau subrutin, adalah mendefinisikan variabel2nya secara lokal, sehingga boleh jadi bahwa antara kode dan ruang data disatukan dalam unit kode untuk subrutin atau fungsi.

Ketiga:
Sehingga misalkan ada fungsi login, maka mungkin saja data username dan password masih melekat satu dengan kode fungsi, walaupun sekarang orang menempatkan data2 sensitif dalam basisdata yang terpisah dengan kode.

Sehingga boleh jadi orang memasukkan input yang ukuran stringnya lebih panjang dari ukuran yang didefinisikan sehingga boleh saja menimpa kode pada memory.
Dengan demikian skema serangan buffer overflow dapat dilakukan.

Keempat:
Akan tetapi, boleh jadi juga bahwa orang melakukan skema buffer overflow terhadap jaringan dengan memanipulasi jumlah paket data untuk ditegakkan menjadi sebuah frame data yang utuh.

Misalkan sebuah server hanya dapat menerima jumlah data dalam satu ukuran frame data yang ditentukan, akan tetapi seseorang mengirim jumlah paket data yang jika semua paket data dijahit menjadi sebuah frame data, jumlah totalnya ternyata melampaui jumlah data yang dapat ditampung oleh buffer dari server, maka secara otomatis dapat saja terjadi buffer overflow terhadap thread program yang menangani paket data tersebut sehingga terjadi crash, atau boleh jadi pengirim paket mengirim string perintah yang berulang2 jumlahnya banyak sampai melampaui satu ukuran data yang bisa diterima oleh buffer sehingga terjadi penimpaan terhadap kode dari thread yang menangani komunikasi tersebut, sehingga secara otomatis bisa saja terjadi kode2 yang dirim lewat paket data tersebut dieksekusi oleh komputer server.

Server disini adalah berarti komputer yang menerima paket data, itu dapat berarti komputer biasa, smartphone, drone, satelit, robot, perangkat IoT, dan lain sebagainya. Semuanya mungkin bisa dibuat crash dengan skema serangan buffer overflow.

Perang dimasa depan, tentunya mungkin mempertimbangakn serangan2 seperti ini, misalkan sekelompok drone atau robot atau sejumlah satelit atau peluru kendali dibuat runtuh atau crash oleh serangan buffer overflow oleh pihak lawan.
Tenutnya orang mesti mempertimbangkan protokol2 pertahanan yang dapat menangani serangan demikian.
————————————————————————————————
#Bagaimana orang mengenkripsi paket data di internet (misal kasus SSH)?
Pertama:
Paket data = set header-protokol + payload

Kedua:
Tidak ada header protokol yang dienkripsi kecuali payload.
Berdasarkan argumentasi bahwa paket data diharapkan melewati belantara router atau server atau host atau sebarang perangkat tengah di internet dimana mungkin hampir semua perangkat tidak sepaham masalah enkrip-dekrip, atau tidak dapat melakukan dekrip, sedang informasi2 pada header2 protokol digunakan untuk melewatkan paket data melalui mesin2 itu. Sehingga jika terjadi enkrip pada header2 protokol maka suatu tempat di sana ada sejumlah (jika tidak semua) mesin yang tidak dapat meneruskan paket data dikarenakan tidak dapat membaca header2 protokol dari paket data.

Ini berarti jika dirumuskan maka:
Misalkan paket data = header2(payload)
Maka:
Enkripsi(paket data) = Enkripsi(header2(payload)) = header2(Enkripsi(payload))

Rumus ini mungkin berlaku untuk seluruh jenis jaringan di dunia, baik itu jaringan kabel, wifi, satelit, selular, perangkat seperti robot, drone, pesawat terbang dan sebagainya.

Misalkan seseorang yang hendak melakukan intercept terhadap sebuah drone, maka pastilah dia dapat membaca seluruh header paket data yang dikirim ke drone atau keluar dari drone, walaupun tidak untuk payload, misalkan pengembangan protokol untuk komuniksi drone tidak berhati-hati sehingga menempatkan informasi GPS pada header paket data, maka seseorang atau sebuah negara dapat melakukan hacking terhadap drone dengan mengganti nilai GPS pada header paket data sehingga informasi pendaratan drone dapat dimanipulasi menuju pada area pendaratan yang dikehendaki oleh orang yang melakukan intercept.

Konsep ini bahkan mungkin dapat dilakukan terhadap roket-roket kendali jarak jauh yang bertugas membawa peledak2 nuklir antarbenua. Sebuah negara dapat melakukan intercept terhadap komunikasi kendali roket2 tersebut dengan merubah nilai GPS target dari roket2 tersebut.

Demikian pula mungkin dapat kita pahami bagaimana seseorang dapat melakukan intercept terhadap perintah2 yang di kirim ke satelit, dapat saja terjadi, perintah2 yang dikirimkan dilewatkan pada protokol yang tidak melakukan enkripsi terhadap informasi posisi2 satelit diangkasa, atau bahwa informasi2 posisi itu diletakkan pada header paket data dan tidak terenkripsi. Kondisi demikian memungkinkan seseorang yang menangkap paket data di frekuensi satelit yang sama dapat membaca informasi2 posisi satelit kemudian memancarkan ulang ke satelit sehingga menyebabkan perubahan posisi dari satelit tersebut.
Atau boleh jadi seseorang menangkap contoh paket data dari perintah yang dikirim ke satelit, kemudian merekonstruksi paket data serupa untuk digunakan mengendalikan satelit dengan menggunakan kredensial yang diambil pada cuplikan yang ditangkap.

Dan berbagai kemungkinan yang luas (termasuk kepada konsep IoT) dapat dilakukan orang dengan memanipulasi header paket data.

Ketiga:
Akan tetapi, dapat saja terjadi bahwa orang melakukan enkripsi terhadap header2 protokol, hanya saja terbatas kepada informasi2 penting yang tidak digunakan untuk melewatkan paket data di belantara internet atau belantara perangkat.

Konsep ini terjadi dengan melihat bahwa header protokol tertentu, adalah sebuah rekord, karenanya header tebagi dalam beberapa field.
Enkripsi terhadap header hanya terjadi pada satu atau lebih nilai field tetapi tidak untuk semua field.
Sebagai contoh, enkripsi terhadap field cookie pada header http.
Atau seperti contoh sebelumnya di atas, dimana header untuk komunikasi drone menempatkan nilai GPS pendaratan pada header paket data, akan tetapi dia berada pada satu field tertentu dari sejumlah field, dan karenanya dia dienkripsi sendirian tanpa harus mengenkripsi seluruh field header yang lain.

Dalam hal ini, konsep ini dapat dirumuskan sebagai berikut:
Misalkan paket data = header2(payload)
Tetapi header = set of field.
Maka:
Enkripsi(paket data) = Enkripsi(header2(payload))
= Enkripsi(any header but not all, in any field but not all)Enkripsi(payload)

Keempat:
Akan tetapi dapat saja terjadi bahwa orang mengenkripsi seluruh field pada suatu header protokol tertentu, misal seluruh field http terenkripsi termasuk payload nya.
Akan tetapi kasus ini terjadi dengan cara melakukan tunneling suatu protokol di dalam protokol lain, seperti dalam kasus tunneling oleh protokol SSH.
Akan tetapi ini wajib tidak boleh mengenkripsi seluruh header protokol, sebab jika termasuk header network layer, tcp layer, atau data link layer dienkripsi, maka dapat diduga bahwa paket data tidak dapat diteruskan kemana-mana, dikarenakan mungkin tidak ada mesin atau perangkat router di internet yang dapat meneruskan paket data ini dikarenakan tidak dapat mendekrip informasi header IP dan informasi lain.

Jadi, misalkan untuk kasus tunneling oleh protokol SSH, semestinya yang terjadi adalah sebagai berikut:
Header protokol yang dienkripsi hanyalah header protokol dari protokol2 yang selevel dengan protokol SSH (berada dalam stack protokol yang sama dalam standar OSI) atau protokol2 yang berada di atas protokol2 SSH (diatas stack protokol SSH, dalam standar OSI layer), akan tetapi tidak terjadi enkripsi pada semua protokol yang berada di bawah stack protokol SSH, atau mungkin beberapa protokol yang selevel stack SSH.

Kelima:
Secara umum, orang dapat membuat sebuah protokol tunneling atau protokol enkripsi yang terletak di suatu layer pada paradigma OSI, dimana sampai pada layer protokol paling bawah.

Sehingga seluruh protokol yg umum yg terletak diatasnya atau setara dengannya menjadi terenkripsi.
Akan tetapi barangkali tak akan ada mesin umum yang dapat meroute paket datanya kecuali mesin2 khusus yang diinstal aplikasi client/server dari protokol tersebut yg dapat mereroute atau membaca paket datanya, jika benar2 sampai pada layer fisik proses enkripsinya maka mestilah pada mesin2 itu harus terdapat dekoder2 sinyal khusus yg tidak umum untuk mendekode fisik dari sinyal pembawa data.

Sebagaimana contoh yg nyata ini diimplementasikan orang adalah eksistensi akan dark web, yang diimplementasikan dengan protokol2 seperti halnya Tor. Mereka mengenkripsi protokol hingga pada layer TCP atau IP, sehingga nomor IP menjadi terenkripsi.
Tak ada yang dapat membaca paket2 data ini walaupun dia dilemparkan secara broadcast atau juga acak di internet, kecuali komputer2 yang terinstal aplikasi client atau server dari protokol khusus ini.

Mereka memgumpamakan paket data seperi onion (bawang) dimana ketika bawang di route dari tangan ke tangan, tiap2 orang harus mengupas (mendekrip) terlebih dahulu layer demi layer untuk dapat memperoleh isi bawangnya.

Pada kasus ini, sebarang no IP mungkin dapat diganti dengan sebarang string acak, sehingga URL hanya dapat dipahami oleh mesin2 yang menginstal aplikasi client atau server dari protokol khusus tersebut.

Pada logikanya, untuk perangkat2 yang sangat sensitif, barangkali orang2 akan mengembangkan protokol2 yang tidak standar dan keluar dari standar spesifikasi internasional yang disepakati.
Demikian juga untuk enkoder-dekoder sinyalnya, mungkin dibuat berdasarkan spesifikasi yang keluar dari spesifikasi standar, lagi pula, negara mana yang akan membiarkan satelit militernya di hack oleh orang lain hanya karena mengukuti standar spesifikasi internasional untuk mengkonstruksikan teknologinya?

Akan tetapi, walaupun tidak ada orang atau mesin yg memahami protokolnya, mungkin saja seseorang masih dapat melakukan serangan buffer overflow dengan membanjirinya paket data kopian, tanpa harus tau arsitektur paket data bersangkutan, sehingga mungkin saja membuatnya crash.
————————————————————————————————

Group simetri, prosesor, kernel, API dan ABI, fungsi logika

Bismillah:
Group:
#Apakah sebenarnya group simetri sebuah objek X?
Pertama:
Simetri sebuah objek X adalah sebuah transformasi T sebarang, dimana jika kita mengkomposisikan T terhadap X sebanyak n kali maka objek X diperoleh kembali.

Atau dengan kata lain:
Jika X di transformasikan oleh T sebanyak n kali (secara komposisi) maka X mencapai keadaan invarian (X kembali ke X).

Contoh:
T = rotasi 180 derajat.
X (keadaan awal)
T(X)
T(T(X))=X (keadaan akhir)

Maka X invarian dalam transformasi T
Atau X simetri dalam transformasi T
T adalah simetri X

Kedua:
Kumpulkan semua transformasi yang memiliki sifat seperti di atas terhadap objek X.
Maka kumpulan itu membangun sebuah group simetri G khusus untuk X dengan operasi group adalah operasi komposisi.

Sebut G sebagai group simetri X.

Ketiga:
Transformasi T didefinisikan dengan cara sebagai berikut:
Bisa misalkan T = rotasi 20
Atau T = rotasi 20 (rotasi 30)

Dan seterusnya, bisa sebuah transformasi tunggal, bisajuga T didefinisikan sbeagai komposisi sejumlah transformasi yang sama atau berbeda.
————————————————————————————————
#Bagaimana semua teorema2 tentang bilangan (dalam teori bilangan) dapat berlaku secara universal kepada selain bilangan, misal kepada sebarang objek2 di alam semesta, matriks, polinomial, fungsi, tensor dan sebagainya?
Pertama:
Orang melakukan generalisasi thadap aritmetika.
Generalisasi aritmetika menjadi apa yang disebut sebagai ring.

Kedua:
Arti dari generalisasi ini adalah bahwa objek dari aritmetika, yaitu bilangan, berubah menjadi sebarang objek, misal matriks, polinom, fungsi, sebarang objek dimalam semsta, dan sebagainya.
Yang lain bahwa operasi penjumlahan dan operasi perkalian digerenalisasi menjadi sebarang operasi yang sifatnya sama dengan operasi penjumlahan dan perkalian.
Yang lain bahwa :
Segala teorema bilangan menjadi berlaku pula bagi sebarang objek di alam semeta yang memenuhi postulat2 dasar Ring.

Ketiga:
Selesai.
————————————————————————————————
#Bagaimana kita memahami arti penting eksistensi dari monoid, group, filed, ring, dan sebagaianya struktur aljabar?
Pertama:
Kiat dapat melihat kesleuruhan struktur aljabar tersebut hanyalah sebuah ruang atau semesta yang berisi butir2 yang mematuhi sebuan struktur (law, atau hukum2).

Kedua:
Hukum2 tersebut adalah serupa atau generalisasi dari hukum2 aljabar yang sederhana seperti jumlah dan perkalian.

Ketiga:
Mereka hanyalah sebuah ruang atau semesta dengan butir2 yang mematuhi hukum2 aljabar yang telah digeneralisir, karenanya, sebagai arti penting bagi eksistensi mereka, adalah bahwa kita dapat membangun objek2 matematika baru di atasnya dengan memanfaatkan butiran2 itu dan memanfaatkan hukum2 yang mendasarinya.

Keempat:
Yang berarti juga bahwa kita dapat membangun sistem matematika baru di atasnya.

Kelima:
Secara umum, arti eksistensi dari struktur aljabar tersebut adalah, memberi ruang untuk membangun sistem matematika baru, atau kalkulus baru, atau teori fisika baru, dan sebagainya.

Keenam:
Secara sederhana, jika kita bertanya, bagaimana membangun sebuah sistem matematika baru di atas aljabar?
Maka langkah pertama adalah pilih sebarang struktur aljabar.
Lalu definisikan objek2 baru yang dimaksud, lalu konstruksikan sistemnya.

Ketujuh:
Selesai.
————————————————————————————————
#Mengapa teori bilangan (dan geometri?) menempati pemikiran yang paling rumit diantara semua sistem matematika yang lain?
Pertama:
Diantara seluruh sistem matematika, maka teori bilangan adalah yang paling tua selain geometri dalam sejarah manusia.

Kedua:
Ini berarti jumlah pertanyaan dan solusi yang dibangun orang untuk teori bilangan dibanding sistem matematika yang lain adalah lebih banyak dan lebih rinci.

Ketiga:
Ini berakibat akan menjadi teori yang mencapai kerumitan lebih jauh dibanding sistem2 matematika yang lain.
————————————————————————————————
#Apa yang dimaksud state program ketika di eksekusi?
State program = nilai2 konfigurasi isi dari register2 prosesor pada posisi terakhir ketika program sedang berjalan.
————————————————————————————————
#Apakah yang dimaksud dengan memindahkan kontrol prosesor kepada user program?
Yaitu mengembalikan state program ke prosesor.
Jadi kontrol program = state program mengisi register2 prosesor.
————————————————————————————————
#Bagaimana sistem operasi menyediakan fungsi2 API (atau ABI) kernel ketika komputer dinyalakan?
Pertama:
Seluruh fungsi API digelar dimemory secara binary (tinggal eksekusi atau tinggal panggil), masing2 fungsi memiliki address, kemudian semua addres dipetakan ke tabel system call, dimana pada tabel ini, tiap2 fungsi diberi nomor, diberi nama, dan diberi address, juga mungkin diberi pointer kepada definisi fungsi dalam bentuk source code bahasa C (file header).

Kedua:
Ketika user program melakukan system call untuk menggunakan fungsi API, maka system call itu dipetakan ke tabel system call untuk mengetahui nantinya fungsi mana yang hendak dieksekusi yang berarti kontrol prosesor hendak dipindahkan ke address fungsi mana.

Ketiga:
Ketika kontrol berpindah ke address fungsi, amka prosesor mulai mengeksekusi tiap2 kode dalam address tersebut hingga selesai, kemudian hasilnya ambil oleh sistem operasi dan dikembalikan ke user program dengan terlebih dahulu memindahkan kontrol prosesor ke user program.
————————————————————————————————
#Bagaimana Hardware abstarction layer dikonstruksikan?
Pertama:
Hardware abstraction layer = himpunan fungsi API atau ABI yang membungkus kode2 mesin untuk mengelola hardware.
Sehingga pengelolaan hardware cukup dilakukan dengan memanggil (system call) fungsi-fungsi tersebut.

Kedua:
Fungsi2 ABI dikosntruksikan dengan menggunakan set instruksi prosesor (assembly) kemudian dibuat menjadi makro atau fungsi.
Pada penyimpanan diluar memory (RAM) yaitu pada storage, dia berada pada suatu file, dimana dia sudah tertulis dalam bentuk bahasa mesin atau assembly, sehingga dia hanya perlu disalin ke memory ketika sistem operasi dimulai.

Ketiga:
Fungsi2 API dikonstruksikan dengan menggunakan bahasa C, ditulis dalam definisi2 pada file2 header. Sebuah wrapper harus menerjemahkan kode C ke sebuah kontinen memory addres ke dalam bahasa mesin ketika sistem operasi diinisialisasi. Sehingga pemanggilan fungsi API oleh kernel dapat langsung diarahkan ke memory address tertentu.

Keempat:
Kernel secara sederhana menjadi dapat dilihat sebagai :
Kernel = set fungsi API/ABI + wrapper set fungsi tersebut + protokol penanganan system call.
————————————————————————————————
#Bagaimana brute force dilakukan?
Pertama:
Orang menguji setiap kombinasi alphabet yang menghasilkan string.

Kedua:
Orang menguji dengan setiap kata yang ada di dalam kamus.

Ketiga:
Orang menguji dengan setiap password yang diambil dari hasil pencurian password, hasil pencurian yang jumlahnya mungkin jutaan, dan memperolehnya mungkin dibeli dari pasar gelap internet.

Keempat:
Orang membangun analisis pendahuluan terhadap set password curian dari seluruh dunia.
Mungkin dengan cara sebagai berikut:
Password apa yang paling sering dipakai di suatu negara, selanjutnya dilakukan perangkingan.
Panjang string berapa paling sering yang terjadi di suatu negara, selanjutnya dilakukan perangkingan.
Karakter pertama apa yang paling sering dipakai disuatu negara, selanjutnya dilakukan perangkingan.
Karakter kedua apa yang paling sering dipakai di suatu negara, selanjutnya dilakukan perangkingan.
Dan seterusnya, untuk posisi ke-n karakter apa yang paling sering dipakai, selanjutnya dilakukan perangkingan.
Pada posisi ke-j berapa persen penggunaan konsonan atau vokal, secara umum suatu kategori karakter tertentu, dan seterusnya.
Berapa persen suatu kata password menyangkut profil yang bersangkutan?
Berapa persen yang mengguankan tanggal kelahiran.
Berapa persen yang menggunakan nama.
Berapa persen penggunaan huruf besar pada posisi ke-k dari karakter.
Berapa persen penggunaan huruf kecil pada posisi ke-n dari karakter, dan seterusnya.

Dan seterusnya, suatu big data password dibangun dan suatu mesin belajar untuk menebak password dibuat.
Dengan demikian proses brute force berjalan diatas artificial intelligence.

Perumusan big data dapat diperluas menyangkut ciri-ciri khusus bahasa suatau negara, ciri-ciri khusus percakapan dan seterusnya.

Kelima:
Serangan burte force dilakukan dari satu no IP.
Serangan brute force dilakukan dari n buah no. IP, terutama jika terjadi pembatasan percobaan brute force.
————————————————————————————————
#Bagaimana prosesor memahami model memory?
Pertama:
Pada level prosesor, jika terjadi model memory atau diimplementasikan model memory, maka pada prosesor mestilah terdapat mikro algrotma khsuus untuk model memory tersebut.
Ketika prosesor dibuat, maka mungkin dicantum pada spesifikasinya bahwa prosesor dapat menerima model memory fisik (sebenarnya), model memory X atau model memory Y.
Programer hanya tinggal menulis tata cara penulisan memory addres sesuai model memory yang diinginkan dan prosesor di setting (mungkin pada flagnya atau register yang lain atau setingan ditempat lain. Atau disediakan set instruksi khusus untuk berpindah-pindah model memory oleh prosesor) maka prosesor menerima penulisan memory addres itu dan sebuah mikro algoritma khusus yang tertanam pada prosesor melakukan penerjemahan dari sebuah model memory ke model memory fisik atau sebenarnya, lalu prosesor bekerja sebagaimana normalnya.

Kedua:
Selesai.
————————————————————————————————
#Bagaimana prosesor memahami konsep system call, sedang system call sebenarnya adalah konsep abstrak yang berada di atas level prosesor?
Pertama:
Vendor prosesor telah menanam sebuah instruksi khsusus untuk mendukung system call pada level atas.

Kedua:
Cara pandang instruksi ini adalah sederhana, dalam level cara pandang prosesor.
Yaitu bahwa system call pada level abstrak di atas tersebut, dilihat saja sebagai suatu proses perpindahan pointer pembacaan prosesor untuk eksekusi ke suatu alamat atau blok alamat tertentu dan permindahan state program (state prosesor dalam hal ini konfigurasi isi register saat titik terakhir user program dieksekusi) ke suatu blok penyimpanan memory.

Cara kerja instruksi2 dalam cara pandang prosesor ini mungkin sebagai berikut:
Terdapat instruksi yang memberitahu prosesor untuk menyimpan state terakhir register pada suatu alamat tertentu, alamat penyimpanan itu diambil prosesor disuatu register yang mencatat arah penyimpanan (programer mungkin yang memberitahu prosesor atau mengisi register ini), kemudian programer menulis di register lain alamat dimana prosesor harus memindahkan pointer pembacaannya atau eksekusinya.
Setelah prosesor selesai.
Terdapat instruksi lagi yang meminta prosesor memindahkan kembali state prosesor semula dimana prosesor membaca register dimana alamat state terakhir user program disimpan.
Dan setersunya, proses system call dipahami prosesor dipahami dalam mekanisme register dan perintah perpindahan pointer.

Ketiga:
Secara umum, seluruh instruksi prosesor dapat dianggap saja sebagai sebuah mikro algoritma yang mengambil input pada register dan memberi output pada register.

Keempat:
Setiap mikro algoritma dapat dilihat sebagai sebuah ekspresi fungsi logika.
Jadi secara umum, tiap2 instruksi adalah sebuah fungsi logika.
Fungsi logika proposisi (yang direpresentasikan secara aljabar oleh aljabar boole).

Kita dapat melihat bahwa prosesor adalah rangkaian logika, dimana rangkaian ini bekerja berdasarkan jalur2 logika yang bisa dirubah2, tiap jalur logika adalah sebuah ekspresi fungsi logika proposisi.

Dengan demikian tiap jalur logika (ekspresi fungsi logika proposisi) diwakili oleh sebuah instruksi prosesor.

Kelima:
Akan tetapi, sebenarnya orang mungkin dapat merancang prosesor yang tidak berbasis logika proposisi, akan tetapi secara umum, mereka mungkin saja membangun prosesor dengan paradigma rangkaian adalah n-order logic. Sehingga tiap-tiap instruksi prosesor adalah mewakili sebuah ekspresi fungsi logika n-order logic.

Atau boleh jadi mereka merancang prosesor yang berbasis logika fuzzy, sehingga tiap2 instruksi adalah sebuah ekspresi fungsi logika fuzzy, atau boleh saja mereka merancang prosesor berbasi k-nilai semantik (bukan sekedar true dan false) sehingga tiap2 instruksi adalah mewakili sebuah ekspresi fungsi logika k-nilai.

Hanya saja yang menjadi point yang penting bahwa apakah aljabar boole mencukupi untuk dapat merepresentasikan n-order logic?
Untuk itu menjadi penting membangun sistem matematika yang sebagaimana halnya aljabar boole, dapat digunakan untuk merepresentasikan n-order logic dan berbagai sistem logika yang lain agar dapat diterapkan dalam sirkuit atau jejala transistor.
Tetapi dalam hal ini tentunya mungkin sangat melihat kepada arsitektur transistor dan konstruksi bit.

Keenam:
Basis logika ini mengikuti arsitektur transistor yang mereka tanam di dalam wafer prosesor. Akan tetapi mungkin tak ada arsitektur prosesor tunggal (tetapi mungkin dalam suatu jejala transistor) yang dapat dikonstruksikan untuk membuat prosesor dengan basis2 logika seperti yang disebut diatas kecuali pada logika proposisi.

Sehingga konsep2 logika diatas diserahkan pada level abstraksi yang lebih tinggi, tidak pada level gerbang logika (transistor2) prosesor. Orang dapat membangun logika2 diatas pada level abstrak, misal pada level pemrograma bahasa C, dan membangun mesin virtual yang bekerja berdasarkan basis logika yang diinginkan.

Ketujuh:
Akan tetapi orang telah menemukan cara untuk mengkonstruksikan bit2 kuantum sekaligus transistor2 kuantum, sehingga terbuka lagi satu cakrawala basis logika, yaitu logika proposisi yang berdiri diatas nilai2 kuantum, sehingga dapat dikonstruksikan ekspresi fungsi2 logika kuantum.

Ekspresi fungsi2 logika kuantum kemudian dinyatakn sebagai instruksi2 dasar prosesor kuantum, dalam hal ini instruksi2 kuantum,
Dengan demikian orang menyusun mikro algoritma kuantum.
————————————————————————————————
#Bagaimana melakukan enkapsulasi fungsi-fungsi API atau ABI dari sisi client?
Pertama:
Buat sebuah class, dimana class ini dapat diinstansiasi pada sisi client.
Sinopsis class atau definisi class haruslah dapat di unduh terlebih dahulu oleh client untuk digunakan pada sisi client.

Kedua:
Class terdiri dari sejumlah property dan method.
Property2 class adalah data-data API/ABI yang dapat diakses dan property2 lain yang perlu mendukung koneksi dan akses ke server API/ABI.

Method2 class adalah representasi satu ke satu dengan fungsi API/ABI di server, dimana ketika method digunakan, dia melakukan inisialisasi pengiriman profil fungsi API/ABI yang hendak digunakan, mungkin memiliki pilihan2 koneksi dalam beberapa protokol, kemudian menerima hasil kalkulasi atau eksekusi pada sisi server yang dikirim balik oleh server.
Method ini kemudian mengembalikan hasil server itu sebagai return method tersebut.

Dengan demikian, penggunaan objek class seakan2 semua kode dan eksekusi dilakukan di sisi client, client tidak perlu menginisialisasi dan mengirim permintaan secara manual kepada sever API/ABI. Tetapi cukup dilakukan oleh objek class secara terenkapsulasi.

Ketiga:
Dalam hal ini, client hanya melakukan satu kali permintaan secara manual, yaitu meminta sinopsis class untuk diimplementasikan pada sisi client.