Programming Programming Challenge: Membuat Mesin Turing Sederhana - dummies

Pada tahun 1936, matematikawan Alan Turing memahami jenis mesin komputasi sederhana yang disebut Mesin Turing . Turing tidak pernah benar-benar membangun Mesin Turing. Sebagai gantinya, perangkat hipotetis yang ia buat untuk membantu studi tentang kemampuan komputasi - yaitu, apakah masalah kompleks dapat diselesaikan dengan langkah-langkah komputasi dan apakah mesin dapat dirancang yang dapat memecahkan masalah yang dapat dikomputasi. (Jika Anda tertarik untuk mengetahui lebih banyak tentang sejarah atau penerapan mesin Turing, Anda dapat menemukan banyak artikel tentang mereka di Internet. Gunakan saja penyedia pencarian untuk mencari "mesin Turing".)

Operasi Mesin Turing sederhana. Ini hanya mencakup beberapa konsep dasar: Hati dari Mesin Turing adalah pita panjang yang tak terbatas yang terbagi dalam sel-sel tempat informasi dapat ditulis.

Dalam praktik sebenarnya, tentu saja, tidak ada perangkat fisik yang memiliki jumlah sel yang tak terbatas. Tapi dalam teori Mesin Turing, rekaman itu tak terbatas.

Informasi yang dapat ditulis ke masing-masing sel dibatasi pada satu simbol tunggal, seperti angka 0 atau 1. Namun, informasi dapat ditunjukkan oleh nilai gabungan sel-sel yang berurutan.
Misalnya, Anda mungkin mewakili nilai numerik dengan kejadian berturut-turut dari simbol 1 diikuti oleh 0. Jadi, 1110 mewakili nilai 3 karena ada tiga 1; 111111011110 mungkin mewakili nilai 6 dan 4 (enam 1 diikuti nol, diikuti oleh empat 1 diikuti nol lain).
Mesin Turing berisi
kepala baca tulis yang selalu diposisikan di atas satu (dan hanya satu) sel dari rekaman itu.

Kepala baca tulis ini bisa membaca simbol yang ada di dalam sel. Hal ini juga dapat menghapus simbol dan, jika diinginkan, tulis simbol baru di tempatnya. Sel di mana kepala baca tulis diposisikan disebut sel
saat ini atau sel kepala . Rekaman itu digerakkan bermotor sehingga bisa dipindahkan ke kiri atau kanan di bawah kepala baca tulis satu sel setiap kalinya.
Mesin memiliki
negara , yang diwakili oleh simbol seperti huruf alfabet. Seperti komputer mana pun, Mesin Turing dapat diprogram. Namun, sebuah program untuk Turing Machine tidak jauh dari program Java.

Sebagai gantinya, program Turing Machine hanyalah seperangkat aturan yang dievaluasi untuk menentukan tindakan apa yang harus dilakukan mesin. Setiap aturan mengidentifikasi tindakan yang akan diambil saat sel saat ini berisi simbol yang diberikan dan mesin berada dalam keadaan tertentu.Misalnya, sebuah aturan mungkin mendikte apa yang harus dilakukan jika sel saat ini berisi 1 dan status mesinnya adalah "a".

Setiap aturan dapat menentukan salah satu dari tiga tindakan berikut:

Hapus sel saat ini atau tuliskan nilai baru ke sel.

Pindahkan pita satu sel ke kiri atau satu sel ke kanan.
Ubah status mesin ke keadaan baru.
Misalnya, sebuah aturan mungkin menentukan bahwa jika sel saat ini berisi 1 dan status mesinnya adalah "a," Mesin Turing harus menulis 0 di sel saat ini, memajukan rekaman satu sel ke kanan, dan mengubahnya status mesin menjadi "b. "

Selain sebuah program, tape Turing Machine dapat memiliki nilai awal.

Itu dia; Itu adalah definisi keseluruhan Mesin Turing. Terlepas dari kesederhanaannya, Mesin Turing dapat menghitung apapun dari 2 + 2 sampai lintasan roket ke Mars.

