Simulator Mesin Turing

15

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.

Marco Martinelli
sumber

Jawaban:

2

GolfScript, 92 karakter

~:m;n\+{:^.n?)>1<]m{2<1$=},.{~2>~^n/~1>[@\+]n*1$%n/~\1$1<+[\1>.!{;" "}*]n*\%@}{;;^0}if}do n-

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 )

> 0
> '101'
> [[0 '0' 0 1 '0']
>  [0 '1' 0 1 '1']
>  [0 ' ' 1 -1 ' ']
>  [1 '0' 2 1 '1']
>  [1 '1' 3 -1 '0']
>  [3 '0' 2 1 '1']
>  [3 ' ' 2 1 '1']
>  [3 '1' 3 -1 '0']] 

110 
Howard
sumber
Anda mengalahkan implementasi sed saya dengan satu char, waktu untuk melihat apakah saya bisa melakukan yang lebih baik
Geoff Reedy
7

GNU sed dengan -r- 133 117 111 93 karakter

Ya, sed sudah selesai. GNU sed dan -r(extended regexps) hanya untuk menyimpan beberapa karakter, itu hanya perubahan kecil untuk bekerja dengan POSIX sed.

:s
s/^(.*@)(.*)>(.)(.*#\1\3([^@]*@)(..))/\5\2\6>\4/
T
s/(..)l>|r>/>\1/
s/>@/@> /
s/>#/> #/
bs

Format input adalah

[initial state]@[non-empty tape with > marking head position]#[state]@[input symbol][next state]@[output symbol][direction l or r]#...

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

Memasukkan

0@>aaabbb#0@a1@ r#0@ 4@ r#1@a1@ar#1@b1@br#1@ 2@ l#2@b3@ l#2@a5@al#3@b3@bl#3@a3@al#3@ 0@ r#4@ 5@Tr

Keluaran

5@    T>  #0@a1@ r#0@ 4@ r#1@a1@ar#1@b1@br#1@ 2@ l#2@b3@ l#2@a5@al#3@b3@bl#3@a3@al#3@ 0@ r#4@ 5@Tr

Marco Halo! program

Memasukkan

0@> #0@ 1@Hr#1@ 2@er#2@ 3@lr#3@ 4@lr#4@ 5@or#5@ 6@!r

Keluaran

6@Hello!> #0@ 1@Hr#1@ 2@er#2@ 3@lr#3@ 4@lr#4@ 5@or#5@ 6@!r
Geoff Reedy
sumber
7

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.

╔═══════════════╦═══════╦═══════════════════╦═══════════════╗
║    m-config    ║ Symbol ║     Operations      ║ Final m-config ║
╠═══════════════╬═══════╬═══════════════════╬═══════════════╣
║ currentCommand ║ Any    ║ L                   ║ currentCommand ║
║                ║ *      ║ MR                  ║ readCommand    ║
╠----------------╬--------╬---------------------╬----------------╣
║ nextCommand    ║ Any    ║ L                   ║ nextCommand    ║
║                ║ *      ║ E  R  R  R  P* R    ║ readCommand    ║
╠----------------╬--------╬---------------------╬----------------╣
║ readCommand    ║ P      ║ R                   ║ readCommandP   ║
║                ║ M      ║ R                   ║ readCommandM   ║
║                ║ G      ║ R                   ║ readCommandG   ║
║                ║ E      ║ R                   ║ MHPNone        ║
╠----------------╬--------╬---------------------╬----------------╣
║ readCommandP   ║ 0      ║                     ║ MHP0           ║
║                ║ 1      ║                     ║ MHP1           ║
║                ║ e      ║                     ║ MHPe           ║
║                ║ x      ║                     ║ MHPx           ║
║                ║ None   ║                     ║ MHPNone        ║
╠----------------╬--------╬---------------------╬----------------╣
║ readCommandM   ║ R      ║                     ║ MHMR           ║
║                ║ L      ║                     ║ MHML           ║
╠----------------╬--------╬---------------------╬----------------╣
║ readCommandG   ║ 1      ║                     ║ G2<1           ║
║                ║ 2      ║                     ║ G2<2           ║
║                ║ 3      ║                     ║ G2<3           ║
║                ║ 4      ║                     ║ G2<4           ║
║                ║ 5      ║                     ║ G2<5           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G2<1           ║ int(1) ║ L  P@ R  R  R  P* R ║ GTS            ║
║                ║ <      ║                     ║ G21            ║
║                ║ *      ║ E  L                ║ G2<1           ║
║                ║ @      ║ E  L                ║ G2<1           ║
║                ║ Any    ║ L                   ║ G2<1           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G2<2           ║ int(2) ║ L  P@ R  R  R  P* R ║ GTS            ║
║                ║ <      ║                     ║ G22            ║
║                ║ *      ║ E  L                ║ G2<2           ║
║                ║ @      ║ E  L                ║ G2<2           ║
║                ║ Any    ║ L                   ║ G2<2           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G2<3           ║ int(3) ║ L  P@ R  R  R  P* R ║ GTS            ║
║                ║ <      ║                     ║ G23            ║
║                ║ *      ║ E  L                ║ G2<3           ║
║                ║ @      ║ E  L                ║ G2<3           ║
║                ║ Any    ║ L                   ║ G2<3           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G2<4           ║ int(4) ║ L  P@ R  R  R  P* R ║ GTS            ║
║                ║ <      ║                     ║ G24            ║
║                ║ *      ║ E  L                ║ G2<4           ║
║                ║ @      ║ E  L                ║ G2<4           ║
║                ║ Any    ║ L                   ║ G2<4           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G2<5           ║ int(5) ║ L  P@ R  R  R  P* R ║ GTS            ║
║                ║ <      ║                     ║ G25            ║
║                ║ *      ║ E  L                ║ G2<5           ║
║                ║ @      ║ E  L                ║ G2<5           ║
║                ║ Any    ║ L                   ║ G2<5           ║
╠----------------╬--------╬---------------------╬----------------╣
║ G21            ║ int(1) ║ L  P@ R             ║ GTS            ║
║                ║ Any    ║ R                   ║ G21            ║
╠----------------╬--------╬---------------------╬----------------╣
║ G22            ║ int(2) ║ L  P@ R             ║ GTS            ║
║                ║ Any    ║ R                   ║ G22            ║
╠----------------╬--------╬---------------------╬----------------╣
║ G23            ║ int(3) ║ L  P@ R             ║ GTS            ║
║                ║ Any    ║ R                   ║ G23            ║
╠----------------╬--------╬---------------------╬----------------╣
║ G24            ║ int(4) ║ L  P@ R             ║ GTS            ║
║                ║ Any    ║ R                   ║ G24            ║
╠----------------╬--------╬---------------------╬----------------╣
║ G25            ║ int(5) ║ L  P@ R             ║ GTS            ║
║                ║ Any    ║ R                   ║ G25            ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTS            ║ ^      ║ R                   ║ TS             ║
║                ║ Any    ║ R                   ║ GTS            ║
╠----------------╬--------╬---------------------╬----------------╣
║ TS             ║ 0      ║                     ║ RL0            ║
║                ║ 1      ║                     ║ RL1            ║
║                ║ e      ║                     ║ RLe            ║
║                ║ x      ║                     ║ RLx            ║
║                ║ None   ║                     ║ RLNone         ║
╠----------------╬--------╬---------------------╬----------------╣
║ RL0            ║ @      ║ R  R                ║ GTS0           ║
║                ║ Any    ║ L                   ║ RL0            ║
╠----------------╬--------╬---------------------╬----------------╣
║ RL1            ║ @      ║ R  R                ║ GTS1           ║
║                ║ Any    ║ L                   ║ RL1            ║
╠----------------╬--------╬---------------------╬----------------╣
║ RLe            ║ @      ║ R  R                ║ GTSe           ║
║                ║ Any    ║ L                   ║ RLe            ║
╠----------------╬--------╬---------------------╬----------------╣
║ RLx            ║ @      ║ R  R                ║ GTSx           ║
║                ║ Any    ║ L                   ║ RLx            ║
╠----------------╬--------╬---------------------╬----------------╣
║ RLNone         ║ @      ║ R  R                ║ GTSNone        ║
║                ║ Any    ║ L                   ║ RLNone         ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTS0           ║ 0      ║ R  P*  R            ║ readCommand    ║
║                ║ Any    ║ R                   ║ GTS0           ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTS1           ║ 1      ║ R  P*  R            ║ readCommand    ║
║                ║ Any    ║ R                   ║ GTS1           ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTSe           ║ e      ║ R  P*  R            ║ readCommand    ║
║                ║ Any    ║ R                   ║ GTSe           ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTSx           ║ x      ║ R  P*  R            ║ readCommand    ║
║                ║ Any    ║ R                   ║ GTSx           ║
╠----------------╬--------╬---------------------╬----------------╣
║ GTSNone        ║ _      ║ R  P*  R            ║ readCommand    ║
║                ║ Any    ║ R                   ║ GTSNone        ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHP0           ║ ^      ║ R                   ║ Print0         ║
║                ║ Any    ║ R                   ║ MHP0           ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHP1           ║ ^      ║ R                   ║ Print1         ║
║                ║ Any    ║ R                   ║ MHP1           ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHPe           ║ ^      ║ R                   ║ Printe         ║
║                ║ Any    ║ R                   ║ MHPe           ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHPx           ║ ^      ║ R                   ║ Printx         ║
║                ║ Any    ║ R                   ║ MHPx           ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHPNone        ║ ^      ║ R                   ║ PrintNone      ║
║                ║ Any    ║ R                   ║ MHPNone        ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHMR           ║ ^      ║ R  R                ║ MHR            ║
║                ║ Any    ║ R                   ║ MHMR           ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHML           ║ ^      ║ L                   ║ MHL            ║
║                ║ Any    ║ R                   ║ MHML           ║
╠----------------╬--------╬---------------------╬----------------╣
║ Print0         ║ ^      ║ R                   ║ Print0         ║
║                ║ None   ║ P0                  ║ nextCommand    ║
║                ║ Any    ║ E                   ║ Print0         ║
╠----------------╬--------╬---------------------╬----------------╣
║ Print1         ║ ^      ║ R                   ║ Print1         ║
║                ║ None   ║ P1                  ║ nextCommand    ║
║                ║ Any    ║ E                   ║ Print1         ║
╠----------------╬--------╬---------------------╬----------------╣
║ Printx         ║ ^      ║ R                   ║ Printx         ║
║                ║ None   ║ Px                  ║ nextCommand    ║
║                ║ Any    ║ E                   ║ Printx         ║
╠----------------╬--------╬---------------------╬----------------╣
║ Printe         ║ ^      ║ R                   ║ Printe         ║
║                ║ None   ║ Pe                  ║ nextCommand    ║
║                ║ Any    ║ E                   ║ Printe         ║
╠----------------╬--------╬---------------------╬----------------╣
║ PrintNone      ║ ^      ║ R                   ║ PrintNone      ║
║                ║ None   ║                     ║ nextCommand    ║
║                ║ Any    ║ E                   ║ PrintNone      ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHL            ║ ^      ║ R  R                ║ MHL            ║
║                ║ [      ║                     ║ SBL            ║
║                ║ Any    ║ L  P^ R  R  E       ║ nextCommand    ║
╠----------------╬--------╬---------------------╬----------------╣
║ MHR            ║ ^      ║ R  R                ║ MHR            ║
║                ║ ]      ║                     ║ SBR            ║
║                ║ None   ║ P^ L  L  E          ║ nextCommand    ║
╠----------------╬--------╬---------------------╬----------------╣
║ SBR            ║ ]      ║ E  R  R  P]         ║ currentCommand ║
╠----------------╬--------╬---------------------╬----------------╣
║ SBL            ║ ]      ║ R                   ║ SBLE           ║
║                ║ Any    ║ R                   ║ SBL            ║
╠----------------╬--------╬---------------------╬----------------╣
║ SBLE           ║ [      ║                     ║ currentCommand ║
║                ║ None   ║ L                   ║ SBLE           ║
║                ║ Any    ║ E  R  R  P] L       ║ SBLE           ║
╚═══════════════╩═══════╩═══════════════════╩═══════════════╝

