Tulis simulator mesin Turing .
Untuk kesederhanaan kita dapat menganggap status sebagai integer, simbol sebagai char, simbol kosong sama dengan spasi putih
5-tuple dalam bentuk kondisi saat ini, simbol input, status berikutnya, simbol output, arah (kiri atau kanan) pesanan tidak wajib tetapi tentukan jika Anda menukar
Mesin harus berhenti ketika kondisi yang tidak diketahui tercapai, tidak ada kondisi berhenti lainnya yang diperbolehkan.
Rekaman itu tak terbatas di kedua arah dan Anda selalu dapat membaca karakter kosong.
Input: rekaman awal, keadaan awal dan program. Anda bebas membaca data dari mana saja dalam format yang Anda suka
Output: rekaman setelah eksekusi program
Wajib: contoh program yang berjalan di atas simulator Anda
Ini adalah kode-colf sehingga kode terpendek menang.
Saya akan memposting implementasi dan beberapa program contoh dalam beberapa jam ke depan.
sumber
Jawaban:
GolfScript, 92 karakter
Mesin Turing dalam GolfScript menjadi lebih lama dari yang dimaksudkan. Masih bermain-main dengan representasi yang berbeda dari rekaman itu.
Baris pertama dari input adalah keadaan asli, baris kedua rekaman awal, diikuti oleh array transisi (dengan urutan kondisi saat ini, simbol input, status berikutnya, arah, simbol output).
Contoh (juga tersedia online )
sumber
GNU sed dengan
-r
-13311711193 karakterYa, sed sudah selesai. GNU sed dan
-r
(extended regexps) hanya untuk menyimpan beberapa karakter, itu hanya perubahan kecil untuk bekerja dengan POSIX sed.Format input adalah
Pembatas
@
,#
dan karakter kepala>
tidak dapat digunakan sebagai simbol pada rekaman. Label negara tidak boleh mengandung@
>
atau#
.Ini akan menjalankan semua program dalam input, satu per baris
Contoh:
Marco adalah n b n Program
Marco Halo! program
sumber
Jadi saya agak terlambat, tetapi hanya berpikir saya akan meninggalkan ini di sini ...
Mesin Turing Mensimulasikan Mesin Turing: 370 byte?
Di sini saya menggunakan struktur yang digunakan Turing dalam makalahnya tahun 1936. Saya menggunakan satu simbol = satu byte, termasuk m-konfigurasi dan operasi.
Ini adalah salah satu contoh Turing dari kertas di atas untuk mesin saya:
Cobalah online! (Menggunakan Python 3 sebagai penerjemah) --Edit: Saya baru saja memeriksa TIO, dan sepertinya itu tidak benar-benar berfungsi ... Cobalah di mesin lokal Anda dan seharusnya (semoga) berfungsi. Itu milikku.
sumber
APL (110)
(Bahkan tidak sesingkat itu ...)
Bunyinya dua baris dari keyboard: yang pertama adalah program dan yang kedua adalah rekaman awal.
Formatnya adalah
dan mereka semua harus berada di jalur yang sama. 'Gerakan' adalah 0 untuk bergerak ke kanan dan 1 untuk bergerak ke kiri.
Contoh program (jeda baris dimasukkan untuk kejelasan, semuanya harus dalam satu baris.)
Program ini menambahkan dua angka unary bersama, misalnya:
Contoh 2 (diadaptasi dari program kenaikan biner dari entri Marco Martinelli):
sumber
Python,
101189152142b dan p adalah input, b adalah rekaman awal, p mengkodekan aturan sebagai (representasi string) dict dari (dalam-keadaan, dalam-rekaman) tuple ke (out-state, head move, out-tape) tuple . Jika langkah 0 adalah program selesai, 1 bergerak ke kanan dan -1 pindah ke kiri.
Program sampel ini menguji apakah huruf terakhir dari string (sebelum pita kosong) adalah 'a', jika demikian ia menulis 'Y' di akhir string (spasi kosong pertama).
Edit 1:
Mengubah rekaman untuk direpresentasikan sebagai dict, karena sepertinya cara terpendek untuk menulis struktur data yang dapat diperluas. Baris kedua hingga terakhir sebagian besar mengubahnya kembali menjadi bentuk yang dapat dibaca untuk output.
Edit 2:
Terima kasih kepada Strigoides untuk banyak perbaikan.
Edit 3:
Saya tidak perlu membuatnya jadi 0 karena output akan meninggalkan tempat seperti sekarang. Saya menghapus ini karena kami selalu dapat menulis output sama dengan input.
sumber
r=0;s=0
bisa menjadir=s=0
(dan titik koma di akhir baris itu tidak perlu), Anda dapat menghapus fungsiw
, karena tidak digunakan, tanda kurung dapat dihapus(s,m,t)=r[s,c]
,try
/except
blok dapat disingkat menggunakan dict.get;c=a.get(i,' ')
, karenam
0 atau 1, Anda dapat menggunakanif m-1:
, dan Anda dapat mempersingkatmap()
panggilan Anda dengan mengubahnya menjadi pemahaman daftar.Nota bene
(205)(156)(150)(135)Ini mungkin curang, tetapi tabel transisi berisi kode untuk melakukan transisi. Dan karena rekaman itu diwakili oleh pemetaan dari bilangan bulat ke bilangan bulat, saya telah mewakili negara sebagai pemetaan dari nama ke kamus sehingga rekaman dan program hidup berdampingan dalam kamus anonim yang sama.
Penghematan ekstra dengan membuat semua nama negara dapat dieksekusi, sehingga dapat memuat secara otomatis .
Tidak digabungkan dengan program "Hello" tertanam.
52 karakter tambahan membeli satu loop untuk membaca rekaman dari stdin.Jalankan dengangsnd -q tm.ps
.Jadi format tabelnya adalah
di mana
in-state
adalah nama,in-tape
danout-tape
karakter (mis. bilangan bulat, atau ekspresi yang menghasilkan bilangan bulat),movement
adalah-1
untuk kiri atau1
kanan, danout-state
merupakan nama yang dapat dieksekusi .in-tape
Transisi berganda untuk kondisi yang sama harus digabungkan seperti di atas.sumber
currentdict{search-for-min-and-max}forall juggle-params-for-for
. :(0 1 0 not{(%stdin)(r)file read not{exit}if def}for
. Saya tidak yakin mengapa saya pikir saya bisa menghilangkan itu dari versi golf. : P0 not
seharusnya16#7fffffff
. Maaf. Aha! itu sebabnya itu dikomentari! Itu langsung keluar dari notebook, tidak diuji, dan saya memangkas semua komentar tanpa melihat ketika saya golf itu. Jangan beri tahu pria Python! : PC (belum bermain golf)
Saya kira saya tidak bisa menang dengan ini, tetap saja menyenangkan membuatnya bekerja. Ini bahkan lebih benar sekarang karena itu benar - benar berfungsi. :)
Kecuali itu hanya tak terbatas dalam satu arah. Saya kira itu perlu rekaman negatif juga. Mendesah....
Negatif tidak terlalu buruk. Kami interleave kedua belah pihak sebagai genap dan peluang. Komplikasi sekarang perlu menampilkan rekaman dalam urutan berurutan , karena file itu sendiri sekarang dicampuradukkan. Ini adalah perubahan yang sah untuk dilakukan, saya pikir. Turing sendiri menyederhanakan cara ini.
Dan inilah uji-coba:
Program ini mengeluarkan rekaman dalam urutan berurutan, tetapi file tersebut mewakili sisi negatif dan positif yang disisipkan.
sumber
0 'a' 0 'b' R; 0 'b' 0 'a' R
dengan input aaa outputnya adalah bab bukannya bbb. Dan ada masalah bergerak ke kiri.Groovy
234228154153149139124Diformat agar mudah dibaca
t adalah fungsi yang mengatur kaset e adalah fungsi yang mengevaluasi program
Contoh 1 - Cetak "Halo!" pada kaset itu :)
Contoh 2 - Tinggalkan T pada pita jika string awal adalah dalam bentuk n b n , berhenti sebaliknya.
Contoh 3 - Peningkatan bilangan biner
dalam contoh 1 berarti bergerak ke kanan dan -1 berarti bergerak ke kiri
sumber