BADAN FEDERAL UNTUK PENDIDIKAN LEMBAGA PENDIDIKAN NEGARA PENDIDIKAN PROFESIONAL TINGGI "UNVERSITAS NEGARA VORONEZH" T.K. Katsaran, L.N. MESIN TURING Stroeva DAN FUNGSI REKURSIF Buku teks untuk universitas Pusat Penerbitan dan Percetakan Universitas Negeri Voronezh 2008 Disetujui oleh dewan ilmiah dan metodologi fakultas PMM pada tanggal 25 Mei 2008, protokol No. 9 Reviewer Doktor Ilmu Teknik, Prof. Departemen Metode Matematika Riset Operasi T.M. Ledeneva Buku teks ini disiapkan di Departemen Osilasi Nonlinier, Fakultas Matematika Mekanik, Universitas Negeri Voronezh. Direkomendasikan untuk mahasiswa tahun pertama Fakultas Matematika Terapan dan Matematika VSU, cabang VSU Starooskolsky dan Liskinsky. Untuk spesialisasi 010500 – Matematika terapan dan ilmu komputer PENDAHULUAN Kata “algoritma” berasal dari algoritma – ejaan Latin dari nama ahli matematika dan astronom Uzbekistan yang hidup pada abad ke-8 hingga ke-9 (783–850), Muhammad ben Musa al- Khawarizmi. Ahli matematika terhebat dari Khorezm (sebuah kota di Uzbekistan modern) dikenal dengan nama ini di Eropa Abad Pertengahan. Dalam bukunya “On Indian Counting”, ia merumuskan aturan penulisan bilangan asli menggunakan angka Arab dan aturan pengoperasiannya. Kemudian konsep algoritma mulai digunakan dalam arti yang lebih luas dan tidak hanya dalam matematika. Bagi ahli matematika dan praktisi, konsep algoritma sangatlah penting. Dengan demikian, kita dapat mengatakan bahwa algoritma adalah resep yang tepat untuk melakukan sistem operasi tertentu dalam urutan tertentu untuk menyelesaikan semua masalah dengan tipe yang sama, menentukan urutan tindakan yang memastikan diperolehnya hasil yang diperlukan dari data awal. Perhatikan bahwa ini bukan definisi dari konsep "algoritma", tetapi hanya deskripsinya, makna intuitifnya. Algoritme dapat dirancang untuk dijalankan baik oleh seseorang atau oleh perangkat otomatis. Gagasan tentang suatu algoritma ini tidak ketat dari sudut pandang matematika, karena ia menggunakan konsep-konsep seperti "instruksi yang tepat" dan "data awal", yang, secara umum, tidak didefinisikan secara ketat. Fitur dari algoritma apa pun adalah kemampuannya untuk memecahkan kelas masalah tertentu. Misalnya, ini bisa berupa algoritme untuk menyelesaikan sistem persamaan linier, mencari jalur terpendek dalam grafik, dll. Membuat algoritme, bahkan yang paling sederhana sekalipun, adalah proses kreatif. Ini tersedia secara eksklusif untuk makhluk hidup, dan untuk waktu yang lama diyakini hanya tersedia untuk manusia. Hal lainnya adalah implementasi algoritma yang sudah ada. Hal itu dapat dititipkan kepada subjek atau objek yang tidak wajib mendalami hakikatnya, bahkan mungkin tidak mampu memahaminya. Subjek atau objek seperti ini biasa disebut dengan pelaku formal. Contoh pelaku formal adalah mesin cuci otomatis, yang secara ketat melakukan tindakan yang ditentukan, bahkan jika Anda lupa memasukkan bedak ke dalamnya. Seseorang juga dapat bertindak sebagai pelaku formal, tetapi pertama-tama, berbagai perangkat otomatis, termasuk komputer, adalah pelaku formal. Setiap algoritma dibuat dengan mempertimbangkan pemain yang sangat spesifik. Perbuatan yang dapat dilakukan oleh pelaku disebut perbuatan yang diperbolehkan. Serangkaian tindakan yang diizinkan membentuk sistem perintah pelaku. Algoritme harus berisi hanya tindakan-tindakan yang diperbolehkan untuk pelaku tertentu. Oleh karena itu, beberapa sifat umum algoritma biasanya dirumuskan untuk membedakan algoritma dari instruksi lainnya. Algoritme harus memiliki properti berikut. Kebijaksanaan (diskontinuitas, keterpisahan) – algoritme harus mewakili proses penyelesaian masalah sebagai eksekusi berurutan dari langkah-langkah sederhana (atau yang telah ditentukan sebelumnya). Setiap tindakan yang disediakan oleh algoritme dijalankan hanya setelah tindakan sebelumnya selesai dieksekusi. Kepastian - setiap aturan algoritma harus jelas, tidak ambigu dan tidak memberikan ruang untuk kesewenang-wenangan. Berkat properti ini, eksekusi algoritme bersifat mekanis dan tidak memerlukan instruksi atau informasi tambahan apa pun tentang masalah yang sedang dipecahkan. Efisiensi (keterbatasan) – algoritma harus mengarah pada penyelesaian masalah dalam sejumlah langkah yang terbatas. 4 Massiveness - algoritma penyelesaian masalah dikembangkan dalam bentuk umum, yaitu harus dapat diterapkan untuk kelas masalah tertentu yang hanya berbeda pada data awal. Dalam hal ini, data awal dapat dipilih dari area tertentu, yang disebut area penerapan algoritma. Teori algoritma adalah salah satu cabang matematika yang mempelajari sifat-sifat umum algoritma. Ada teori algoritma kualitatif dan metrik. Masalah utama teori kualitatif algoritma adalah masalah membangun suatu algoritma yang memiliki sifat-sifat tertentu. Masalah ini disebut masalah algoritmik. Teori metrik algoritma mengkaji algoritma dalam hal kompleksitasnya. Cabang teori algoritma ini juga dikenal sebagai teori kompleksitas algoritmik. Ketika mencari solusi terhadap beberapa permasalahan, diperlukan waktu yang cukup lama untuk menemukan algoritma yang sesuai. Contoh soal tersebut adalah: a) menunjukkan suatu metode yang dengannya, untuk rumus predikat apa pun, dalam sejumlah operasi yang terbatas seseorang dapat mengetahui apakah rumus tersebut benar atau tidak; b) apakah persamaan Diophantine (persamaan aljabar dengan koefisien bilangan bulat) dapat diselesaikan dalam bilangan bulat? Karena tidak mungkin menemukan algoritma untuk memecahkan masalah ini, muncul asumsi bahwa algoritma tersebut tidak ada sama sekali, yang terbukti: masalah pertama diselesaikan oleh A. Church, dan yang kedua oleh Yu.V. Matiyasevich dan G.V. Chudnovsky. Pada prinsipnya tidak mungkin membuktikan hal ini dengan menggunakan konsep intuitif suatu algoritma. Oleh karena itu, upaya telah dilakukan untuk memberikan definisi matematis yang tepat tentang konsep suatu algoritma. Pada pertengahan 30-an abad kedua puluh, S.K. Kleene, A.A. Markov, E. Post, A. Turing, A. Church dan lain-lain telah mengajukan berbagai definisi matematika 5 dari konsep algoritma. Selanjutnya, terbukti bahwa definisi matematika formal yang berbeda ini dalam beberapa hal setara: definisi tersebut menghitung himpunan fungsi yang sama. Hal ini menunjukkan bahwa fitur utama dari konsep intuitif suatu algoritma tampaknya ditangkap dengan benar dalam definisi ini. Selanjutnya, kita akan mempertimbangkan penyempurnaan matematis dari algoritma yang diusulkan oleh A. Turing, yang disebut mesin Turing. 6 1. MESIN TURING § 1. Model matematika mesin Turing Gagasan untuk menciptakan mesin Turing, yang dikemukakan oleh ahli matematika Inggris A. Turing pada tahun tiga puluhan abad ke-20, dikaitkan dengan upayanya untuk memberikan a definisi matematis yang tepat dari konsep suatu algoritma. Mesin Turing (MT) adalah model matematika dari komputer digital yang diidealkan. Mesin Turing adalah objek matematika yang sama dengan fungsi, turunan, integral, grup, dll. Sama seperti konsep matematika lainnya, konsep mesin Turing mencerminkan realitas objektif dan memodelkan proses nyata tertentu. Untuk menggambarkan algoritma MT, akan lebih mudah untuk membayangkan sebuah perangkat yang terdiri dari empat bagian: tape, read head, perangkat kontrol dan memori internal. 1. Rekaman itu diasumsikan berpotensi tak terbatas, dibagi menjadi sel-sel (sel yang sama). Jika perlu, sel kosong dilampirkan ke sel pertama atau terakhir tempat simbol berada. Mesin beroperasi dalam waktu yang dianggap diskrit, dan momennya diberi nomor 1, 2, 3,…. Setiap saat rekaman itu berisi sejumlah sel yang terbatas. Hanya satu simbol (huruf) dari alfabet luar A = (L, a1 , a 2 ,..., a n -1 ), n ³ 2 yang dapat ditulis ke dalam sel pada waktu diskrit. Sel kosong dilambangkan dengan simbol L, dan simbol L itu sendiri disebut kosong, sedangkan simbol lainnya disebut tidak kosong. Dalam alfabet A ini, informasi yang diberikan ke MT dikodekan dalam bentuk sebuah kata (sekumpulan simbol terurut berhingga). Mesin tersebut “memproses” informasi yang disajikan dalam bentuk kata menjadi kata baru. 2. Kepala pembaca (elemen pembaca tertentu) bergerak sepanjang pita sehingga pada setiap saat ia melihat tepat satu sel pita. Kepala dapat membaca isi sel dan menulis karakter baru dari alfabet A. Dalam satu siklus operasi, ia hanya dapat memindahkan satu sel ke kanan (R), kiri (L) atau tetap di tempatnya (N ). Mari kita nyatakan himpunan gerakan (pergeseran) kepala D = (P, L, N). Jika pada saat tertentu t kepala berada di sel terluar dan berpindah ke sel yang hilang, maka sel kosong baru ditambahkan, di atasnya kepala akan berada pada saat t + 1. 3. Memori internal mesin adalah himpunan keadaan internal tertentu yang terbatas Q = ( q0 , q1 , q 2 , ..., q m ), m ³ 1 . Kita asumsikan pangkat |Q | ³ 2. Dua keadaan mesin mempunyai arti khusus: q1 adalah keadaan internal awal (dapat ada beberapa keadaan internal awal), q0 adalah keadaan akhir atau keadaan berhenti (selalu ada satu keadaan akhir). Pada setiap momen waktu, MT dicirikan oleh kedudukan pemimpin dan keadaan internal. Misalnya, di bawah sel tempat kepala berada, keadaan internal mesin ditunjukkan. ¯ a2 a1 L a2 a3 q1 4. Pada setiap momen t, perangkat kontrol, bergantung pada simbol pada pita yang dibaca pada saat itu dan keadaan internal mesin, melakukan tindakan berikut: 1) mengubah simbol ai yang dibaca saat ini t ke simbol baru a j (khususnya, biarkan tidak berubah, yaitu ai = a j); 2) menggerakkan kepala ke salah satu arah berikut: N, L, R; 3) mengubah keadaan internal mesin 8 qi yang ada pada saat t menjadi q j baru dimana mesin akan berada pada waktu t +1 (bisa jadi qi = q j). Tindakan perangkat kendali seperti itu disebut perintah, yang dapat ditulis dalam bentuk: qi ai ® a j D q j , (1) di mana qi adalah keadaan internal mesin saat ini; a i – simbol yang sedang dibaca saat ini; a j – simbol yang diubah oleh simbol a i (dapat berupa ai = a j); simbol D adalah N, atau L, atau P dan menunjukkan arah pergerakan kepala; q j adalah keadaan internal mesin pada saat berikutnya (mungkin qi = q j). Ekspresi qi ai dan a j D q j masing-masing disebut sisi kiri dan kanan perintah ini. Banyaknya perintah yang ruas kirinya berbeda berpasangan adalah bilangan berhingga, karena himpunan Q \ (q 0 ) dan A berhingga. Tidak ada perintah dengan sisi kiri yang identik, yaitu jika program mesin T berisi ekspresi qi ai ® a j D q j dan qt di ® ak D qk , lalu qi ¹ qt atau ai ¹ at dan DO (P, L, N ). Himpunan semua instruksi disebut program mesin Turing. Jumlah maksimum perintah dalam suatu program adalah (n + 1) x m, dimana n + 1 = A dan m + 1 = Q. Dipercayai bahwa keadaan akhir dari perintah q0 hanya dapat muncul di sisi kanan perintah, keadaan awal q1 dapat muncul di sisi kiri dan kanan perintah. Mengeksekusi satu perintah disebut langkah. Komputasi (atau pengoperasian) mesin Turing merupakan rangkaian langkah satu demi satu tanpa ada lompatan, dimulai dari langkah pertama. Jadi, MT diberikan jika empat himpunan berhingga diketahui: alfabet eksternal A, alfabet internal Q, himpunan D gerakan kepala, dan program mesin, yang merupakan himpunan perintah berhingga. 9 § 2. Pengoperasian mesin Turing Pengoperasian mesin sepenuhnya ditentukan oleh tugas pada saat pertama (awal): 1) kata-kata pada pita, yaitu rangkaian simbol yang ditulis dalam sel pita (a kata diperoleh dengan membaca simbol-simbol ini melintasi sel-sel pita dari kiri ke kanan); 2) posisi kepala; 3) keadaan internal mesin. Kombinasi ketiga kondisi tersebut (saat ini) disebut konfigurasi (saat ini). Biasanya, pada saat awal, keadaan internal mesin adalah q1, dan head berada di atas sel kiri pertama atau kanan pertama pada pita. Kata tertentu pada pita dengan keadaan awal q1 dan posisi kepala di atas kata pertama disebut konfigurasi awal. Jika tidak, kami mengatakan bahwa mesin Turing tidak berlaku untuk konfigurasi awal. Dengan kata lain, pada saat awal konfigurasinya dapat direpresentasikan dalam bentuk berikut: pada pita yang terdiri dari sejumlah sel tertentu, di setiap sel ditulis salah satu simbol alfabet luar A, kepalanya terletak di atas yang pertama. sel kiri atau kanan pertama dari pita dan bagian dalam.posisi mesin adalah q1. Kata yang dihasilkan pada tape dan posisi kepala yang dihasilkan dari implementasi perintah ini disebut konfigurasi akhir. Misalnya, jika pada saat awal tertulis kata a1La 2 a1a1 pada pita, maka konfigurasi awal akan terlihat seperti: a1 a2 L a1 a1 q1 (di bawah sel tempat kepala berada, keadaan internal mesin ditunjukkan). 10

