PEMODELAN INTERAKSI ANTARA PENGGUNA DAN SISTEM AUGMENTED REALITY KE DALAM BAHASA FORMAL MENGGUNAKAN TIMED AUTOMATA

ASLAN ALWI, Dr. Azhari, MT

2019 | Disertasi | DOKTOR ILMU KOMPUTER

Penelitian disertasi ini mengemukakan dua gagasan utama, yaitu permodelan interaksi antara pengguna dengan ARS menggunakan bahasa yang reguler sehingga diperoleh model interaksi dengan kompleksitas polinomial, dan permodelan Universal Turing Machine (UTM) untuk sebagai kompiler atau interpreter bagi bahasa-bahasa reguler, bebas konteks, konteks sensitif dan unrestricted dalam level-level bahasa Chomsky. Pada kebanyakan interaksi antara pengguna dan sistem augmented reality (ARS), pengguna memberikan penanda (marker) kepada ARS dan ARS memberi respon di atas penanda tersebut. Di dalam konteks ini, sebuah penanda dipetakan kepada sebuah respon ARS atau secara umum sebuah matriks penanda dipetakan kepada sebuah matriks respon ARS. Interaksi ini adalah sebuah interaksi yang konstan atau linier sejak di sana hanya ada sebuah pemetaan bijective antara sebuah himpunan penanda kepada sebuah himpunan respon ARS. Pada penelitian ini, kami mengusulkan perluasan kompleksitas interaksi pengguna-ARS ke dalam polinomial. Interaksi ini bukan hanya sebuah penanda untuk sebuah respon ARS (atau sebuah matriks penanda untuk sebuah matriks respon ARS), tetapi interaksi yang penggunanya menyediakan sebuah string penanda sebagai sebuah word marker, yaitu sebuah kombinasi sejumlah penanda sebagai sebuah word, untuk sebuah respon ARS tunggal. Interaksi diimplementasikan dengan menyatakan bahasa pengguna ke dalam generalized Finite State Automata (gFSA) dan menempatkan sebuah mesin Turing universal (UTM) antara pengguna dan ARS sehingga UTM berkedudukan sebagai sebuah interpreter yang menerjemahkan atau memetakan bahasa pengguna kepada respon ARS. Penelitian ini menghasilkan sebuah model interaksi yang memiliki algoritma komputasi berupa interpreter dan kompiler untuk interaksi yang polinomial dan nondeterministik polinomial. Algoritma komputasi untuk model interaksi tersebut adalah sebuah algoritma mesin Turing universal. Penelitian model interaksi ini juga menghasilkan sebuah algoritma komputasi real time berupa mesin Turing universal yang diberi waktu (clock). Algoritma komputasi ini dapat dijadikan sebagai sebuah interpreter real time atau kompiler real time baik interaksi yang kompleksitasnya polinomial atau nondeterministik polinomial. Penelitian juga menghasilkan sebuah fondasi gagasan tentang bagaimana membangun sebuah bahasa interaksi yang real time dalam seluruh bentuk kompleksitas bahasa, baik itu bahasa reguler, bebas konteks, konteks sensitif, unrestricted dan sebagainya di dalam hierarki bahasa Chomsky. Seluruh model diuji menggunakan langkah-langkah mesin Turing dan dibuktikan keabsahannya menggunakan matematika induksi. Model juga dibuktikan sifat decidability nya dengan menurunkan sebuah teorema beserta pembuktiannya secara deduktif. Sifat decidability menjamin bahwa algoritma dapat dijalankan atau disimulasikan oleh semua jenis komputer yang Turing complete.

This dissertation research proposes two main ideas, namely the modeling of interactions between users and ARS using regular language so as to obtain interaction models with polynomials complexity, and modeling Universal Turing Machine (UTM) for compilers or interpreters for regular, context-free languages. sensitive and unrestricted context in Chomsky language levels. In most interactions between the user and the augmented reality (ARS) system, the user provides a marker to ARS and the ARS responds above the marker. In this context, a marker is mapped to an ARS response or generally a marker matrix is mapped to an ARS response matrix. This interaction is a constant or linear interaction since there is only a bijective mapping between a set of markers and a set of ARS responses. Interaction is implemented by declaring the user's language into the generalization of finite state automata (gFSA) and placing a universal Turing machine (UTM) between the user and ARS, where UTM as an interpreter translates or maps the user's language to the ARS response. This research produced a interaction model with has a computational model in the form of interpreters and compilers for polynomial and nondeterministic polynomials interactions. The resulting computational model is a universal Turing machine algorithm. The study also produced a real time computational model in the form of a clocked universal Turing machine. This computational model can be used as a real time interpreter or real time compiler, whether it is interaction with the complexity of the polynomial or nondeterministic polynomials. Research also produces a foundation for ideas on how to build a language of real-time interaction in all forms of language complexity, be it regular language, context-free, sensitive context, unrestricted and so on in the Chomsky language hierarchy. All models were tested using the Turing machine steps and proven validity using mathematical induction. The model is also proven by its decidability by declaring a theorem and its proof deductively. The nature of decidability guarantees that the algorithm can be run or simulated by all types of computers that Turing complete.

Kata Kunci : Interaksi Polinomial, Interaksi Polinomial Nondeteriministik, Mesin Turing, Mesin Turing Universal (UTM), gFSA, interpreter, word marker, decidability, real time.