Ini adalah salah satu contoh Turing dari kertas di atas untuk mesin saya:

['<', None, 1, '0', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
                      '1', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
                      'e', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
                      'x', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
                      '_', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',

             None, 2, '1', None, 'M', 'R', None, 'P', 'x', None, 'M', 'L', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
                      '0', None, 'G', '3',

             None, 3, '0', None, 'M', 'R', None, 'M', 'R', None, 'G', '3',
                      '1', None, 'M', 'R', None, 'M', 'R', None, 'G', '3',
                      '_', None, 'P', '1', None, 'M', 'L', None, 'G', '4',

             None, 4, 'x', None, 'E', 'E', None, 'M', 'R', None, 'G', '3',
                      'e', None, 'M', 'R', None, 'G', '5',
                      '_', None, 'M', 'L', None, 'M', 'L', None, 'G', '4',

             None, 5, '0', None, 'M', 'R', None, 'M', 'R', None, 'G', '5',
                      '1', None, 'M', 'R', None, 'M', 'R', None, 'G', '5',
                      'e', None, 'M', 'R', None, 'M', 'R', None, 'G', '5',
                      'x', None, 'M', 'R', None, 'M', 'R', None, 'G', '5',
                      '_', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2',
        None, '[', '^', None, ']', None]

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.