Topik “Mesin Turing” dalam kursus ilmu komputer sekolah

DI DALAM. Falina,
Moskow

Dalam banyak buku teks ilmu komputer, ketika mempelajari konsep dan sifat-sifat suatu algoritma, terdapat ungkapan-ungkapan yang isinya sebagai berikut: “...ada banyak cara berbeda untuk menulis algoritma yang sama, misalnya menulis dalam bentuk teks, menulis dalam bentuk diagram alur, penulisan dalam beberapa bahasa algoritmik, representasi suatu algoritma dalam bentuk mesin Turing atau mesin Post…” Sayangnya, frasa seperti ini adalah satu-satunya yang menyebutkan mesin Turing. Tidak diragukan lagi, jumlah jam yang dicurahkan untuk mempelajari algoritma tidak memungkinkan kita untuk memasukkan dalam topik ini studi tentang cara menulis algoritma dalam bentuk mesin Turing. Namun topik ini sangat menarik, penting dan bermanfaat bagi anak sekolah, terutama yang tertarik dengan ilmu komputer.

Topik “Mesin Turing” dapat dipelajari di kelas 8–11 sebagai bagian dari topik “Proses Informasi. Pemrosesan informasi”, di kelas pilihan, dalam sistem pendidikan tambahan, misalnya, di sekolah untuk programmer muda. Pembelajaran topik ini dapat disertai dengan dukungan komputer jika guru memiliki perangkat lunak simulator “Mesin Turing”. Di kelas pemrograman tingkat lanjut, siswa dapat secara mandiri menulis program Mesin Turing. Sebagai bagian dari artikel ini, kami menawarkan kepada Anda lokakarya tentang pemecahan masalah dengan topik “Mesin Turing”. Materi teori tentang topik ini telah dimuat lebih dari satu kali di halaman surat kabar Informatika, misalnya pada artikel No. 3/2004 oleh I.N. Falina “Elemen Teori Algoritma”.

Mesin Turing adalah konstruksi matematika yang ketat, peralatan matematika (mirip, misalnya, dengan peralatan persamaan diferensial), yang dibuat untuk memecahkan masalah tertentu. Peralatan matematika ini disebut “mesin” karena dari segi gambaran bagian-bagian penyusunnya dan cara kerjanya mirip dengan komputer. Perbedaan mendasar antara mesin Turing dan komputer adalah perangkat penyimpanannya merupakan pita tak terbatas: di komputer sebenarnya, perangkat penyimpanan bisa sebesar yang Anda suka, namun harus terbatas. Mesin Turing tidak dapat direalisasikan secara tepat karena pitanya tidak terbatas. Dalam hal ini, ia lebih kuat daripada mesin komputasi mana pun.

Setiap mesin Turing memiliki dua bagian:

1)tak terbatas perjalanan pulang pergi pita, dibagi menjadi sel;