Untuk tantangan ini, Anda harus membuat Mesin Turing yang sangat sederhana. Untuk menyederhanakan masalahnya, terimalah batasan berikut pada versi Mesin Turing ini:

Rekaman itu tidak harus tak terbatas.

Anda dapat menggunakan fitur Java - sebuah array, string, atau koleksi - untuk mewakili rekaman itu. (Perhatikan bahwa meskipun pita itu tidak harus tak terbatas, Anda harus dapat dengan mudah bergerak ke kiri atau kanan dari sel saat ini. Jika Anda memilih untuk menggunakan sebuah array, jangan mulai dengan sel saat ini pada elemen 0 karena Anda tidak akan bisa bergerak ke kiri dari sana.

Sel bisa kosong atau bisa berisi huruf atau angka apapun.
Sel kosong diwakili oleh karakter underscore. Negara bisa menjadi karakter alfanumerik tunggal.
Program untuk Mesin Turing akan dibaca dari file teks.
File teks ini berisi satu aturan per baris. Setiap aturan berisi lima karakter, dipisahkan oleh spasi, yang memberikan rincian untuk setiap aturan, sebagai berikut: Sel saat ini:
- Nilai yang harus dicocokkan untuk sel saat ini. Kondisi saat ini:
- Nilai yang harus dicocokkan untuk keadaan mesin saat ini. Sel baru:
- Nilai untuk menulis ke sel baru. _ untuk menghapus sel, * meninggalkan sel tidak berubah. Gerakan :
- L atau R untuk memindahkan kaset kiri atau kanan; H untuk menghentikan program; ada karakter lain untuk tidak menggerakkan rekaman itu. Negara baru:
- Nilai baru untuk status mesin. Misalnya, berikut ini mengatakan bahwa ketika sel saat ini adalah 1 dan negara adalah "a," sel saat ini harus diset ke 0, pita tersebut memindahkan satu sel ke kiri, dan negara harus ditetapkan menjadi " b: "
1 a 0 L b
```
Baris pertama dari file teks harus berisi sebuah string yang mewakili nilai awal rekaman itu.
```
- Baris kedua dari file teks harus berisi status awal.
- Gambar berikut menunjukkan antarmuka pengguna untuk solusi sampel, namun Anda bebas menggunakan desain antarmuka pengguna yang Anda inginkan untuk proyek ini.

Antarmuka Mesin Turing yang potensial.

Berikut adalah beberapa pertimbangan untuk membuat antarmuka:

Nilai dan sel saat ini:

Minimal, Anda harus menunjukkan nilai rekaman dan sorot sel saat ini. Alat dan tampilan:
Anda juga harus menyediakan kemampuan untuk memulai, menghentikan, atau memulai ulang eksekusi program, dan Anda harus menampilkan hasil setiap langkah program. Eksekusi program:
Anda dapat memberi jalan bagi pengguna untuk menjalankan program yang dimuat dari awal sampai akhir, dan juga cara bagi pengguna untuk melakukan langkah tunggal melalui program dengan mengklik sebuah tombol untuk melakukan setiap langkah. dari program Memasukkan program
: Anda harus menyediakan tombol yang memungkinkan pengguna memuat program Turing Machine dari file teks dan membiarkan pengguna mengatur ulang mesin agar menjalankan program lagi. Berikut tip untuk menerapkan pita tak terbatas: Gunakan tiga variabel string untuk menahan nilai rekaman, satu untuk karakter tunggal yang tersimpan dalam sel saat ini, yang kedua untuk karakter di sebelah kiri sel saat ini, dan yang ketiga untuk karakter di sebelah kanan sel saat ini. Anda kemudian dapat dengan mudah memindahkan sel saat ini ke kiri atau kanan dengan menggunakan kombinasi yang tepat dari operasi penggabungan dan substring.

Anda dapat menemukan solusi untuk tantangan ini di tab Unduhan halaman produk

Java All-in-One For Dummies, ke-4. semoga berhasil!