bendl
sumber
Tidak ada ruginya, hanya menyelaraskan perbatasan di atas meja.
Greg Bacon
@GregBacon Jangan tersinggung ... mungkin ada beberapa perbedaan antara bagaimana komputer yang berbeda membuat kode kunci, tetapi hasil edit Anda membuat penyelarasan jauh lebih buruk di layar edit saya ... Saya yakin itu terlihat baik-baik saja ketika Anda menyarankan edit; tidak yakin apa masalahnya
bendl
3

APL (110)

(Bahkan tidak sesingkat itu ...)

0(''⍞){×⍴X←0~⍨⍺∘{x y S T s m t←⍺,⍵⋄S T≡x,⊃⊃⌽y:s,⊂(⊃y){m:(¯1↓⍺)(⍵,⍨¯1↑⍺)⋄(⍺,⊃⍵)(1↓⍵)}t,1↓⊃⌽y⋄0}¨⍵:⍵∇⍨⊃X⋄,/⊃⌽⍺}⎕

Bunyinya dua baris dari keyboard: yang pertama adalah program dan yang kedua adalah rekaman awal.

Formatnya adalah

(in-state in-tape out-state movement out-tape) 

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.)

(0 ' ' 1 0 '1')
(0 '1' 0 0 '1')
(1 '1' 1 0 '1')
(1 ' ' 2 1 ' ')
(2 '1' 3 1 ' ')

Program ini menambahkan dua angka unary bersama, misalnya:

in:  1111 111
out: 1111111

Contoh 2 (diadaptasi dari program kenaikan biner dari entri Marco Martinelli):

(0 '0' 0 0 '0')
(0 '1' 0 0 '1')
(0 ' ' 1 1 ' ')
(1 '0' 2 0 '1')
(1 '1' 3 1 '0')
(3 '0' 2 0 '1')
(3 ' ' 2 0 '1')
(3 '1' 3 1 '0')
marinus
sumber
Bagaimana saya bisa mencobanya? Saya menggunakan linux dan mencoba dengan aplus tetapi tidak bekerja (token yang tidak ditentukan :(). Penerjemah / kompiler mana yang harus saya coba?
Marco Martinelli
Saya menggunakan Dyalog APL. Saya tidak sadar menggunakan fungsi khusus Dyalog tetapi A + tidak sepenuhnya sama. Ada versi gratis Dyalog tetapi hanya untuk Windows. (Mungkin berjalan di bawah Wine tetapi menggunakan metode input sendiri sehingga Anda dapat mengetik APL.) Jika Anda menjalankan Dyalog, cukup masukkan / tempel kode APL (pada satu baris), kemudian program mesin Turing (pada baris kedua) ), lalu rekaman awal (pada baris ketiga).
marinus
ok, saya akan coba itu, terima kasih
Marco Martinelli
3

Python, 101 189 152 142

a=dict(zip(range(len(b)),b))
r=eval(p)
i=s=0
while 1:
 c=a.get(i,' ')
 s,m,a[i]=r[s,c]
 if 0==m:exit([x[1]for x in sorted(a.items())])
 i=i+m

b 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.

b="aaba"

p="""{(0, 'a'): (1, 1, 'a'),
      (0, 'b'): (0, 1, 'b'),
      (1, 'a'): (1, 1, 'a'),
      (1, 'b'): (0, 1, 'b'),
      (1, ' '): (1, 0, 'Y'),
      (0, ' '): (0, 0, 'N')}"""

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.