2) mesin(kepala baca/tulis dikendalikan oleh perangkat lunak).

Setiap mesin Turing dikaitkan dengan dua huruf terakhir: alfabet simbol masukan A = (a 0 , a 1 , ..., am ) dan alfabet keadaan Q = (q 0 , q 1 , ..., q p ). (Mesin Turing yang berbeda mungkin memiliki alfabet berbeda yang terkait dengannya A Dan Q.) Keadaan q 0 disebut pasif. Hal ini diyakini bahwa jika mesin masuk ke keadaan ini, maka ia telah menyelesaikan pekerjaannya. Keadaan q 1 disebut awal. Saat dalam keadaan ini, mesin mulai bekerja.

Kata masukan ditempatkan pada pita satu huruf pada satu waktu dalam sel yang berurutan. Di sebelah kiri dan kanan kata masukan hanya terdapat sel kosong (sesuai abjad A selalu menyertakan surat kosong A 0 adalah tanda bahwa sel tersebut kosong).

Mesin dapat bergerak sepanjang pita ke kiri atau ke kanan, membaca isi sel dan menulis huruf ke dalam sel. Di bawah ini adalah gambar skema mesin Turing, yang robotnya memeriksa sel pertama dengan data.

Mesin “melihat” hanya satu sel setiap kali. Tergantung suratnya yang mana ai dia melihat, dan juga tergantung pada kondisinya qj Mesin dapat melakukan tindakan berikut:

• · menulis surat baru di sel yang diamati;
• · menggeser pita satu sel ke kanan/kiri atau tetap tidak bergerak;
• · pindah ke negara bagian baru.

Artinya, mesin Turing mempunyai tiga jenis operasi. Setiap kali untuk pasangan berikutnya ( qj, sebuah saya) mesin Turing menjalankan perintah yang terdiri dari tiga operasi dengan parameter tertentu.

Program mesin Turing adalah tabel dengan perintah yang ditulis di setiap sel.

Sel ( qj, sebuah saya) ditentukan oleh dua parameter - simbol alfabet dan status mesin. Perintah tersebut merupakan indikasi: ke mana harus memindahkan kepala baca/tulis, karakter apa yang akan ditulis ke sel saat ini, status mesin yang harus digunakan. Untuk menunjukkan arah pergerakan mesin, kami menggunakan salah satu dari tiga huruf: “L” (kiri), “P” (kanan) atau “N” (diam).

Setelah mesin menjalankan perintah berikutnya, mesin masuk ke status qm(yang dalam kasus tertentu mungkin bertepatan dengan keadaan sebelumnya qj). Perintah selanjutnya harus ditemukan di M baris tabel pada perpotongan dengan kolom Al(surat Al mesin melihat setelah shift).

Mari kita sepakat bahwa ketika rekaman itu berisi kata masukan, maka mesin ditempatkan pada sel tertentu di negara bagian Q 1. Selama operasi, otomat akan melompat dari satu sel program (tabel) ke sel lain hingga mencapai sel yang di dalamnya tertulis bahwa otomat harus masuk ke keadaan Q 0 . Sel-sel ini disebut menghentikan sel. Setelah mencapai sel tersebut, mesin Turing berhenti.

Meskipun desainnya sederhana, mesin Turing dapat melakukan semua kemungkinan transformasi kata, sehingga mengimplementasikan semua algoritma yang mungkin.

Contoh. Anda perlu membuat mesin Turing yang menambahkan satu ke nomor pada kaset. Kata masukan terdiri dari angka bilangan bulat desimal yang ditulis ke dalam sel berurutan pada pita. Pada saat awal, mesin terletak di seberang digit paling kanan dari nomor tersebut.

Larutan. Mesin harus menambahkan satu ke digit terakhir nomor tersebut. Jika angka terakhirnya 9, gantilah dengan 0 dan tambahkan satu pada angka sebelumnya. Sebuah program untuk mesin Turing tertentu mungkin terlihat seperti ini:

Di mesin Turing ini Q 1 - status perubahan digit, Q 0 - keadaan berhenti. Jika kamu bisa q aku mesin melihat angka 0..8, lalu menggantinya dengan 1..9, dan masuk ke status Q 0, yaitu mobil berhenti. Jika dia melihat angka 9, maka dia menggantinya dengan 0, bergerak ke kiri, tetap dalam keadaan q aku. Hal ini berlanjut hingga mesin menemukan angka yang kurang dari 9. Jika semua angka tersebut sama dengan 9, maka mesin akan menggantinya dengan nol, tulis 0 sebagai pengganti angka tertinggi, pindah ke kiri dan tulis 1 di sel kosong. Kemudian akan masuk ke negara bagian Q 0, yaitu akan berhenti.

Tugas praktis

1. Pita mesin Turing berisi rangkaian simbol “+”. Tulis program untuk mesin Turing yang setiap detiknya mengganti simbol “+” dengan “–”. Penggantian dimulai dari ujung kanan urutan. Mesinnya mampu Q 1 melihat salah satu karakter dalam urutan yang ditentukan. Selain program tabel itu sendiri, jelaskan dengan kata-kata apa yang dilakukan oleh mesin di setiap negara bagian.

2. Diberi nomor N dalam sistem bilangan oktal. Rancang mesin Turing yang menambah bilangan tertentu N pada 1. Mesin mampu Q 1 melihat digit tertentu dari kata masukan. Selain program tabel itu sendiri, jelaskan dengan kata-kata apa yang dilakukan oleh mesin di setiap negara bagian.

3. Diberikan notasi desimal suatu bilangan asli N> 1. Kembangkan mesin Turing yang dapat mengurangi bilangan tertentu N pada 1. Mesin mampu Q 1 melihat digit kanan nomor tersebut. Selain program tabel itu sendiri, jelaskan dengan kata-kata apa yang dilakukan oleh mesin di setiap negara bagian.

4. Diberikan bilangan asli N> 1. Kembangkan mesin Turing yang dapat mengurangi bilangan tertentu N dengan 1, sedangkan angka paling signifikan pada kata keluaran tidak boleh 0. Misalnya, jika kata masukan adalah “100”, maka kata keluarannya harus “99”, bukan “099”. Mesinnya mampu Q 1 melihat digit kanan nomor tersebut. Selain program tabel itu sendiri, jelaskan dengan kata-kata apa yang dilakukan oleh mesin di setiap negara bagian.

5. Diberikan deretan tanda kurung buka dan tutup. Bangun mesin Turing yang akan menghilangkan pasangan tanda kurung bersama, mis. terletak pada baris “()”.

