Bagaimana sistem tag siklik berhenti dengan output?

Sebagai contoh, kita dapat mengatakan bahwa kita memiliki program abstrak yang, diberi string biner terbatas sebagai input, menghapus semua nol (yaitu 0010001101011 dievaluasi menjadi 111111), yang jelas merupakan fungsi yang dapat dihitung oleh Turing.

Bagaimana sistem tag siklik menghitung ini (yang dapat, menurut definisi itu menjadi Turing-lengkap) ketika hanya berhenti ketika mencapai string kosong? Artikel Wikipedia memberikan contoh konversi ke sistem 2-tag, tetapi menambahkan penghentian yang ditiru yang tidak dimiliki sistem asli.

Saya tidak dapat menemukan referensi tentang bagaimana sistem tag siklik berhenti secara berarti. Seperti apa outputnya? Saya sudah mempertimbangkan hal-hal seperti

• Jumlah langkah (tapi kemudian input membatasi kemungkinan keluaran tanpa semacam pengkodean mewah yang tidak dapat saya temukan)
• Produksi terakhir (tetapi itu hanya memiliki rentang keluaran yang terbatas)
• Memperbaiki poin (yang tidak dapat dideteksi dalam sistem ini dan hanya ada dengan aturan dan input produksi yang sangat terbatas)

tetapi mereka tidak bekerja, setidaknya tidak dengan cara apa pun yang bisa saya lihat.

Neary and Woods menggambarkan simulasi mesin Turing yang efisien menggunakan sistem tag siklik, meningkatkan kerja Matthew Cook . Kelengkapan Turing adalah gagasan yang agak cair dan informal. Suatu sistem komputasi X mensimulasikan sistem komputasi Y yang lain jika jika diberikan pada setiap program dalam Y kita dapat membuat program dalam X sehingga dengan melihat transkrip program X, kita dapat memulihkan transkrip program Y.

Anda dapat melihat makalah di atas untuk melihat apa artinya ini untuk sistem tag siklik. Ide dasarnya adalah bahwa ketika mesin Turing berhenti, sistem tag siklik terus berjalan, mengulangi urutan konfigurasi yang sama, mewakili konfigurasi berhenti mesin Turing. Dalam pengertian ini sebenarnya dapat menghitung fungsi.

Dalam jawaban sebelumnya saya mencatat bahwa beberapa model perhitungan hanya dapat menghitung masalah keputusan, dalam arti bahwa mereka tidak berhenti, atau mereka berhenti hanya dengan sedikit output. Dalam hal ini Anda dapat menyandikan fungsi umum setidaknya dalam dua cara:

1. Diberikan fungsi , pertimbangkan bahasa pasangan .$f$$\langle x,f(x) \rangle$

2. Diberikan fungsi , pertimbangkan bahasa tiga kali lipat sedemikian rupa sehingga bit ke- dari (jika ada) sama dengan .$f$$\langle x,i,b \rangle$$i$$f(x)$$b$

Seperti biasa, kami mengharuskan mesin selalu berhenti.

Meskipun versi non-halting dari tag siklik mungkin menarik minat khusus untuk automata seluler, sistem tag siklik juga dapat dirancang untuk mensimulasikan mesin Turing universal sedemikian rupa sehingga menghentikan iff TM berhenti, menampilkan kata output yang mengkode output mesin:

1. Simulasikan TM dengan sistem 2-tag yang mengkodekan semua konfigurasi instan TM, menggunakan "output alphabet" yang terpisah untuk menyandikan segala konfigurasi yang terhenti, sehingga sistem tag berhenti (dengan menghapus kata ini huruf per huruf) jika TM berhenti. ( Makalah ini menunjukkan secara rinci bagaimana hal ini dapat dilakukan dengan menggunakan formulasi mesin Wang dari TMs.)

2. Simulasikan sistem 2 tag dengan sistem tag siklik seperti yang dijelaskan di bagian sistem tag siklik artikel Wikipedia . Karena setiap huruf dalam alfabet keluaran 2-tag memiliki string kosong sebagai pelengkapnya (menyebabkan simulasi 2-tag terhenti), sistem tag siklik akan memiliki perilaku penghentian / keluaran yang sama.

Kunci dalam pendekatan ini adalah bahwa alfabet keluaran yang ditunjuk, katakan , memungkinkan setiap hurufnya memiliki string kosong sebagai pelengkapnya ( ), menyebabkan simulasi untuk menghapus kata data dan berhenti.$\{\alpha_i\}$$\alpha_i\rightarrow \epsilon$

NB : Untuk ketiga jenis sistem (TM, tag, tag siklik), identifikasi output yang jelas dapat dipastikan dengan menggunakan alfabet output yang ditentukan, dan ini dapat dilakukan untuk varietas baik yang menghentikan maupun yang tidak menghentikan sistem ini. (Mengingat bahwa "standar" TM adalah jenis penghentian, ironisnya bahwa mesin komputasi asli Turing adalah varietas non-penghenti dengan alfabet keluaran .)$\{0,1\}$

Dengan pendekatan yang sama, kita juga dapat langsung membangun sistem 2-tag sederhana untuk menghapus s dari string biner, kemudian mensimulasikannya dengan tag siklik. Perhitungan dengan cepat menjadi membosankan, jadi kami hanya akan menerapkannya pada string input , terputus dengan string output . (Simbol akan menunjukkan string kosong.)$0$$101$$11$-

2-tag

input alphabet {a,b}, output alphabet {c}
input encoding:
<0> = aa
<1> = bb
input = <101> = bbaabb
output decoding: <cc> = 1

produksi:

a -> - 
b -> cc 
c -> - 

komputasi:

bbaabb   <-- input word <101>
  aabbcc
    bbcc
      cccc  <-- output word <11>
        cc
         -

tag siklik

pengodean alfabet 2-tag:

<a> = 100
<b> = 010
<c> = 001
cyclic tag system = [-,001001,-,-,-,-]
cyclic tag input = <bbaabb> = 010010100100010010 

komputasi:

appendant    dataword
---------    ---------------------------------------------------------------
-            010010100100010010  <-- input word <bbaabb> = <<101>>
001001        10010100100010010
-              0010100100010010001001
-               010100100010010001001
-                10100100010010001001
-                 0100100010010001001
-                  100100010010001001
001001              00100010010001001
-                    0100010010001001
-                     100010010001001
-                      00010010001001
-                       0010010001001
-                        010010001001
001001                    10010001001
-                          0010001001001001
-                           010001001001001
-                            10001001001001
-                             0001001001001
-                              001001001001  <-- output word <cccc> = <<11>>
001001                          01001001001
-                                1001001001
-                                 001001001
-                                  01001001
-                                   1001001
-                                    001001
001001                                01001
-                                      1001
-                                       001
-                                        01
-                                         1
-                                         -