shiona
sumber
Saya tidak berpikir ini adalah solusi yang valid karena dalam implementasi Anda rekaman itu terbatas. Dengan cara ini Anda perlu tahu terlebih dahulu konsumsi memori program Anda. Dan ada masalah bergerak ke kiri. Petunjuk: rekaman dapat dibuat dari dua tumpukan yang dimodifikasi di mana Anda selalu dapat memunculkan simbol kosong.
Marco Martinelli
Ah benar Maaf, tidak berpikir sejauh ini.
shiona
Uhm .. afaik rekaman itu tak terbatas di kedua arah dan Anda selalu dapat membaca karakter kosong. Saya akan menentukan itu dalam jawaban.
Marco Martinelli
Anda benar (kami memiliki aturan yang lebih ketat dalam latihan kami). Saya memperbaiki setidaknya beberapa kekurangan.
shiona
Anda dapat menghapus spasi di baris pertama, r=0;s=0bisa menjadi r=s=0(dan titik koma di akhir baris itu tidak perlu), Anda dapat menghapus fungsi w, karena tidak digunakan, tanda kurung dapat dihapus (s,m,t)=r[s,c], try/ exceptblok dapat disingkat menggunakan dict.get; c=a.get(i,' '), karena m0 atau 1, Anda dapat menggunakan if m-1:, dan Anda dapat mempersingkat map()panggilan Anda dengan mengubahnya menjadi pemahaman daftar.
Strigoides
3

Nota bene (205) (156) (150) (135)