Misalnya, jika diberi “) (() (()”, Anda perlu mendapatkan “) . . . ((”.

Mesinnya mampu Q

6. Diberi rangkaian huruf “ A" Dan " B" Kembangkan mesin Turing yang akan memindahkan semua huruf “ A” ke kiri, dan huruf “ B” - ke sisi kanan garis. Mesinnya mampu Q 1 melihat karakter paling kiri dari baris tersebut. Selain program tabel itu sendiri, jelaskan dengan kata-kata apa yang dilakukan oleh mesin di setiap negara bagian.

7. Pada pita mesin Turing terdapat bilangan yang ditulis dengan sistem bilangan desimal. Kalikan angka ini dengan 2. Mesin mampu Q 1 melihat digit paling kiri dari nomor tersebut. Selain program tabel itu sendiri, jelaskan dengan kata-kata apa yang dilakukan oleh mesin di setiap negara bagian.

8. Diberikan dua bilangan asli M Dan N, disajikan dalam sistem bilangan unary. Kumpulan karakter yang cocok adalah “|” dipisahkan oleh sel kosong. Mesinnya mampu Q 1 melihat karakter paling kanan dari urutan masukan. Kembangkan mesin Turing yang akan meninggalkan sejumlah angka pada kaset M Dan N. Selain program tabel itu sendiri, jelaskan dengan kata-kata apa yang dilakukan oleh mesin di setiap negara bagian.

9. Diberikan dua bilangan asli M Dan N, disajikan dalam sistem bilangan unary. Kumpulan karakter yang cocok adalah “|” dipisahkan oleh sel kosong. Mesinnya mampu Q 1 melihat karakter paling kanan dari urutan masukan. Kembangkan mesin Turing yang akan meninggalkan perbedaan angka pada pita. M Dan N. Diketahui bahwa M> N. Selain program tabel itu sendiri, jelaskan dengan kata-kata apa yang dilakukan oleh mesin di setiap negara bagian.

10. Terdapat angka desimal pada pita mesin Turing. Tentukan apakah bilangan tersebut habis dibagi 5 tanpa sisa. Jika habis dibagi, tulislah kata “ya” di sebelah kanan bilangan tersebut, jika tidak “tidak”. Mesin memeriksa digit tertentu dari nomor masukan. Selain program tabel itu sendiri, jelaskan dengan kata-kata apa yang dilakukan oleh mesin di setiap negara bagian.

Mampu Q 1 mesin mencari ujung kanan angka, mampu Q 2 - lewati tanda “+”, ketika mencapai akhir urutan - berhenti. Mampu Q 3, mesin mengganti tanda “+” dengan tanda “–”, dan ketika mencapai akhir urutan, mesin berhenti.

Solusi untuk masalah ini mirip dengan contoh yang dibahas di atas.

Negara Q 1 - angka terendah (berikutnya) kita kurangi dengan 1. Jika tidak sama dengan nol, maka segera hentikan setelah penurunan, jika angka terendah adalah 0, maka kita tulis 9, geser ke kiri dan lakukan pengurangan lagi . Didalam sangkar [ A 0 , Q 1 ] mesin Turing tidak akan pernah terkena, sehingga dapat dibiarkan tidak terisi.

Tugas 4 (komplikasi tugas 3)

Negara Q 1 - angka minor (berikutnya) kita kurangi dengan 1. Jika lebih besar dari 1, maka setelah pengurangan kita langsung berhenti, tetapi jika angka minornya 0, maka kita tulis 9 saja, geser ke kiri dan lakukan pengurangan lagi. Jika angka yang dikurangi adalah 1, maka kita tulis 0 saja dan masuk ke keadaan Q 2 .

Negara Q 2 - setelah menulis "0" di posisi mana pun, perlu untuk menganalisis apakah angka nol ini adalah angka paling signifikan (yaitu, apakah angka tersebut berada di sebelah kirinya dalam catatan kata keluaran A 0).

Negara Q 3 - jika “0” yang tercatat adalah angka paling berarti, maka harus dikeluarkan dari catatan kata keluaran.

Sel-sel yang tidak pernah dimasuki oleh mesin Turing dibiarkan kosong.

Negara Q 1: jika “(” ditemukan, maka geser ke kanan dan lanjutkan ke keadaan Q 2 ; jika kamu bertemu “ A 0”, lalu berhenti.

Negara Q 2: analisis simbol “(” untuk berpasangan, jika berpasangan mereka akan melihat “)”. Jika itu ruang uap, kembali ke kiri dan pergi ke negara bagian Q 3 .

Negara Q 3: pertama-tama hapus “(”, lalu “)” dan lanjutkan ke Q 1 .

Penyelesaian masalah ini biasanya menimbulkan kesulitan bagi anak sekolah. Saat menganalisis solusi untuk masalah ini, Anda dapat melakukan, misalnya, dengan cara berikut.

Tinjau opsi berikut untuk kata masukan bersama siswa Anda dan mintalah mereka merumuskan apa yang harus dilakukan mesin Turing, seperti apa kata keluarannya, dan apa perbedaan opsi ini dari sudut pandang mesin Turing:

aaa ->

a -> kata keluaran cocok dengan kata masukan, kita lihat kata masukannya sampai habis.

bbb -> kata keluaran cocok dengan kata masukan, kita lihat kata masukannya sampai habis.

b -> kata keluaran cocok dengan kata masukan, kita lihat kata masukannya sampai habis.

ab -> kata keluaran cocok dengan kata masukan, kita lihat kata masukannya sampai habis.

Hasil diskusi. Mesin Turing harus “memahami” rantai huruf mana yang diikutinya, mis. itu harus memiliki setidaknya dua negara bagian. Biarkan negara Q 1 - gerakan sepanjang rantai huruf “ A", A Q 2 - keadaan pergerakan sepanjang rantai huruf “ B" Perhatikan bahwa rantai juga bisa terdiri dari satu huruf. Jika kita sudah mencapai garis akhir di negara bagian tersebut Q 1 atau Q 2, yaitu bertemu A 0, mesin harus berhenti, kami telah memproses seluruh baris.

Pertimbangkan opsi berikut untuk memasukkan kata-kata:

sayang -> abb

bbbab -> aabbbb

aabbbaab -> aaaaabbbb

Hasil diskusi. Versi pertama dari kata masukan dapat diproses secara berurutan sebagai berikut: bba -> bbb-> kembali ke ujung kiri rantai surat “ B” -> abb(ganti huruf pertama dalam rantai ini dengan “ A"). Untuk melakukan tindakan ini, kita perlu memperkenalkan dua negara bagian baru dan, sebagai tambahan, memperjelas negara bagian tersebut Q 2. Oleh karena itu, untuk mengatasi masalah ini kita perlu membangun mesin Turing dengan kondisi sebagai berikut:

q 1 - ke kanan sepanjang rantai huruf “ A" Jika rantainya berakhir A 0, lalu pergi ke Q 0 ; jika diakhiri dengan huruf “ B”, lalu kita pergi ke Q 2 ;

q 2 - ke kanan sepanjang rantai huruf “ B” jika rantainya berakhir A 0, lalu pergi ke Q 0 ; jika berakhir “ A”, lalu ganti huruf “ A" pada " B”, pergi ke negara bagian Q 3 (rantai spesies digantikan oleh rantai spesies);

q 3 - ke kiri sepanjang rantai huruf “ B” di ujung kirinya. Jika Anda bertemu A 0 atau “ A”, lalu kita pergi ke Q 4 ;

q 4 - ganti “ B" pada " A” dan pergi ke Q 1 (ganti rantai bentuk dengan rantai bentuk .

Masalah 7

negara Q 1 - mencari digit kanan (terendah) suatu angka;

negara Q 2 - mengalikan digit berikutnya dari suatu angka dengan 2 tanpa menambahkan 1 carry;

negara Q 3 - mengalikan digit berikutnya dari suatu angka dengan 2 dengan penambahan 1 carry.

Mesin Turing untuk program ini terlihat sederhana - hanya memiliki satu keadaan. Mesin Turing seperti itu melakukan tindakan berikut: menghapus guratan paling kanan, mencari pemisah (sel kosong) dan menempatkan guratan di sel kosong ini, sehingga membentuk rangkaian guratan panjang yang berkesinambungan. N + M.

Namun anehnya, penyelesaian masalah ini menimbulkan kesulitan besar. Sangat sering, siswa membuat mesin Turing yang melakukan tindakan siklik: mendorong ke kanan secara berurutan N pukulan ke kiri.

Dalam hal ini, program mereka terlihat seperti ini:

negara Q 1 - cari pemisah;

negara Q 2 - memindahkan pukulan;

negara Q 3 - periksa bagian akhir (apakah semua pukulan telah dipindahkan).

Contoh masalah ini dengan jelas menunjukkan betapa seringnya anak-anak mencoba memecahkan suatu masalah dengan cara yang sudah biasa mereka lakukan. Tampak bagi saya bahwa dengan menawarkan masalah kepada siswa untuk membuat mesin Turing, kita mengembangkan kemampuan untuk menemukan solusi yang tidak biasa dan mengembangkan kemampuan berpikir kreatif!

Tugas ini tampaknya cukup mudah bagi anak sekolah, tetapi timbul kesulitan dalam menghentikan mesin Turing. Di bawah ini adalah salah satu kemungkinan versi mesin Turing untuk tugas ini.

Ide solusi (kondisi berhenti). Ada dua susunan guratan awal pada rekaman itu.

Kita mulai menghapus guratan dari ujung kiri array M. Dan satu per satu kita menghapus goresan paling kiri dalam array M dan goresan paling kanan dalam larik N. Namun sebelum menghapus goresan kanan pada array N, kami memeriksa apakah itu satu-satunya (yaitu yang terakhir yang perlu dihapus) atau tidak.

Mari kita jelaskan dulu keadaan mesin Turing yang diperlukan untuk memecahkan masalah kita, dan kemudian buat program tabel.

Negara Q 1 - mencari pemisah antara susunan guratan saat berpindah dari kanan ke kiri;

negara Q 2 - mencari goresan kiri dalam larik M;

negara Q 3 - menghapus goresan kiri pada larik M;

negara Q 4 - mencari pemisah saat bergerak dari kiri ke kanan;

negara Q 5 - mencari goresan yang tepat dalam larik N;

negara Q 6 - memeriksa keunikan pukulan ini dalam array N, yaitu tentukan apakah itu yang terakhir;

negara Q 7 - jika itu yang terakhir, maka hentikan, jika tidak, lanjutkan ke siklus eksekusi algoritma yang baru.

Saat memecahkan masalah ini, Anda harus memperhatikan ejaan alfabet yang benar:

SEBUAH = ( A 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, D, A, N, E, T).

Negara Q 1 - cari ujung kanan nomor;

negara Q 2 - analisis digit terkecil dari angka tersebut; jika sama dengan “0” atau “5”, mis. bilangan tersebut habis dibagi 5, lalu beralih ke keadaan Q 3 , jika tidak, transisi ke status Q 5 ;

negara Q 3 - tulis huruf "D" di sebelah kanan kata pada pita;

negara Q 4 - tulis huruf "A" di sebelah kanan kata dan hentikan mesin;

negara Q 5 - menulis huruf “N” di sebelah kanan kata;

negara Q 6 - menulis huruf "E" di sebelah kanan kata;

negara Q 7 - tulis huruf “T” di sebelah kanan kata dan hentikan mesin.

Properti mesin Turing sebagai suatu algoritma

Dengan menggunakan mesin Turing sebagai contoh, sifat-sifat algoritma dapat terlihat dengan jelas. Mintalah siswa untuk menunjukkan bahwa mesin Turing memiliki semua sifat algoritma.

Kebijaksanaan. Mesin Turing dapat menuju ke ( k+ 1) langkah ke-hanya setelah selesai Ke- langkah ke-th, karena tepat Ke- langkah ke- menentukan apa yang akan terjadi ( k+ 1) langkah ke-1.

Kejelasan. Pada setiap langkah, simbol alfabet ditulis ke dalam sel, robot membuat satu gerakan (L, P, N), dan mesin Turing memasuki salah satu keadaan yang dijelaskan.

Determinisme. Setiap sel tabel mesin Turing hanya berisi satu opsi untuk suatu tindakan. Pada setiap langkah, hasilnya ditentukan secara unik, oleh karena itu urutan langkah penyelesaian masalah ditentukan secara unik, yaitu. Jika mesin Turing diberikan kata masukan yang sama, maka kata keluarannya akan selalu sama.

Produktifitas. Dalam hal konten, hasil dari setiap langkah dan seluruh urutan langkah didefinisikan secara unik; oleh karena itu, mesin Turing yang ditulis dengan benar akan masuk ke keadaan dalam jumlah langkah yang terbatas. Q 0, yaitu dalam beberapa langkah yang terbatas jawaban atas pertanyaan masalah akan diperoleh.

Karakter massa. Setiap mesin Turing didefinisikan untuk semua kata yang dapat diterima dari alfabet, ini adalah properti karakter massal. Setiap mesin Turing dirancang untuk memecahkan satu kelas masalah, yaitu. Untuk setiap soal, mesin Turingnya sendiri (baru) ditulis.

DARI REDAKSI

Semua masalah yang diberikan dalam artikel dapat diselesaikan hanya di buku catatan dengan menggambar strip informasi dan program tabel. Namun Anda dapat membuat proses ini lebih menyenangkan dan visual: gunakan implementasi mesin - penerjemah mesin Post dan mesin Turing “Algo2000”, yang dibuat oleh Radik Zartdinov. Program ini memiliki antarmuka yang intuitif, dan persyaratannya paling moderat: komputer IBM PC AT 486 atau lebih tinggi, sistem operasi Windows 95/98/NT.

Mari kita lihat secara umum cara kerja “Algo2000”.

Di menu program, pilih item Penerjemah dan tunjukkan mesin mana yang ingin kami gunakan (dalam kasus kami, ini adalah "mesin Turing").

Bidang mesin Turing akan muncul di depan kita.

Sekarang Anda perlu mengatur alfabet eksternal, mis. Di barisan Alfabet eksternal menunjukkan karakter mana yang termasuk di dalamnya (jika string Alfabet eksternal tidak terlihat, Anda perlu memilih item menu Lihat | Alfabet eksternal). Setiap karakter hanya dapat ditentukan satu kali. Setelah selesai memasukkan alfabet luar, kolom pertama tabel terbentuk: diisi dengan karakter dari alfabet luar dalam urutan yang sama. Saat mengedit alfabet eksternal, tabel diubah secara otomatis: baris disisipkan, dihapus, atau ditukar.

Jangan lupa bahwa Anda perlu mengatur simbol alfabet eksternal menjadi beberapa bagian pita (Anda dapat membiarkan semua bagian kosong) dan menempatkan kereta di seberang salah satu bagian, mis. Anda perlu mengatur program dan beberapa kondisi mesin.

Sekarang Anda dapat melanjutkan langsung ke penulisan algoritma untuk menyelesaikan masalah. Dinyatakan dalam bentuk tabel: karakter alfabet internal dimasukkan di setiap kolom baris atas, dan karakter alfabet eksternal dimasukkan di setiap baris kolom pertama. Perintah ditempatkan di sel di persimpangan kolom dan baris lainnya. Jika di perpotongan baris dan kolom mana pun kita mendapatkan sel kosong, ini berarti simbol ini tidak dapat ditemukan dalam keadaan internal ini.

Misalnya kita membuat algoritma untuk mencari selisih dua bilangan bulat positif (dalam sistem bilangan desimal), jika diketahui bilangan pertama lebih besar dari bilangan kedua, dan terdapat tanda minus di antara keduanya.

Bidang program akan terlihat seperti ini:

Format perintah di setiap sel adalah aKq. Di Sini:
a adalah konten baru dari sel saat ini (simbol baru alfabet eksternal yang dimasukkan ke dalam sel saat ini), K adalah perintah mekanisme pita mesin Turing (kiri, kanan, berhenti), q adalah keadaan internal baru dari mesin Turing.

Tombol tersebut akan meluncurkan program. Jika eksekusi belum ditangguhkan, eksekusi selalu dimulai dari keadaan internal nol Q0.

Program ini dapat diselesaikan langkah demi langkah. Untuk melakukan ini, klik tombol pada toolbar (jika tombol tidak terlihat, Anda perlu memilih item menu Lihat | Bilah Alat) atau pilih dari menu utama Mulai | Selangkah demi selangkah. Jika Anda perlu menghentikan eksekusi program sepenuhnya, ini dapat dilakukan dengan menggunakan tombol pada toolbar atau menggunakan menu utama ( Mulai | Menggugurkan). Barang menu Kecepatan memungkinkan Anda untuk mengatur kecepatan eksekusi program.

Program akan terus dijalankan hingga perintah “Stop” ditemukan atau terjadi kesalahan.

Jika Anda mempunyai pertanyaan saat bekerja dengan program juru bahasa, silakan merujuk ke file bantuan Algo2000.hlp. Ini, serta program “Algo2000” itu sendiri, dapat ditemukan di situs web surat kabar “Informatika” http://inf.1september.ru di bagian “Unduh”.

Kecerdasan buatan (AI, Bahasa Inggris: Artificial Intelligence, AI) - ilmu dan teknologi untuk menciptakan mesin cerdas, khususnya program komputer cerdas. AI terkait dengan tugas serupa dalam menggunakan komputer untuk memahami kecerdasan manusia, namun tidak terbatas pada metode yang masuk akal secara biologis.

Apa itu kecerdasan buatan

Intelijen(dari Lat. intellectus - sensasi, persepsi, pemahaman, pemahaman, konsep, alasan), atau pikiran - kualitas jiwa yang terdiri dari kemampuan beradaptasi dengan situasi baru, kemampuan belajar dan mengingat berdasarkan pengalaman, memahami dan menerapkan konsep abstrak dan menggunakan pengetahuannya untuk pengelolaan lingkungan. Kecerdasan adalah kemampuan umum untuk mengetahui dan memecahkan kesulitan, yang menyatukan semua kemampuan kognitif manusia: sensasi, persepsi, memori, representasi, berpikir, imajinasi.

Pada awal tahun 1980an. Ilmuwan komputasi Barr dan Fajgenbaum mengusulkan definisi kecerdasan buatan (AI) berikut:

Belakangan, sejumlah algoritme dan sistem perangkat lunak mulai diklasifikasikan sebagai AI, yang ciri khasnya adalah mereka dapat memecahkan beberapa masalah dengan cara yang sama seperti yang dilakukan seseorang yang memikirkan solusinya.

Sifat utama AI adalah pemahaman bahasa, pembelajaran dan kemampuan berpikir dan, yang terpenting, bertindak.

AI adalah suatu kompleks teknologi dan proses terkait yang berkembang secara kualitatif dan pesat, misalnya:

• pemrosesan teks bahasa alami
• sistem pakar
• agen virtual (chatbots dan asisten virtual)
• sistem rekomendasi.

Strategi nasional pengembangan kecerdasan buatan

• Artikel utama: Strategi nasional pengembangan kecerdasan buatan

Penelitian AI

• Artikel utama: Penelitian Kecerdasan Buatan

Standardisasi dalam AI

2019: Pakar ISO/IEC mendukung proposal untuk mengembangkan standar dalam bahasa Rusia

Pada tanggal 16 April 2019 diketahui bahwa subkomite ISO/IEC untuk standardisasi di bidang kecerdasan buatan mendukung usulan Komite Teknis “Sistem siber-fisik”, yang dibentuk berdasarkan RVC, untuk mengembangkan “Kecerdasan Buatan” standar. Konsep dan terminologi" dalam bahasa Rusia selain versi dasar bahasa Inggris.

Standar terminologis “Kecerdasan buatan. Konsep dan terminologi" merupakan hal mendasar bagi seluruh rangkaian dokumen peraturan dan teknis internasional di bidang kecerdasan buatan. Selain istilah dan definisi, dokumen ini berisi pendekatan konseptual dan prinsip-prinsip untuk membangun sistem dengan elemen, deskripsi hubungan antara AI dan teknologi end-to-end lainnya, serta prinsip-prinsip dasar dan pendekatan kerangka kerja terhadap regulasi dan regulasi teknis. dari kecerdasan buatan.

Setelah pertemuan subkomite ISO/IEC terkait di Dublin, para ahli ISO/IEC mendukung usulan delegasi dari Rusia untuk secara bersamaan mengembangkan standar terminologi di bidang AI tidak hanya dalam bahasa Inggris, tetapi juga dalam bahasa Rusia. Dokumen tersebut diharapkan disetujui pada awal tahun 2021.

Dalam pertemuan tersebut, para ahli ISO/IEC juga mendukung pengembangan rancangan dokumen internasional Teknologi Informasi - Kecerdasan Buatan (AI) - Tinjauan Pendekatan Komputasi untuk Sistem AI, di mana Rusia bertindak sebagai co-editor. Dokumen tersebut memberikan gambaran umum tentang keadaan sistem kecerdasan buatan saat ini, menjelaskan karakteristik utama sistem, algoritme dan pendekatan, serta contoh aplikasi khusus di bidang AI. Pengembangan rancangan dokumen ini akan dilakukan oleh kelompok kerja 5 yang dibentuk khusus “Pendekatan komputasi dan karakteristik komputasi sistem AI” dalam subkomite (Kelompok Kerja SC 42 5 “Pendekatan komputasi dan karakteristik komputasi sistem AI”).

Teknologi kecerdasan buatan sangat diminati di berbagai sektor ekonomi digital. Salah satu faktor utama yang menghambat penerapan praktisnya adalah keterbelakangan kerangka peraturan. Pada saat yang sama, kerangka peraturan dan teknis yang dikembangkan dengan baiklah yang menjamin kualitas penerapan teknologi dan dampak ekonomi yang sesuai.

Di bidang kecerdasan buatan, TC Cyber-Physical Systems berbasis RVC sedang mengembangkan sejumlah standar nasional yang rencananya akan disetujui pada akhir tahun 2019 - awal tahun 2020. Selain itu, upaya sedang dilakukan bersama dengan pelaku pasar untuk merumuskan Rencana Standardisasi Nasional (NSP) untuk tahun 2020 dan seterusnya. TC "Sistem siber-fisik" terbuka untuk proposal pengembangan dokumen dari organisasi yang berkepentingan.

2018: Pengembangan standar di bidang komunikasi kuantum, AI, dan kota pintar

Pada tanggal 6 Desember 2018, Komite Teknis “Sistem Siber-Fisik” berdasarkan RVC bersama dengan Pusat Teknik Regional “SafeNet” mulai mengembangkan seperangkat standar untuk pasar Inisiatif Teknologi Nasional (NTI) dan ekonomi digital. Pada Maret 2019, direncanakan untuk mengembangkan dokumen standardisasi teknis di bidang komunikasi kuantum, dan, RVC melaporkan. Baca selengkapnya.

Dampak kecerdasan buatan

Risiko terhadap perkembangan peradaban manusia

Dampak terhadap perekonomian dan bisnis

• Dampak teknologi kecerdasan buatan terhadap perekonomian dan bisnis

Dampak terhadap pasar tenaga kerja

Bias Kecerdasan Buatan

Inti dari semua praktik AI (terjemahan mesin, pengenalan suara, pemrosesan bahasa alami, visi komputer, mengemudi otomatis, dan banyak lagi) adalah pembelajaran mendalam. Ini adalah bagian dari pembelajaran mesin, yang ditandai dengan penggunaan model jaringan saraf, yang dapat dikatakan meniru cara kerja otak, sehingga akan sulit untuk mengklasifikasikannya sebagai AI. Setiap model jaringan saraf dilatih pada kumpulan data yang besar, sehingga memperoleh beberapa “keterampilan”, namun cara penggunaannya masih belum jelas bagi pembuatnya, yang pada akhirnya menjadi salah satu masalah terpenting bagi banyak aplikasi pembelajaran mendalam. Alasannya adalah model seperti itu bekerja dengan gambar secara formal, tanpa pemahaman apa pun tentang fungsinya. Apakah sistem seperti itu AI dan dapatkah sistem yang dibangun berdasarkan pembelajaran mesin dapat dipercaya? Implikasi dari jawaban atas pertanyaan terakhir tidak hanya terbatas pada laboratorium ilmiah. Oleh karena itu, perhatian media terhadap fenomena yang disebut bias AI semakin meningkat. Ini dapat diterjemahkan sebagai “bias AI” atau “bias AI”. Baca selengkapnya.

Pasar Teknologi Kecerdasan Buatan

pasar AI di Rusia

Pasar AI global

Area penerapan AI

Area penerapan AI cukup luas dan mencakup teknologi yang sudah dikenal dan area baru yang sedang berkembang yang jauh dari penerapan massal, dengan kata lain, ini adalah keseluruhan solusi, mulai dari penyedot debu hingga stasiun luar angkasa. Anda dapat membagi semua keragamannya sesuai dengan kriteria poin-poin penting pembangunan.

AI bukanlah bidang studi yang monolitik. Selain itu, beberapa bidang teknologi AI muncul sebagai sub-sektor ekonomi baru dan entitas terpisah, sekaligus melayani sebagian besar bidang perekonomian.

Perkembangan penggunaan AI mengarah pada adaptasi teknologi di sektor ekonomi klasik di sepanjang rantai nilai dan mentransformasikannya, yang mengarah pada algoritmaisasi hampir semua fungsi, mulai dari logistik hingga manajemen perusahaan.

Pemanfaatan AI untuk Urusan Pertahanan dan Militer

Gunakan dalam pendidikan

Menggunakan AI dalam bisnis

AI dalam perang melawan penipuan

Pada 11 Juli 2019 diketahui bahwa hanya dalam dua tahun kecerdasan buatan dan pembelajaran mesin akan digunakan untuk memerangi penipuan tiga kali lebih sering dibandingkan pada Juli 2019. Data tersebut diperoleh selama studi bersama oleh SAS dan Association of Certified Fraud Examiners (ACFE). Pada bulan Juli 2019, alat anti-penipuan tersebut telah digunakan di 13% organisasi yang ikut serta dalam survei ini, dan 25% lainnya mengatakan bahwa mereka berencana untuk menerapkannya dalam satu atau dua tahun ke depan. Baca selengkapnya.

AI di industri tenaga listrik

• Pada tingkat desain: peningkatan perkiraan pembangkitan dan permintaan sumber daya energi, penilaian keandalan peralatan pembangkit listrik, otomatisasi peningkatan pembangkitan ketika permintaan melonjak.
• Di tingkat produksi: optimalisasi pemeliharaan preventif peralatan, meningkatkan efisiensi pembangkitan, mengurangi kerugian, mencegah pencurian sumber daya energi.
• Di tingkat promosi: optimalisasi harga tergantung pada waktu dan penagihan dinamis.
• Pada tingkat penyediaan layanan: pemilihan otomatis pemasok yang paling menguntungkan, statistik konsumsi terperinci, layanan pelanggan otomatis, optimalisasi konsumsi energi dengan mempertimbangkan kebiasaan dan perilaku pelanggan.

AI di bidang manufaktur

• Pada tingkat desain: meningkatkan efisiensi pengembangan produk baru, penilaian pemasok otomatis, dan analisis kebutuhan suku cadang.
• Di tingkat produksi: meningkatkan proses penyelesaian tugas, mengotomatisasi jalur perakitan, mengurangi jumlah kesalahan, mengurangi waktu pengiriman bahan baku.
• Di tingkat promosi: memperkirakan volume layanan dukungan dan pemeliharaan, manajemen harga.
• Pada tingkat penyediaan layanan: peningkatan perencanaan rute armada kendaraan, permintaan sumber daya armada, peningkatan kualitas pelatihan teknisi layanan.

AI di bank

• Pengenalan pola - digunakan termasuk. untuk mengenali pelanggan di cabang dan menyampaikan penawaran khusus kepada mereka.

AI dalam transportasi

• Industri otomotif berada di ambang revolusi: 5 tantangan era mengemudi tanpa awak

AI dalam bidang logistik

AI dalam pembuatan bir

AI di peradilan

Perkembangan di bidang kecerdasan buatan akan membantu mengubah sistem peradilan secara radikal, menjadikannya lebih adil dan bebas dari skema korupsi. Pendapat ini diungkapkan pada musim panas 2017 oleh Vladimir Krylov, Doctor of Technical Sciences, konsultan teknis di Artezio.

Ilmuwan percaya bahwa solusi yang ada di bidang AI dapat berhasil diterapkan di berbagai bidang ekonomi dan kehidupan masyarakat. Pakar tersebut menunjukkan bahwa AI berhasil digunakan dalam pengobatan, tetapi di masa depan AI dapat sepenuhnya mengubah sistem peradilan.

“Melihat laporan berita setiap hari tentang perkembangan di bidang AI, Anda hanya akan takjub melihat imajinasi yang tiada habisnya dan keberhasilan para peneliti dan pengembang di bidang ini. Laporan penelitian ilmiah terus-menerus diselingi dengan publikasi tentang produk baru yang memasuki pasar dan laporan hasil luar biasa yang diperoleh melalui penggunaan AI di berbagai bidang. Jika kita berbicara tentang kejadian yang diperkirakan, disertai dengan hype yang nyata di media, di mana AI akan kembali menjadi pahlawan dalam pemberitaan, maka saya mungkin tidak akan mengambil risiko membuat perkiraan teknologi. Saya dapat membayangkan bahwa peristiwa berikutnya adalah munculnya pengadilan yang sangat kompeten dalam bentuk kecerdasan buatan, adil dan tidak dapat dirusak. Hal ini rupanya akan terjadi pada tahun 2020-2025. Dan proses yang akan terjadi di pengadilan ini akan mengarah pada refleksi yang tidak terduga dan keinginan banyak orang untuk mentransfer sebagian besar proses pengelolaan masyarakat manusia ke AI.”

Ilmuwan mengakui penggunaan kecerdasan buatan dalam sistem peradilan sebagai “langkah logis” untuk mengembangkan kesetaraan dan keadilan legislatif. Kecerdasan mesin tidak rentan terhadap korupsi dan emosi, dapat secara ketat mematuhi kerangka legislatif dan mengambil keputusan dengan mempertimbangkan banyak faktor, termasuk data yang menjadi ciri para pihak yang bersengketa. Dengan analogi bidang medis, robot hakim dapat beroperasi dengan data besar dari repositori layanan pemerintah. Dapat diasumsikan bahwa

Musik

Lukisan

Pada tahun 2015, tim Google menguji jaringan saraf untuk melihat apakah mereka dapat membuat gambar sendiri. Kemudian kecerdasan buatan dilatih menggunakan sejumlah besar gambar berbeda. Namun, ketika mesin tersebut “diminta” untuk menggambarkan sesuatu sendiri, ternyata mesin tersebut menafsirkan dunia di sekitar kita dengan cara yang agak aneh. Misalnya, untuk tugas menggambar halter, pengembang menerima gambar di mana logam dihubungkan oleh tangan manusia. Hal ini mungkin terjadi karena fakta bahwa selama tahap pelatihan, gambar yang dianalisis dengan dumbel berisi tangan, dan jaringan saraf salah menafsirkannya.

Pada tanggal 26 Februari 2016, pada lelang khusus di San Francisco, perwakilan Google mengumpulkan sekitar $98 ribu dari lukisan psikedelik yang dibuat dengan kecerdasan buatan. Dana ini disumbangkan untuk amal. Salah satu gambar mobil tersukses disajikan di bawah ini.

Sebuah lukisan yang dilukis oleh kecerdasan buatan Google.

Kami melihatnya sepanjang waktu. Protokol “RESTful” ini, “REST” itu, dll. Namun, banyak dari kita yang belum memahami secara pasti apa maksudnya. Kami akan memperbaiki kesenjangan tersebut di artikel ini!

Negara

Dalam ilmu komputer (dan matematika, sampai batas tertentu), terdapat konsep negara. Suatu sistem tertentu dapat berada dalam keadaan A atau bisa juga di negara bagian B atau bisa berupa sekumpulan negara bagian lain (biasanya, daftar negara bagian yang terbatas).

Sebagai contoh, katakanlah Anda menulis sebuah program yang mengubah layar menjadi merah jika suhu lebih dari 80 derajat farenheit atau mengubah layar menjadi biru jika suhu kurang dari 80 derajat farenheit.

Kita dapat menyebut keadaan pertama (suhu > 80 derajat) sebagai “A” dan keadaan kedua (suhu< 80 degrees) state “B”. We’ll call the middling state (temp = 80 degrees) state “C”. As we can see, we have defined behaviours of the programs at state A and state B, but not at state C.

Itulah gambaran umum tentang negara. Berikut definisi yang diberikan oleh Wikipedia yang maha tahu:

“Dalam teori ilmu komputer dan automata, keadaan rangkaian logika digital atau program komputer adalah istilah teknis untuk semua informasi yang disimpan, pada titik waktu tertentu, yang digunakan oleh rangkaian atau program tersebut.”

Singkatnya, ini adalah semacam “kombinasi” dari semua informasi yang diperhitungkan oleh program.

Sekarang, kita akan melakukan lompatan ke dalam sesuatu yang sebagian besar dianggap teoretis dan tidak berguna, lalu terhubung ke dunia REST yang sangat praktis.

Mesin turing

Ada pria bernama Alan Turing, dan dia adalah seorang ahli matematika yang cerdas dan tertarik pada cara kerja komputer. Dia menyusun sebuah komputer imajiner (yang, seperti akan kita lihat, sebenarnya mustahil untuk dibuat) yang dia gunakan untuk memikirkan hal-hal yang terjadi di komputer nyata.

Komputer terdiri dari pita yang panjangnya tak terhingga, dengan kepala yang dilalui pita tersebut. Pita itu mempunyai “sel”, di mana informasi dapat ditulis (angka, warna, dll.). Pita itu bergerak melalui mesin ini, ke kiri atau ke kanan, satu sel pada satu waktu. Mesin memindai apa pun yang sudah ada di kaset dan, tergantung pada kondisinya, mesin menulis sesuatu kembali ke kaset, kemudian, mengubah statusnya.

Anda mungkin ingin membaca definisi itu lagi agar dapat memahaminya sepenuhnya. Inti dari idenya adalah membuat operasi pada memori berdasarkan keadaan dan keadaan berubah sesuai dengan operasi pada memori.

Hal ini tampak seperti khayalan teoritis yang tidak berguna (walaupun, tidak ada yang salah dengan hal itu, bacalah A Mathematician’s Apology jika Anda bertanya-tanya mengapa orang tertarik pada hal-hal teoritis). Namun, ini mungkin merupakan konsep paling mendasar dalam ilmu komputer.

Dengan menggunakan Mesin Turing, ilmuwan komputer dapat memikirkan algoritma apa pun yang dapat dijalankan di komputer. Faktanya, mesin Turing telah membawa banyak kemajuan dalam ilmu komputer.

Jadi, Mesin Turing menunjukkan kepada kita bahwa saat ini (catatan: Saya tidak mempertimbangkan prosesor reduksi grafik), secara harfiah segala sesuatu dalam ilmu komputer didasarkan pada gagasan tentang negara.

Jaringan

Kemudian muncullah konsep internet. Ini adalah tempat di mana paket bisa rusak dan dikirim ulang hingga mencapai tujuannya. Secara umum, tidak pernah ada transmisi data lengkap secara lengkap.

Klien datang dengan cepat dan pergi dua kali lebih cepat. Oleh karena itu, mempertahankan status klien tidak masuk akal ketika bekerja pada sistem jaringan.

Selain itu, secara umum, menyimpan terlalu banyak status dalam suatu sistem telah menyebabkan masalah besar (yang juga menyebabkan bahasa pemrograman berfungsi, yang tidak mengizinkan penyimpanan status di sebagian besar kode Anda).

Saat ini, masyarakat membutuhkan protokol jaringan untuk internet yang sederhana, cepat, dan menangani pengelolaan negara dengan baik dalam lingkungan yang sangat dinamis.

Protokol tersebut adalah HTTP, dan teori yang muncul dari pengerjaan HTTP diberi nama REST.

ISTIRAHAT

REST adalah singkatan dari: REpresentational State Transfer. Ini adalah sistem yang dibangun berdasarkan konsep "client-server" di mana jaringan dibangun (yah, ada juga jaringan tipe peer to peer, namun, server klien bisa dibilang merupakan arsitektur yang paling sederhana dan paling teruji). Namanya sendiri agak menyesatkan, karena servernya sepenuhnya bebas negara!

Ada beberapa batasan yang harus dipatuhi oleh semua sistem yang mengklaim “RESTful”.

Pertama-tama, itu harus menjadi sistem client-server. Batasan ini telah dimodifikasi di masa lalu, namun dalam definisi formal (dan, agar teori REST berfungsi dengan baik), kami memiliki server yang dapat dihubungkan dengan klien.

Server sepenuhnya tanpa kewarganegaraan. Artinya, untuk setiap permintaan klien ke server, tidak ada status yang dicadangkan di server. Misalnya, jika klien (menggunakan HTTP), meminta halaman indeks dan kemudian meminta halaman /pengguna/beranda, kedua permintaan tersebut sepenuhnya independen satu sama lain. Klien memegang semua keadaan sistem (karenanya, kita memiliki tombol kembali).

Respons dari server harus dapat disimpan dalam cache, artinya harus ada sistem di server yang mengidentifikasi respons sebagai dapat di-cache atau tidak, sehingga klien (misalnya browser web) dapat memanfaatkan cache tersebut.

Terakhir, kita harus memiliki antarmuka yang sederhana, bersih, dan seragam. Jika Anda memiliki pengalaman tentang cara kerja HTTP, formulir permintaannya sangat sederhana. Sebagian besar merupakan kata kerja dan kata benda dengan format yang sangat mudah diurai dan dapat dibaca manusia. SOAP adalah bentuk lain dari protokol jaringan yang benar-benar menghilangkan persyaratan ini dan, oleh karena itu, seringkali sangat sulit untuk digunakan.

Sekarang, apa arti dari semua properti ini, jika digabungkan?

Implikasi dari REST

Mereka memungkinkan kita membangun sistem yang terpisah dengan rapi, dapat diskalakan, dan di-debug dengan mudah.

Mari kita pertimbangkan pembatasan keadaan tanpa kewarganegaraan di server terlebih dahulu, ini mungkin merupakan bagian yang paling penting (dan, juga, paling sering dilanggar oleh apa yang disebut arsitektur RESTful).

Seperti disebutkan sebelumnya, dalam arsitektur klien-server, klien sangat gesit; mereka memecat permintaan dan tiba-tiba mematikan semua komunikasi. Dalam situasi seperti ini, jauh lebih bersih jika tidak menyimpan status tentang klien di server. Hal ini memungkinkan kita berpikir tentang server HTTP dengan sangat mudah; setiap permintaan klien dapat diperlakukan seolah-olah itu adalah klien yang benar-benar baru, dan tidak akan ada bedanya satu sen pun.

Kedua, respons yang dapat di-cache berarti klien dapat memperoleh data lebih cepat, karena seringkali data dapat diambil dari memori klien. Hal ini segera meningkatkan kinerja klien dan, dalam beberapa sistem, skalabilitas server.

Antarmuka yang seragam mungkin yang paling penting. Setelah bekerja dengan SOAP, saya dapat memberi tahu Anda bahwa format HTTP yang sederhana merupakan suatu berkah ketika mencoba men-debug kode server dan hal yang sama berlaku untuk sistem RESTful lainnya.

Merancang Sistem Tenang

Katakanlah kita perlu menulis server yang mengembalikan harga saham, serta menyimpan daftar harga saham untuk dipantau (dan, pengguna dapat menambah atau menghapus daftar tersebut).

Ini adalah kasus yang sangat baik untuk sistem RESTful, karena sistem ini secara inheren tidak bergantung pada identitas klien. Oleh karena itu, server tidak perlu menyimpan status apa pun tentang klien.

Pertama-tama kita mulai dengan mendefinisikan cara kerja bahasa protokol (mirip dengan kata kerja GET dan POST pada HTTP):

DAPATKAN KUTIPAN jantung- memberikan harga untuk saham tertentu
PENAMBAH jantung- menambahkan stok yang diberikan ke daftar
GETLIST - mendapat daftar saham yang dipisahkan koma dalam daftar

Itu adalah protokol yang cukup sederhana, dan tidak memiliki status apa pun di server. Sekarang, mengenai caching, kita dapat mengatakan bahwa kita memperbarui harga setiap jam, sehingga cache yang berumur lebih dari satu jam dapat dibuang.

Dan, hanya itu saja! Tentu saja, kami masih harus menerapkannya, tetapi gambaran umum sistem ini cukup sederhana dan bersih!

Kesimpulan

Semoga artikel ini memberi Anda pemahaman yang kuat tentang REST.

Selain itu, saya harap sekarang Anda dapat menyebut orang-orang yang terlalu sering menggunakan istilah “TENANG” - Saya dapat memberitahu Anda, ada banyak sekali dari mereka!

TURING

TURING(Turing) Alan (1912-54), ahli matematika dan logika Inggris yang merumuskan teori yang kemudian menjadi dasar teknologi komputer. Pada tahun 1937 dia menemukan mesin turing - mesin hipotetis yang mampu mengubah serangkaian perintah masukan. Itu adalah cikal bakal komputer modern. Turing juga menggunakan ide komputer untuk memberikan bukti alternatif dan sederhana dari teorema ketidaklengkapan Gödel. Turing memainkan peran utama dalam memecahkan Enigma, metode enkripsi kompleks yang digunakan Jerman selama Perang Dunia II. Pada tahun 1948 ia berpartisipasi dalam pembuatan salah satu komputer pertama di dunia. Pada tahun 1950 dia menemukan Uji Turing - ini seharusnya menjadi ujian terhadap kemampuan komputer untuk "berpikir". Intinya dikatakan bahwa seseorang tidak akan bisa membedakan dialog dengan mesin dengan dialog dengan orang lain. Karya ini membuka jalan bagi terciptanya KECERDASAN BUATAN. Turing juga terlibat dalam biologi teoretis. Sedang berlangsung "Dasar kimia morfogenesis"(1952) ia mengusulkan model yang menggambarkan asal usul berbagai pola struktural organisme dalam biologi. Sejak itu, model seperti itu sering digunakan untuk mendeskripsikan dan menjelaskan banyak sistem yang diamati di alam. Turing bunuh diri setelah secara resmi dituduh melakukan homoseksualitas.

Kamus ensiklopedis ilmiah dan teknis.

Lihat apa itu "TURING" di kamus lain:

Turing, Alan Mathison Alan Turing Monumen Alan Mathison Turing di Taman Sackville Tanggal lahir ... Wikipedia

- (Turing) Alan Mathieson (1912 54), matematikawan Inggris. Pada tahun 1936-1937 ia memperkenalkan konsep matematika tentang persamaan abstrak dari suatu algoritma, atau fungsi yang dapat dihitung, yang kemudian disebut mesin Turing... Ensiklopedia modern

- (Turing), Alan Matheson (23 Juni 1912 - 7 Juni 1954) - Bahasa Inggris. ahli logika dan matematikawan. Pada tahun 1936–37 ia mengusulkan model komputasi mesin yang diidealkan. proses - skema komputasi yang dekat dengan tindakan orang yang melakukan perhitungan, dan dikemukakan... ... Ensiklopedia Filsafat

Turing A.- Turing A. Matematikawan Inggris. Topik keamanan informasi EN Turing… Panduan Penerjemah Teknis

Monumen Alan Turing Alan Turing di Taman Sackville Tanggal lahir: 23 Juni 1912 Tempat lahir: London, Inggris Tanggal kematian: 7 Juni 1954 ... Wikipedia

Turing- Matematikawan Inggris Alan M. Turing, salah satu pencipta landasan logis teknologi komputer, khususnya, memberikan salah satu definisi formal dari algoritma; membuktikan bahwa ada kelas komputer yang dapat melakukan simulasi... ... Lem's World - Kamus dan Panduan

- (Turing) Alan Mathieson (23.6.1912, London, 7.6.1954, Wilmslow, dekat Manchester), ahli matematika Inggris. Anggota Royal Society (1951). Setelah lulus dari Universitas Cambridge (1935), ia mengerjakan disertasi doktoralnya di Princeton... ... Ensiklopedia Besar Soviet

Turing A.M.- TURING (Turing) Alan Mathieson (191254), Inggris. ahli matematika. Dasar tr. dalam matematika logika, menghitung. matematika. Pada tahun 193637 ia memperkenalkan matematika. konsep persamaan abstrak dari suatu algoritma, atau fungsi yang dapat dihitung, kemudian disebut. keranjang... Kamus Biografi

- (lengkap Alan Mathison Turing) (23 Juni 1912, London 7 Juni 1954, Wilmslow, Inggris), matematikawan Inggris, penulis karya logika matematika dan matematika komputasi. Pada tahun 1936-1937 ia memperkenalkan konsep matematika... kamus ensiklopedis

Buku

• Bisakah mesin berpikir? Teori umum dan logis tentang automata. Edisi 14, Turing A., Buku ini, berisi karya Alan Turing dan John von Neumann, yang merupakan cikal bakal penciptaan komputer berpikir pertama, termasuk dalam karya klasik filosofis-cybernetic... Kategori: Basis Data Seri: Ilmu Buatan Penerbit: URSS, Pabrikan: URSS,
• Bisakah mesin berpikir? Teori umum dan logis tentang automata. Edisi No. 14, Turing A., Buku ini, berisi karya Alan Turing dan John von Neumann, yang merupakan cikal bakal penciptaan “mesin berpikir” pertama komputer, termasuk dalam karya klasik filosofis-cybernetic arah... Kategori: