Mesin Turing, sebagai model program otomat

Mesin Turing, sebagai model program otomat

1. Pendahuluan

Pemrograman membutuhkan model algoritmik universal baru, dan perangkat keras mengimplementasikan algoritma tidak hanya dalam bentuk yang berbeda, tetapi juga berdasarkan model algoritmik lain - otomatis. Mengadopsi teknologi dari bidang pengembangan perangkat keras adalah ide kunci pemrograman otomatis. Namun, sintesis perangkat digital berbeda dari pemrograman. Tetapi, meminjam model, di satu sisi, tidak disarankan untuk mengubahnya secara substansial, tetapi, di sisi lain, seseorang tidak dapat mengabaikan teori dan praktik pemrograman yang ada.

Selanjutnya, kami akan mempertimbangkan teknologi SWITCH untuk merancang program otomatis, di mana Anda mengalami proses seperti itu sepanjang waktu. Di satu sisi, itu mengubah model mesin negara sehingga benar-benar membawanya melampaui ruang lingkup teori automata. Dan, di sisi lain, ia memperkenalkan ke dalam konsep pemrograman yang sulit untuk dipahami oleh pemrogram, dan, kadang-kadang, hanya berlebihan, karena ada rekan-rekan yang lebih akrab dari teori program dan praktik pemrograman.

Sebagai dasar untuk pembahasan masalah pemrograman otomatis, kami mengambil kuliah terbaru oleh A. Shalyto [1] dan artikel-artikel "terprogram" tentang definisi paradigma pemrograman otomatis [2, 3].

1. Objek otomatis, skema program

Dalam kuliah tersebut, pencapaian pemrograman otomatis adalah pengenalan konsep objek kontrol otomatis, yang dipinjam dari teori kontrol otomatis (TAU). Namun, ingatlah bahwa dalam TAU mereka menganggap tidak begitu banyak objek, tetapi sistem, di antaranya yang dibedakan sebagai berikut: [4]



Berdasarkan ini, akan lebih tepat untuk berbicara tentang sistem kontrol otomatis (ACS). Sekarang mari kita lihat diagram fungsional khas dari senjata self-propelled yang ditunjukkan pada Gambar. 1. Jika pita mesin Turing dianggap sebagai objek kontrol, maka perangkat penggerak (IS) akan menjadi elemen MT yang menerapkan pengubahan isi pita dan menggerakkan kepala, dan alat pengukur (IS) akan menjadi elemen yang membaca informasi dari pita tersebut.


Fig. 1. Diagram fungsional senjata self-propelled

Tapi mengapa beralih ke TAU, jika ada praktik yang lebih dekat dengan pemrograman desain sistem komputer, di mana perangkat operasi (OS), yang, tentu saja, termasuk MT, dianggap sebagai kombinasi mesin operasi (OA) dan pengendali (UA). Dan ini lebih dekat dengan apa yang akhirnya kami perjuangkan - membenarkan kekuatan pemrograman otomatis. Dalam gbr. 2 menunjukkan layar teks dari monograf oleh Mayorov S.A., Novikov G.I. Struktur komputer elektronik [5], di mana masalah desain op-amp dipertimbangkan dengan sangat rinci.


Fig. 2. Konsep manajer dan mesin operasi

Tetapi, jika kita membandingkan teori desain komputer dan teori program, maka analogi struktural yang jelas dapat dilacak di antara mereka. Dalam teori pemrograman, model program apa pun pada level struktural dapat direpresentasikan sebagai skema program S = (M, A, C), di mana M adalah himpunan elemen memori, A adalah himpunan operator, C adalah himpunan [10]. Mengikuti pendekatan ini, setiap program mesin Turing juga dapat didefinisikan sebagai skema program di mana himpunan M diwakili oleh sel tape, himpunan operator dengan tindakan MT yang terkait dengan 1) analisis sel, 2) mengubah karakter dalam sel tape dan 3) menggerakkan kepala.

Dengan demikian, konsep skema program sepenuhnya analog dengan konsep operasional dan kontrol automata yang dipertimbangkan, di mana model UA adalah model mesin keadaan terbatas struktural (SKA) yang dipertimbangkan di bawah ini, dan OA "adalah struktur untuk melakukan tindakan terhadap informasi." Dalam hal ini, OA mencakup elemen penyimpanan data (di atas adalah memori) dan blok untuk memproses informasi yang menerapkan perhitungan kondisi logis dan implementasi tindakan tertentu (di atas - banyak operator).