<<
>>begin
/${stopped}def([){add dup{load}${exit}if}def
0 A{1 index{load}${pop( )}if
get{exec}${exit}if}loop
3{-1[pop}loop{1[print}loop

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 dengan gsnd -q tm.ps.

%!
<<
    /A<<( ){dup(H)def 1 add B}>>
    /B<<( ){dup(e)def 1 add C}>>
    /C<<( ){dup(l)def 1 add D}>>
    /D<<( ){dup(l)def 1 add E}>>
    /E<<( ){dup(o)def 1 add F}>>
>>begin %ds: int-keys=tape name-keys=prog
0 A %pos state
{ %loop
    1 index{load}stopped{pop( )}if  %pos state tape(pos)
    get    {exec}stopped{exit  }if  %new-pos new-state
} loop
% Loop from tape position 0 to left until left tape end is found
0{                                  %pos
  -1 add                            %new-pos
  dup{load}stopped{exit}if          %new-pos tape(new-pos)
  pop                               %new-pos tape(new-pos)
}loop
% Move to the right and print all chars until right end is hit
{                                   %pos
  1 add                             %new-pos
  dup{load}stopped{exit}if          %new-pos tape(new-pos)
  print                             %new-pos tape(new-pos)
}loop

Jadi format tabelnya adalah

/in-state<<in-tape{dup out-tape def movement add out-state}
           in-tape2{dup out-tape2 def movement2 add out-state2}>>

di mana in-stateadalah nama, in-tapedan out-tapekarakter (mis. bilangan bulat, atau ekspresi yang menghasilkan bilangan bulat), movementadalah -1untuk kiri atau 1kanan, dan out-statemerupakan nama yang dapat dieksekusi . in-tapeTransisi berganda untuk kondisi yang sama harus digabungkan seperti di atas.

luser droog
sumber
Masalah lain adalah tidak ada ketentuan untuk menemukan bagian rekaman yang menarik. Itu akan membutuhkan sedikit biaya untuk melakukan currentdict{search-for-min-and-max}forall juggle-params-for-for. :(
luser droog
Sudah mencoba sendiri, tetapi jauh melebihi keringkasanmu. Tetapi saya menyarankan beberapa perbaikan pada kode Anda.
Thomas W.
BTW, bagaimana dengan rekaman awal? Saya menghapus baris komentar dari kode un-golfed karena sepertinya tidak melakukan pekerjaan. ("0 not" mengembalikan -1, oleh karena itu tidak ada pengulangan dari loop)
Thomas W.
Peningkatan luar biasa! ... Tentang kode rekaman awal, saya rasa saya salah ketik dari buku catatan saya. SB 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. : P
luser droog
Oh, tunggu, -1! Maka 0 notseharusnya 16#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! : P
luser droog
2

C (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.

#include<stdio.h>
int main(int c, char**v){
    int min=0,max=0;
    int pos=0,qi;sscanf(v[1],"%d",&qi);
    FILE*tab=fopen(v[2],"r");
    FILE*tape=fopen(v[3],"r+");
    setbuf(tape,NULL);
    do {
        min = pos<min? pos: min;
        max = pos>max? pos: max;
        fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET);
        int c = fgetc(tape), qt=qi-1,qr;
        fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET);
        char x = c==EOF?' ':c, xt=x-1,xr,d[2];
        if (x == '\n') x = ' ';
printf("%d '%c' %d (%d)\n", qi, x, pos, (int)ftell(tape));
        while((qt!=qi)||(xt!=x)){
            fscanf(tab, "%d '%c' %d '%c' %1[LRN]", &qt, &xt, &qr, &xr, d);
            if (feof(tab)){
                goto HALT;
            }
printf("%d '%c' %d '%c' %s\n", qt, xt, qr, xr, d);
        }
        qi=qr;
        rewind(tab);
        fputc(xr,tape);
        pos+=*d=='L'?-1:*d=='R'?1:0;
    } while(1);
HALT:
printf("[%d .. %d]:\n", min, max);
    for (pos = min; pos <= max; pos++){
        fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET);
        //printf("%d ",pos);
        putchar(fgetc(tape));
        //puts("");
    }
    return qi;
}

Dan inilah uji-coba:

522(1)04:33 AM:~ 0> cat bab.tm
0 'a' 0 'b' R
0 'b' 0 'a' R
523(1)04:33 AM:~ 0> echo aaaaa > blank; make tm ; tm 0 bab.tm blank; echo; cat blank
make: `tm' is up to date.
0 'a' 0 (0)
0 'a' 0 'b' R
0 'a' 1 (2)
0 'a' 0 'b' R
0 'a' 2 (4)
0 'a' 0 'b' R
0 ' ' 3 (6)
0 'a' 0 'b' R
0 'b' 0 'a' R
[0 .. 3]:
bbbÿ
babab

Program ini mengeluarkan rekaman dalam urutan berurutan, tetapi file tersebut mewakili sisi negatif dan positif yang disisipkan.

luser droog
sumber
Ada masalah dengan implementasi Anda. Coba program ini yang menukar a dan b 0 'a' 0 'b' R; 0 'b' 0 'a' Rdengan input aaa outputnya adalah bab bukannya bbb. Dan ada masalah bergerak ke kiri.
Marco Martinelli
Terima kasih atas perhatiannya! Perbarui perbaikan keduanya, saya pikir (harapan).
luser droog
uhm .. masih mendapatkan bab
Marco Martinelli
ya, tapi kali ini benar! 'aaa' sesuai dengan posisi [0, -1,1] pada kaset. Tetapi output yang seharusnya menunjukkan ini jelas perlu bekerja.
luser droog
1

Groovy 234 228 154 153 149 139 124

n=[:];i=0;t={it.each{n[i++]=it};i=0};e={p,s->a=p[s,n[i]?:' '];if(a){n[i]=a[1];i+=a[2];e(p,a[0])}else n.sort()*.value.join()}

Diformat agar mudah dibaca

n=[:];
i=0;
t={it.each{n[i++]=it};i=0};
e={p,s->
    a=p[s,n[i]?:' '];
    if(a){
        n[i]=a[1];
        i+=a[2];
        e(p,a[0])
    }else n.sort()*.value.join()
}

t adalah fungsi yang mengatur kaset e adalah fungsi yang mengevaluasi program

Contoh 1 - Cetak "Halo!" pada kaset itu :)

t('')
e([[0,' ']:[1,'H',1],
   [1,' ']:[2,'e',1],
   [2,' ']:[3,'l',1],
   [3,' ']:[4,'l',1],
   [4,' ']:[5,'o',1],
   [5,' ']:[6,'!',1]],0)

Contoh 2 - Tinggalkan T pada pita jika string awal adalah dalam bentuk n b n , berhenti sebaliknya.

t('aaabbb')
e([[0,'a']:[1,' ',1],
   [0,' ']:[4,' ',1],
   [1,'a']:[1,'a',1],
   [1,'b']:[1,'b',1],
   [1,' ']:[2,' ',-1],
   [2,'b']:[3,' ',-1],
   [2,'a']:[5,'a',-1],
   [3,'b']:[3,'b',-1],
   [3,'a']:[3,'a',-1],
   [3,' ']:[0,' ',1],
   [4,' ']:[5,'T',1]],0)

Contoh 3 - Peningkatan bilangan biner

t('101')
e([[0,'0']:[0,'0',1],
   [0,'1']:[0,'1',1],
   [0,' ']:[1,' ',-1],
   [1,'0']:[2,'1',1],
   [1,'1']:[3,'0',-1],
   [3,'0']:[2,'1',1],
   [3,' ']:[2,'1',1],
   [3,'1']:[3,'0',-1]],0)

dalam contoh 1 berarti bergerak ke kanan dan -1 berarti bergerak ke kiri

Marco Martinelli
sumber