Apakah loop do-while cukup untuk Turing-kelengkapan?

Saya tahu bahwa, dalam bahasa pemrograman imperatif, loop sementara-lakukan sudah cukup sebagai konstruk aliran kontrol untuk membuat bahasa Turing-lengkap (sejauh aliran kontrol berlangsung - tentu saja kita juga memerlukan memori tidak terbatas dan operator tertentu ...) . Inti dari pertanyaan saya adalah: apakah loop do-while memiliki kekuatan komputasi yang sama dengan loop sementara-do? Dengan kata lain, dapatkah sebuah bahasa menjadi Turing-lengkap jika tidak mungkin untuk melewatkan instruksi sepenuhnya.

Saya menyadari bahwa beberapa semantik di sini bisa sedikit ambigu, jadi izinkan saya mengutarakan pertanyaan aktual dengan contoh spesifik:

Brainfuck (BF) adalah turing Turing di mana satu-satunya aliran kontrol adalah loop sementara, dilambangkan sebagai [...](ada spesifikasi bahasa lengkap di bagian bawah pertanyaan, jika Anda tidak terbiasa dengan Brainfuck). Mari kita mendefinisikan bahasa baru BF *, di mana ,.+-<>memiliki semantik yang sama dengan di BF, tetapi alih-alih []kita memiliki {}yang menunjukkan loop do-while. Yaitu, satu-satunya perbedaan pada BF adalah bahwa setiap loop dijalankan setidaknya satu kali sebelum iterasi lebih lanjut dapat dilewati.

Apakah BF * Turing-lengkap? Jika ya, saya akan tertarik pada bagaimana saya bisa menerjemahkan BF ke BF *. Jika tidak, bagaimana saya membuktikannya?

Beberapa pengamatan saya sendiri:

• Tidak setiap program BF dapat diterjemahkan ke dalam BF *. Misalnya, tidak mungkin untuk menulis program dalam BF * yang mungkin atau mungkin tidak membaca atau mencetak nilai - jika program berpotensi mencetak satu atau lebih nilai, ia akan selalu mencetak setidaknya satu. Namun, mungkin ada subset Turing-complete dari BF yang dapat diterjemahkan ke BF *.
• Kami tidak dapat dengan mudah menerjemahkan [f](di mana fada beberapa program Brainfuck yang sewenang-wenang yang hanya terdiri dari +-[]<>) untuk (dalam upaya untuk membatalkan efek dari iterasi pertama), karena a) tidak setiap fungsi yang dihitung memiliki kebalikan yang dapat dihitung dan b) bahkan jika itu terjadi, tidak harus memiliki loop yang lebih sedikit daripada menerapkan langkah ini secara rekursif tidak dijamin untuk berakhir di tempat pertama.f-1{f}f-1f

Berikut ini adalah ikhtisar cepat atas bahasa Brainfuck. Brainfuck beroperasi pada pita tanpa batas di mana setiap sel berisi nilai byte, awalnya nol. Meluap membungkus, sehingga kenaikan 255 memberi 0 dan sebaliknya. Bahasa ini terdiri dari 8 instruksi:

+   Increment the current cell.
-   Decrement the current cell.
>   Move tape head to the right.
<   Move tape head to the left.
,   Input a character from STDIN into the current cell.
.   Output the current cell as a character to STDOUT.
[   If the current cell is zero, jump past the matching ].
]   If the current cell is non-zero, jump back to just behind the matching [.

Saya tidak tahu Brainfuck sehingga Anda harus melakukan beberapa terjemahan dari pseudocode saya. Tetapi, dengan anggapan bahwa Brainfuck berperilaku bijaksana (ha!), Semuanya di bawah ini harus berlaku.

do-while setara dengan while-do. do X while Ysama dengan X; while Y do Xdan, dengan asumsi Anda memiliki persyaratan, while Y do Xsama dengan if Y then (do X while Y).

Hidup sedikit lebih sulit jika Anda tidak memiliki persyaratan. Jika Anda memiliki sementara-lakukan, Anda dapat mensimulasikan if Y then Xmenggunakan sesuatu seperti ini:

B := true
while (Y and B) do
    X
    B := false
endwhile

Tetapi bagaimana jika Anda hanya melakukan-sementara? Saya mengklaim bahwa berikut ini mensimulasikan if Y then X, dengan asumsi yang Xberakhir diberi nilai saat ini dari variabel. (Ini tidak dijamin: program if y=0 then loopforeverberakhir jika y != 0, meskipun Xloop untuk nilai variabel apa pun). Mari V1, ..., Vnmenjadi variabel dimodifikasi oleh Xdan membiarkan X'akan Xdimodifikasi sehingga menggunakan Vi'bukan Viuntuk masing-masing variabel. swap(A,B)menunjukkan kode yang jelas yang menukar variabel Adan B.

V1' := V1; ...; Vn' := Vn
V1'' := V1; ...; Vn'' := Vn
C := 0
do
    X'
    swap (V1',V1''); ...; swap (Vn',Vn'')
    C := C+1
while Y and C<2
V1 := V1'; ...; Vn := Vn'

Idenya adalah sebagai berikut. Pertama, anggap itu Ysalah. Kami mensimulasikan melakukan Xsekali, dan menyimpan hasilnya di V1'', ..., Vn''; V1', ..., Vn'pegang nilai-nilai asli V1, ..., Vn. Kemudian, kami menetapkan V1 := V1'; ...; Vn := Vn', yang tidak melakukan apa-apa. Jadi, jika Ysalah, kami tidak melakukan apa pun. Sekarang, anggap itu Ybenar. Kami sekarang akan mensimulasikan X dua kali , menyimpan hasil dalam variabel "prima" dan "prima ganda". Jadi, sekarang, tugas di akhir loop memiliki efek yang Xdihitung satu kali. Perhatikan bahwa Yhanya tergantung pada variabel "unprimed", sehingga nilainya tidak terpengaruh dengan menjalankan loop berulang kali.

OK, jadi bagaimana jika Xmungkin tidak mengakhiri nilai variabel saat ini? (Terima kasih kepada Martin Ender karena menunjukkan kemungkinan ini.) Dalam hal ini, kita perlu mensimulasikan Xinstruksi demi instruksi, menggunakan ide-ide serupa dengan yang di atas. Setiap instruksi pasti berakhir sehingga kita dapat menggunakan ifsimulasi di atas untuk melakukan decoding instruksi, di sepanjang baris "Jika opcode adalah foo, lakukan ini; jika bilah, lakukan itu; ...". Jadi, sekarang, kita menggunakan loop untuk beralih melalui instruksi X, menggunakan pointer instruksi dan seterusnya sehingga kita tahu instruksi mana yang harus dieksekusi selanjutnya. Pada akhir setiap iterasi dari loop, periksa Ydan periksa apakah Xsudah dihentikan. Jika Ysalah, teknik bertukar memungkinkan kita untuk membatalkan efek dariXInstruksi pertama.