Dari uraian di atas, dapat dipahami bahwa rekaman itu hanya dapat dianggap kondisional sebagai objek kontrol untuk MT. Jika hanya karena perangkat kontrol mesin Turing tidak memiliki akses langsung ke sana, karena semua operasi dengan sel direalisasikan secara tidak langsung oleh blok OA. Selain itu, tampaknya itu tidak terlalu akrab atau, jika tidak dikatakan, aneh untuk dipertimbangkan sebagai tujuan manajemen program, sebagai sistem kontrol, objek yang mewakili memori (rekaman).
Jadi, untuk definisi formal dari mesin Turing, dan dalam konteksnya tempat untuk model mesin keadaan terbatas, konsep teori program sudah cukup. Sekarang, berbeda dengan definisi yang sangat kabur dari program otomat yang diberikan dalam kerangka teknologi SWITCH, kita dapat mengatakan bahwa program automaton adalah program yang memiliki kontrol dalam bentuk model mesin keadaan terbatas.

Apa yang akan menjadi program itu sendiri - dengan perilaku sederhana atau kompleks, apa itu "variasi" - dengan kontrol logis, "dengan alokasi keadaan eksplisit", dll. dll. tidak terlalu penting. Yang utama adalah jenis manajemennya. Elemen-elemen yang tersisa dari program dapat ditentukan dalam rentang yang luas - dari yang paling sederhana, seperti, misalnya, dengan mesin Turing, hingga yang paling kompleks - segala bentuk operator, fungsi dan struktur data dari bahasa pemrograman - assembler, bahasa tingkat tinggi, dll.

Anda juga dapat mengingat bahwa mesin Turing telah lama dianggap sebagai mat otomatis [6] atau, dalam kasus ekstrem, perpanjangannya yang sederhana [7]. Tetapi Anda perlu memahami apa jenis robot itu, apa jenis ekstensi itu, dan apakah mereka setara dengan model mesin negara terbatas klasik. Mari kita coba klarifikasi ini.

2. Turing pemrograman dalam lingkungan pemrograman otomatis

Dalam gbr. Gambar 3 menunjukkan otomat untuk fungsi kenaikan MT dari monograf [8]. Dalam bentuk, ini jelas bukan program MT, tetapi sudah bukan mesin negara hingga klasik. Dalam gbr. Gambar 4 menunjukkan grafik mesin negara terbatas struktural klasik (SKA) dan implementasinya di lingkungan VKPa (lingkungan pemrograman otomatis komponen visual dalam C ++ dalam kerangka perpustakaan Qt dan lingkungan Pencipta Qt), yang mengimplementasikan algoritma unit kontrol MT yang sama.


Fig. 3. Tambah jumlah per unit menggunakan mesin Turing


Gambar. 4 Model program kenaikan untuk MT dalam bentuk SKA

Anda dapat melihat bahwa mesin struktural memiliki empat saluran input dan lima output. Setiap saluran ini dikaitkan dengan fungsi program dengan nama yang sama - predikat atau tindakan. Di sini, predikat adalah fungsi tanpa parameter yang mengembalikan nilai Boolean tergantung pada nilai sel rekaman yang mereka lihat, dan tindakan adalah fungsi tanpa parameter yang melakukan satu atau tindakan lain untuk mengubah sel kaset dan menggerakkan kepala mesin Turing.

SKA ini memiliki seperangkat status yang sama dengan otomat pada Gambar. 3. Selain itu, selain pemetaan otomat itu sendiri, yang disajikan oleh SKA, ia mengimplementasikan dua pemetaan lagi: memetakan set predikat (x1, ..., xM) ke set saluran input dari mesin yang sama, dan set saluran output mesin ke set tindakan yang sama - y1, ..., yN. Misalnya, predikat x3 akan mengembalikan true (nilai 1 untuk sinyal input dengan nama yang sama), jika ada 1 dalam sel saat ini, dan tindakan y4, yang akan dipicu ketika sinyal output yang sama dari mesin mengambil nilai 1, akan sesuai dengan menggerakkan kepala ke kiri (L) dan dll. dll.

Perhatikan bahwa SKA tidak secara langsung mengontrol kaset, tetapi mengimplementasikan pemetaan [tambahan], menghubungkan sinyal automaton dengan fungsi yang menentukan banyak pengoperasian mesin Turing. Ini sekali lagi meyakinkan kita bahwa tidak perlu memperkenalkan konsep objek kontrol otomatis dalam situasi di mana "kuno", tetapi konsep pemetaan ketat secara matematis sudah cukup.

Membandingkan automata di Fig. 3 dan ara. 4, dapat dilihat bahwa SKA tidak menggunakan perintah "*" (lihat Gambar 1). Dalam situasi seperti itu, cukup baginya untuk tidak memberikan sinyal yang terkait dengan perintah ini. Selain itu, dua atau lebih sinyal (baik input dan output) pada transisi yang sama adalah paralel. Oleh karena itu, ketika ada konflik akses ke objek yang dibagikan (misalnya, Anda perlu mengubah sel dan memindahkan kepala), perjanjian digunakan: tindakan pada satu transisi dilakukan secara berurutan dalam urutan jumlah mereka, mis. tindakan dengan angka yang lebih tinggi dilakukan setelah tindakan dengan angka yang lebih rendah. Perjanjian ini tidak berlaku untuk predikat, karena mereka tidak mengganti kaset. Jadi kami membuat mesin lebih kompak dan intuitif (tidak perlu memperkenalkan kondisi perantara).

Dalam proses pengujian program kenaikan, situasi diidentifikasi di mana masalah mungkin timbul selama operasi MT. Pertama, rekaman nyata tidak terbatas dan melampaui itu dapat menyebabkan program macet. Kedua, perlu untuk menunjukkan posisi awal kepala. Tanpa ini, jika, misalnya, nomor berada di tempat kaset yang sewenang-wenang, dan keadaan awal kepala adalah di sebelah kiri nomor dan berlawanan dengan ruang, maka kepala akan segera mulai bergerak ke kiri. Kemudian ia dapat melampaui batas-batas kaset, menyebabkan program "macet", atau, setelah bergerak satu langkah ke kiri, ia akan menulis ke sel 1 dan, menggantung, akan menyelesaikan operasi "sukses". Atau, jika nomor tersebut berisi 1 dalam semua digit dan ditulis dari awal kaset, maka upaya terakhir untuk mentransfer 1 ke digit senior akan menyebabkan "crash" yang sama.

2.1. Implementasi objek MT di C ++

Pertimbangkan implementasi perangkat lunak objek dari mesin Turing di C ++ di lingkungan VKPa, yang mengimplementasikan program apa pun untuk MT, termasuk program perhitungan kenaikan.

Untuk tujuan ini, kelas dasar telah dibuat yang mewakili mesin Turing, yang diwarisi oleh objek perangkat lunak yang mengimplementasikan satu atau lain program MT. Yang dasar ini ditunjukkan pada Listing 1, dan program yang mengimplementasikan tugas kenaikan ditunjukkan pada Listing 2.

Daftar 1. Implementasi perangkat lunak dari kelas dasar MT

#include "lfsaappl.h" class FTuringMashine : public LFsaAppl { public: FTuringMashine(string strNam, CVarFsaLibrary *pCVFL, LArc* pTBL); protected: int x15(); int x16(); void y14(); void y15(); void y16(); void y17(); QString strSrc; //    QString strTape; //  QString strHead; //  int nIndexHead{0}; //   bool bRestart{false}; //   int nHeadPosition{0}; //    }; #include "stdafx.h" #include "FTuringMashine.h" FTuringMashine::FTuringMashine(string strNam, CVarFsaLibrary *pCVFL, LArc* pTBL): LFsaAppl(pTBL, strNam, nullptr, pCVFL) { nHeadPosition = 0; strHead = "________________________________________"; nIndexHead = nHeadPosition; } //============================================================== //  //  ? int FTuringMashine::x15() { return strTape[nIndexHead] == '#'; } // ? int FTuringMashine::x16() { return bRestart; } //============================================================== //  //      void FTuringMashine::y14() { strTape[nIndexHead] = '#'; } //    ( ) void FTuringMashine::y15() { nIndexHead++; } //    ( ) void FTuringMashine::y16() { nIndexHead--; } //     void FTuringMashine::y17() { strTape = strSrc; nIndexHead = 0; bRestart = false; nIndexHead = nHeadPosition; } 

Daftar 2. Program kenaikan untuk mesin Turing

 #include "FTuringMashine.h" class FTIncrement : public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTIncrement(nameFsa, pCVarFsaLibrary); } FTIncrement(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); void y1(); void y2(); }; #include "FTIncrement.h" static LArc TBL_TIncrement[] = { // . . , .   , 2- , 2011 ., // .17-18 //=====    (. ..   , - .: , 2003. - 208 .) ============== // f(,^` `) = (,`*`,R) // f(,` `) = (,` `,L) // f(,`1`) = (,`0`,L) // f(,` `) = (,`1`,R) // f(,`0`) = (,`1`,R) //========================================= LArc(" ", " ", "^x1", "y15"), LArc(" ", " ", "x1", "y16"), LArc(" ", " ", "x2", "y2y16"), LArc(" ", "", "x1", "y1"), LArc(" ", "", "x3", "y1"), LArc("", " ", "x16", "y17"), LArc() }; FTIncrement::FTIncrement(string strNam, CVarFsaLibrary *pCVFL): FTuringMashine(strNam, pCVFL, TBL_TIncrement) { strSrc = "11011110011111 "; strTape = strSrc; } //  int FTIncrement::x1() { return strTape[nIndexHead] == ' '; } int FTIncrement::x2() { return strTape[nIndexHead] == '1'; } int FTIncrement::x3() { return strTape[nIndexHead] == '0'; } //  void FTIncrement::y1() { strTape[nIndexHead] = '1'; } void FTIncrement::y2() { strTape[nIndexHead] = '0'; } 

2.2. Contoh program untuk MT dengan implementasi di C ++

Pertimbangkan contoh program untuk MT yang "bertindak sebagai akseptor bahasa, mis. itu bisa mengenali bahasa ”dari [9]. Fungsi transisinya ditunjukkan pada Gambar. 5, dan otomat setara dalam bentuk SKA pada Gambar. 6.

 δ(1, a) = (2, x, R) δ(1, y) = (4, y, R) δ(2, a) = (2, a, R) δ(2, y) = (2, y, R) δ(2, b) = (3, y, L) δ(3, y) = (3, y, L) δ(3, a) = (3, a, R) δ(3, x) = (1, x, R) δ(4, y) = (4, a, R) δ(4, #) = (F, #, L) 

Fig. 5. Fungsi transisi dari mesin Turing, mengenali bahasa {anbn: n≥1}


Fig. 6. Grafik SKA dari mesin Turing yang mengenali bahasa {anbn: n≥1}

Unit kontrol MT dalam bentuk SKA memiliki 6 saluran input dan 7 output. Program akseptor juga mencakup jumlah predikat dan tindakan yang sesuai, yang disajikan dalam gambar di sebelah kanan grafik otomat. Implementasi program C ++ di lingkungan VKPA ditunjukkan pada Listing 3.

Listing 3. Program untuk mesin Turing yang mengenali bahasa {anbn: n≥1}

 #include "FTuringMashine.h" extern LArc TBL_TAcceptor[]; class FTAcceptor : public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTAcceptor(nameFsa, pCVarFsaLibrary); } FTAcceptor(string strNam, CVarFsaLibrary *pCVFL, LArc* pTB = TBL_TAcceptor); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y18(); int nState{1}; friend class CDlgTAcceptor; }; #include "stdafx.h" #include "FTAcceptor.h" LArc TBL_TAcceptor[] = { // . .Ma  .   . 2013 ., //     , .304 //=====    ============== // f(1,a) = (2,x,R) f(1,y) = (4,y,R) // f(2,a) = (2,x,R) f(2,y) = (2,y,R) // f(2,b) = (2,x,R) f(3,y) = (3,y,L) // f(3,a) = (3,a,R) f(3,x) = (1,x,R) // f(4,y) = (4,a,R) f(4,#) = (F,#,L) //========================================= LArc("1", "2","x1", "y1y15"), // 1,a,2,x,R LArc("1", "4","x3", "y15"), // 1,y,4,R LArc("2", "2","x1", "y15"), // 2,a,2,R LArc("2", "3","x2", "y2y16"), // 2,b,3,y,L LArc("2", "2","x3", "y15"), // 2,y,2,R LArc("3", "3","x1", "y16"), // 3,a,3,L LArc("3", "3","x3", "y16"), // 3,y,3,L LArc("3", "1","x4", "y15"), // 3,x,1,R LArc("4", "4","x3", "y2y15"), // 4,y,4,a,R LArc("4", "F","x15", "-"), // 4,#,F,-,- LArc("F", "1","x16", "y17"), // LArc("1", "1","x16", "y17"), // LArc("2", "1","x16", "y17"), // LArc("3", "1","x16", "y17"), // LArc("4", "1","x16", "y17"), // // LArc("1", "1","--", "y18"), // LArc() }; FTAcceptor::FTAcceptor(string strNam, CVarFsaLibrary *pCVFL, LArc* pTB): FTuringMashine(strNam, pCVFL, pTB) { strSrc = "aaaaaaaaaabbbbbbbbbb#"; strTape = strSrc; } int FTAcceptor::x1() { return strTape[nIndexHead] == 'a'; } int FTAcceptor::x2() { return strTape[nIndexHead] == 'b'; } int FTAcceptor::x3() { return strTape[nIndexHead] == 'y'; } int FTAcceptor::x4() { return strTape[nIndexHead] == 'x'; } void FTAcceptor::y1() { strTape[nIndexHead] = 'x'; } void FTAcceptor::y2() { strTape[nIndexHead] = 'y'; } void FTAcceptor::y3() { strTape[nIndexHead] = 'a'; } void FTAcceptor::y18() { switch(nState) { case 1: if (x1()) { nState = 2; y1(); y5(); break; } if (x3()) { nState = 4; y5(); break; } break; case 2: if (x1()) { nState = 2; y5(); break; } if (x2()) { nState = 3; y2();y6(); break; } if (x3()) { nState = 2; y5(); break; } break; case 3: if (x1()) { nState = 3; y6(); break; } if (x3()) { nState = 3; y6(); break; } if (x4()) { nState = 1; y5(); break; } break; case 4: if (x3()) { nState = 4; y2(); y5(); break; } if (x5()) { nState = 5; break; } break; case 5: if (x6()) { y7(); nState = 1; break; } break; } } 

Dalam Listing 3, tindakan y18 merupakan varian dari program MT sesuai dengan pendekatan teknologi SWITCH. Sebagai bagian dari implementasi pemrograman otomatis lingkungan VKPA, dalam hal ini, bukannya otomaton pada Gambar. 6, akan diperlukan untuk mengimplementasikan otomat dengan satu keadaan, yang mengeluarkan sinyal y18 dalam siklus. Itu sesuai dengan baris komentar dari tabel konversi pada Listing 3. Agar mesin otomatis berfungsi sebagai SWICH, Anda perlu menghapus komentar dari baris ini dan mengomentari baris yang tersisa.

Pertimbangkan contoh lain dari program untuk mesin Turing dari [7], di mana MT didefinisikan sebagai "perpanjangan yang sangat sederhana dari model mesin keadaan terbatas". Dalam hal ini, program untuk mesin Turing adalah daftar terbatas hingga lima fungsi transisi dan output yang didefinisikan sebagian δ: S × XS × X × G.

Program MT, yang menemukan pembagi umum terbesar (GCD) dari dua angka, ditunjukkan pada Gambar. 7. Grafik SKA yang setara dengannya disajikan pada Gambar. 8. Perhatikan bahwa perintah penulisan ulang tidak digunakan di sini juga. Implementasi C ++ ditunjukkan pada Listing 4.


Fig. 7. Grafik transisi dari mesin Turing yang menghitung GCD dari dua angka, dan beberapa konfigurasinya saat memproses sepasang angka <4, 6>


Fig. 8. Grafik SKA, setara dengan grafik pada Gambar. 7

Listing 4. Program untuk mesin Turing untuk menemukan GCD dari dua angka

 #include "FTuringMashine.h" class FTGrCmDiv: public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTGrCmDiv(nameFsa, pCVarFsaLibrary); } FTGrCmDiv(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y17(); }; #include "FTGrCmDiv.h" static LArc TBL_TGrCmDiv[] = { //=====     (Greatest Common Divider) ============== // . ..   , - .: , 2003. - 208 . // .194 // .  ..    . .:  , 1974, - 200. // .76, 84-87 LArc("s","s","x1", "y16"), // LArc("s","s","x2", "y16"), // LArc("s","p","x3", "y1"), // LArc("s","r","x15", "y15"), // LArc("p","p","x1", "y15"), // LArc("p","p","x2", "y15"), // LArc("p","s","x3", "y2"), // LArc("p","q","x15", "y16"), // LArc("q","q","x1", "y3y16"), // LArc("q","q","x2", "y14y16"), // LArc("q","s","x3", "y15"), // LArc("q","s","x15", "y15"), // LArc("r","r","x1", "y14y15"), // LArc("r","r","x2", "y3y15"), // LArc("r","s","x3", "y16"), // LArc("r","!","x15", "--"), // LArc("!","s","x16", "y17"), // LArc() }; FTGrCmDiv::FTGrCmDiv(string strNam, CVarFsaLibrary *pCVFL): FTuringMashine(strNam, pCVFL, TBL_TGrCmDiv) { nHeadPosition = 4; strSrc = "#1111111111## "; strTape = strSrc; nIndexHead = nHeadPosition; } int FTGrCmDiv::x1() { return strTape[nIndexHead] == 'a'; } int FTGrCmDiv::x2() { return strTape[nIndexHead] == 'b'; } int FTGrCmDiv::x3() { return strTape[nIndexHead] == '1'; } int FTGrCmDiv::x4() { return strTape[nIndexHead] == '#'; } void FTGrCmDiv::y1() { strTape[nIndexHead] = 'a'; } void FTGrCmDiv::y2() { strTape[nIndexHead] = 'b'; } void FTGrCmDiv::y3() { strTape[nIndexHead] = '1'; } void FTGrCmDiv::y17() { strTape = strSrc; nIndexHead = 4; bRestart = false; nIndexHead = nHeadPosition; } 

Sebagai kesimpulan, program MT lain dari para pengembang teknologi SWITH, dipertimbangkan dalam artikel [11], yang menyajikan tugas mengenali tanda kurung dalam dua versi. Salah satunya adalah dalam bentuk mesin Miles, yang kedua adalah mesin campuran (masing-masing pada Gambar. 9 dan Gambar. 11). Automata struktural yang berkaitan dengan mereka ditunjukkan pada Gambar. 10 dan ara. 12. Implementasi program C ++ ditunjukkan pada Listing 5.


Fig. 9. Pengakuan tanda kurung kedalaman sewenang-wenang. Grafik Konversi Mil


Fig. 10. Pengakuan tanda kurung kedalaman sewenang-wenang. Earl SKA Miles


Fig. 11. Pengakuan tanda kurung kedalaman sewenang-wenang. Grafik transisi dari otomat campuran


Fig. 12. Pengakuan tanda kurung kedalaman sewenang-wenang. SCA grafik transisi dari automaton campuran

Listing 5. Program untuk mesin Turing untuk mengenali tanda kurung

 #include "../FTuringMashine.h" class FTListing2 : public FTuringMashine { public: void MooreAction(); LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTListing2(nameFsa, pCVarFsaLibrary); } FTListing2(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y4(); void y5(); int i{0}; }; #include "FTListing2.h" static LArc TBL_TListing2[] = { // .  ..,  ..     , , №2, .144-149 //=====    (. ..   , - .: , 2003. - 208 .) ============== // f(,^` `) = (,`*`,R) // f(,` `) = (,` `,L) // f(,`1`) = (,`0`,L) // f(,` `) = (,`1`,R) // f(,`0`) = (,`1`,R) //========================================= /* //  LArc("0", "1", "x2", "y2"), // '(';  LArc("0", "3", "x3", "--"), // '('; LArc("1", "1", "x2", "y2"), // '(';  LArc("1", "1", "x3", "y3"), // ')';  LArc("1", "3", "^x1x4", "--"), // i!=0;' ';  LArc("1", "3", "x1x3", "--"), // i==0;')';  LArc("1", "2", "x1x4", "--"), // i==0;' ';  LArc("2", "0", "x16", "y17"), // bRestart;  LArc("3", "0", "x16", "y17"), // bRestart;  */ //* //   - LArc("0", "1", "x2", "y2"), // '(' LArc("0", "3", "x3", "--"), // ')' LArc("1", "1", "x2", "y2"), //'(';  LArc("1", "1", "x3", "y3"), // ')';  LArc("1", "2", "x1x4", "--"), // i==0;' '; LArc("1", "3", "^x1x4", "--"), // i!=0;' '; LArc("1", "3", "x1x3", "--"), // i==0;')'; LArc("2", "0", "x16", "y17"), // bRestart;  LArc("3", "0", "x16", "y17"), // bRestart;  //*/ LArc() }; FTListing2::FTListing2(string strNam, CVarFsaLibrary *pCVFL): FTuringMashine(strNam, pCVFL, TBL_TListing2) { strSrc = "(()()) "; strTape = strSrc; } //  int FTListing2::x1() { return i == 0; } int FTListing2::x2() { return strTape[nIndexHead] == '('; } // int FTListing2::x3() { return strTape[nIndexHead] == ')'; } // int FTListing2::x4() { return strTape[nIndexHead] == ' '; } // //  void FTListing2::y1() { i = 0; } // z1_0 void FTListing2::y2() { i++; } // z1_1 void FTListing2::y3() { i--; } // z1_2 void FTListing2::y4() { strTape = ""; } // z2_0 void FTListing2::y5() { strTape = ""; } // z2_1 void FTListing2::MooreAction() { string strState = FGetState(); if (strState=="0") { y1(); } //   else if (strState=="1") { y15(); } //    else if (strState=="2") { y4(); } //  else if (strState=="3") { y5(); } //  } 

Karena otomat pada Gambar. 12 menolak untuk bekerja, diputuskan untuk pergi ke mesin pada Gambar. 9. Mesin otomatis setara dengan itu dalam bentuk SKA ditunjukkan pada Gambar. 10. Benar, secara formal ini juga merupakan automaton campuran, dari mana sinyal pada kondisi "0" dan sinyal y15 pada keadaan "1" ditinggalkan dari implementasi pertama (Gbr. 12). Yang pertama diperlukan selama instalasi awal, dan sinyal y15 mengimplementasikan pergeseran kepala ke kanan untuk membaca karakter pita berikutnya. Sisa SKA sesuai dengan mesin Miles pada Gambar. 9.

Setelah otomat dalam gambar. 10 berhasil diuji, dikembalikan ke mesin pada Gambar. 11. Dan menjadi jelas bahwa sinyal z1_1 dengan status "1" tidak perlu untuk itu (untuk otomat pada Gambar. 12 itu adalah sinyal y2). Masalahnya adalah ketika dia menemukan "braket kiri", dia menambah penghitung dengan dua unit, dan ketika dia menemukan "braket kiri" dia tidak mengubahnya sama sekali. Jadi, setelah mendeteksi "braket kiri" itu disebut dua kali - satu kali pada loop bertanda x2 / y2, dan kedua kalinya setelah memasuki keadaan. Dan ketika "braket kanan" terdeteksi, penghitung pertama berkurang pada loop, dan kemudian meningkat saat memasuki negara.

Alasan untuk pekerjaan kontrol MT ini adalah dalam interpretasi yang salah oleh penulis tentang fungsi mesin tipe Moore. Rupanya, mereka percaya bahwa sinyal dengan keadaan di otomat Moore dijalankan hanya ketika memasuki keadaan ini (lihat transisi dari negara "0" ke "1"), tetapi pada kenyataannya itu dikeluarkan setiap kali Anda memasuki negara ini. Termasuk saat akan melalui loop. Dengan demikian, kita berhadapan bukan dengan kesalahan (siapa yang tidak salah?), Tetapi dengan masalah yang lebih serius - interpretasi yang salah dalam kerangka kerja teknologi SWITH tentang fungsi automata tipe Moore. Pengujian model setara menunjukkan ini.

3. Kesimpulan

Sebagai rangkuman, kita dapat mengatakan bahwa tidak ada perbedaan formal antara Turing dan pemrograman otomatis, seperti Mesin Turing adalah model abstrak dari program otomat. Hanya dalam kasus terakhir, satu set yang lebih luas dari operator dan struktur data (memori) digunakan. Sekarang kita dapat dengan yakin menjawab pertanyaan tentang bagaimana mesin Post, sebagai model program biasa, berbeda dari mesin Turing, model program otomatis. Model manajemen dan hanya itu, karena sisanya - memori dan operator bisa sama.
Akibatnya, pemrograman biasa berbeda dari pemrograman otomatis hanya dalam satu hal - model kontrol. Jadi, sementara untuk implementasi automata, operator kontrol biasa dari tipe sakelar digunakan dan sejenisnya tidak dapat digunakan, dengan kata lain, pemrograman semacam itu dianggap otomatis. Ini bisa menjadi tiruan automata dengan kehilangan sifat spesifiknya dan tidak lebih.

Jadi, memberikan definisi konsep program otomat dan pemrograman otomat, kita tidak perlu berbicara tentang "objek kontrol otomatis", tetapi tentang program dan hanya program yang memiliki kontrol dalam bentuk mesin keadaan terbatas klasik.
Dan fakta menarik lainnya yang ingin saya perhatikan. Pada awal 2000-an, penulis menyuarakan pemahaman mereka tentang pemrograman otomatis untuk khalayak luas. Artikel mereka tentang mesin abstrak diterbitkan di majalah PC World No. 2 tahun 2002 [11, 12, 13]. Dapat dikatakan bahwa selama bertahun-tahun, vonis para pihak tidak terpengaruh. Meskipun, mungkin ini hanya mencerminkan tingkat kepercayaan mereka pada keputusan yang dipilih.

Misalnya, dalam "kuliah baru tentang pemrograman otomatis" A. Shalyto Dibandingkan dengan "kuliah dengan slide" sebelumnya (sepuluh tahun yang lalu), hanya video contoh berdasarkan pada "paket canggih" Stateflow ditambahkan. Tampaknya ini menegaskan kebenaran gagasan A. Shalyto, karena apa yang tidak dapat diimplementasikan dalam UniMod (proyek ini tampaknya "beku"), pengembang Stateflow diwujudkan. Dan, mungkin, tidak begitu penting siapa yang melakukannya ...

Namun, pada saat publikasi artikel yang disebutkan, penulis teknologi SWITCH sudah tahu kritik tentang itu. Ini bukan rahasia sejak itu itu tersedia di situs web SoftCraft [14]. Itu juga menciptakan bagian yang ditujukan untuk pemrograman otomatis pada umumnya dan teknologi SWITH dan teknologi KA pada khususnya. Posisi penulis dibahas di forum situs (terbuka pada saat itu). Tapi semua tetap tidak yakin.

Hasil saat ini adalah sebagai berikut. Kritik yang diungkapkan mengenai teknologi SWITH pada suatu waktu relevan dan terkini. Ini juga berlaku untuk paket Stateflow. Dalam teknologi SWITH, tidak ada, dan tidak ada definisi yang jelas tentang pemrograman otomatis, pendekatan implementasi automata tidak berubah, modelnya sendiri tidak klasik, tidak ada model komputasi paralel, dll. dll. Tanpa menghilangkan masalah-masalah ini, pemrograman otomatis semacam itu paling-paling mengklaim peran yang cukup terbatas.

Alasan untuk masalah yang disebutkan di atas cukup jelas: teori program diabaikan, teori automata dilupakan, meskipun banyak kata yang baik dan benar dikatakan tentang automata itu sendiri dan sifat-sifatnya yang indah. Tetapi sebenarnya ini adalah mesin lain. Penulis yakin akan keragu-raguan upaya yang dikandung untuk membuat model asli. Ini tentang model sinkron, reaktif dan lainnya. Mereka bisa nyaman ketika memecahkan kelas masalah yang sempit dan tidak lebih. Tetapi yang lebih serius adalah bahwa mereka jatuh dari teori automata tanpa memiliki teori mereka sendiri. Tetapi model di luar teori tidak berdaya, dan karenanya hampir tidak ada artinya.