Kami akan mencoba untuk menulis sebuah program yang mengingat apa yang telah ia lakukan sejauh ini dan terus menuju tujuannya jika dibatalkan kembali. Ini adalah program yang ulet . Ini akan menggunakan Memori Non-Volatile untuk menyimpan informasi lintas, sebagai sejumlah kutipan , yang merupakan bit dengan memperhitungkan apa yang terjadi pada batalkan. Saya pernah menduga bahwa dengan kutipan N , setiap tujuan hingga panjang 2 (NK) dapat dicapai, untuk beberapa K. tetap kecil. Saya sekarang condong ke arah berpikir tujuan tidak dapat dicapai :-(
Itu diminta program ulet dengan tujuan 01
, yang sudah merupakan tujuan non-sepele ; atau bukti kuat ketidakmungkinan.
Sebuah ulet Program didefinisikan sebagai salah satu yang:
- Setiap kali dijalankan , dijalankan mulai dari titik entri yang sama, tanpa input, dan dapat berbagi informasi lintas berjalan secara eksklusif dengan menggunakan
N
kutipan (didefinisikan di bawah); setiap informasi lain memiliki konten yang sama pada awal setiap proses, memiliki konten yang tidak dapat diprediksi pada awal proses, tidak dapat diubah (program itu sendiri), atau tidak dapat dibaca ( output dan nilai sebelumnya ). - Adalah sedemikian sehingga ketika dijalankan dalam suatu sesi itu dapat dikenali berhenti (menggunakan fitur bahasanya), dalam beberapa penundaan terbatas sejak mulai dijalankan, kecuali dibatalkan sebelum dihentikan; batalkan terjadi kapan saja sembarang arbitrase dan mencegah operasi sampai menjalankan lain (jika ada).
- Sedemikian rupa sehingga rangkaian dalam urutan kronologis dari karakter yang dihasilkannya adalah string berhingga yang sama ( tujuan ) dalam setiap sesi arbitrase banyak run yang terdiri dari setidaknya satu run di mana program dibiarkan berjalan sampai berhenti.
- Output karakter menggunakan perangkat yang secara atom : menerima nilai di antara 0 1 2 3 dimasukkan oleh program, dan output
0
(resp.1
) Untuk nilai di antara 0 atau 2 (resp 1 atau 3) jika dan hanya jika nilai itu berbeda dari sebelumnya nilai put, dianggap 0 untuk put pertama dalam suatu sesi.
Ada program ulet! Setiap program yang hanya menempatkan beberapa kali nilai tetap yang valid, kemudian berhenti, adalah ulet dengan tujuan baik kosong (jika angka atau nilainya 0), 0
(jika angka positif dan nilainya 2), atau 1
(jika tidak). Setiap tujuan yang lebih lama membutuhkan NVM.
Setiap cit memodelkan satu NVM bit dengan akun untuk efek run yang dibatalkan saat menulis ke cit. Kapan saja cit berada di salah satu dari tiga kemungkinan negara 0
1
atau U
. Nilai yang dibaca dari cit selalu 0 atau 1; itu juga cocok dengan keadaan kecuali U
. Cit diinisialisasi untuk menyatakan 0
sebelum menjalankan pertama dalam suatu sesi dan sebaliknya mengubah hanya menyatakan ketika menulis untuk itu diperintahkan oleh program, dengan efek tergantung pada apa yang tertulis, apakah menjalankan dibatalkan pada saat penulisan atau tidak, dan dari negara bekas cit:
Former state 0 1 U Rationale given by hardware guru
Operation
Write 0 completed 0 0 0 Discharging returns cit to 0
Write 0 aborted 0 U U Aborted discharging leaves cit unspecified
Write 1 aborted U 1 U Aborted charging leaves cit unspecified
Write 1 completed 1 1 U Charging a non-discharged cit is inhibited
The HAL untuk di atas dinyatakan dalam C sebagai:
/* file "hal.h" unspecified parameter values give undefined behavior */
#define N 26 /* number of cits */
void p(unsigned v); /* put value v; v<4 */
unsigned r(unsigned i); /* read from cit at i; returns 0 or 1; i<N. */
void w(unsigned i, unsigned b); /* write b to cit at i; b is 0 or 1; i<N. */
/* all functions return in bounded time unless aborted */
Upaya pertama kami pada program ulet dengan tujuan 01
adalah:
#include "hal.h" /* discount this line's length */
main(){ /* entry point, no parameters or input */
if (r(3)==0) /* cit 3 read as 0, that is state 0 or U */
w(3,0), /* write 0 to cit 3, to ensure state 0 */
p(2); /* put 2 with output '0' initially */
w(3,1), /* mark we have output '0' (trouble spot!) */
p(1); /* put 1 with output '1' */
} /* halt (but we can be re-run) */
Murphy membuat sesi pertama, membiarkan lari pertama berhenti, dan mengakhiri sesi; output sesi adalah output single run 01
; sejauh ini bagus.
Di sesi lain, Murphy membatalkan putaran pertama selama w(3,1)
, meninggalkan cit dalam keadaan U
; dalam menjalankan kedua Murphy memutuskan itu r(3)
adalah 1 (bahwa cit dalam keadaan U
), dan meninggalkan program berhenti (perhatikan bagaimana w(3,1)
tidak mengubah keadaan cit); dalam menjalankan ketiga Murphy memutuskan itu r(3)
adalah 0, dibatalkan setelah p(2)
, dan mengakhiri sesi.
Output gabungan sesi kedua adalah 010
(satu karakter per run) tetapi berbeda dari 01
pada sesi pertama, sehingga program tidak ulet, karena kondisi 3 tidak terpenuhi.
Bahasa gratis, sesuaikan antarmuka C sesuai bahasa. Saya akan memilih jawaban terbaik berdasarkan jumlah kutipan terendah yang digunakan; kemudian jumlah terburuk terburuk dari penulisan dari jalankan ke output (atau berhenti jika tidak ada output); lalu jumlah penulisan terendah sebelum berhenti dalam sesi tanpa dibatalkan; maka program terpendek. Hitung hanya kode panggilan, bukan antarmuka atau implementasinya, yang tidak diperlukan. Sebuah bukti ketidakmungkinan akan menghilangkan program apa pun (dan mengejutkan saya) ; Saya akan memilih yang paling sederhana untuk dipahami.
Harap periksa tiga kali bahwa program benar-benar memenuhi tujuan sesuai 3, terlepas dari jumlah dan jumlah aborsi; itu sulit!
Pembaruan: Saya menambahkan jawaban kandidat . Jangan ragu untuk mengalahkannya. Oh, hammar melakukannya dalam hitungan menit menggunakan program yang sistematis!
Status : Sejauh ini kami tidak punya solusi; tahu pasti bahwa tidak ada solusi dengan 1 atau 2 kutipan; tetapi tidak memiliki bukti ketidakmungkinan dengan 3 kutipan atau lebih. Pernyataan itu tidak ditemukan ambigu. Masalahnya akan memiliki solusi jika kita mengubah matriks cit sedikit (misalnya diletakkan di 1 di kanan bawah, dalam hal ini contoh di atas sudah benar).
sumber
Jawaban:
Sementara saya tidak punya solusi atau bukti ketidakmungkinan, saya pikir saya akan memasang test harness saya untuk siapa pun yang ingin bermain-main dengan ini, karena saya sudah cukup banyak menyerah pada saat ini.
Ini merupakan implementasi dari program pemodelan HAL sebagai Haskell monad. Ini memeriksa keuletan dengan melakukan pencarian pertama-lebar atas sesi yang mungkin untuk memeriksa sesi yang 1. telah dihentikan sekali tanpa menghasilkan output yang benar, atau 2. telah menghasilkan output yang bukan awalan dari yang diinginkan (ini juga menangkap program yang menghasilkan keluaran tanpa batas).
Berikut adalah contoh program yang diberikan oleh OP yang dikonversi ke Haskell.
Dan di sini adalah output yang sesuai, menunjukkan bahwa program ini tidak ulet.
sumber
Kecuali seseorang dapat menemukan bug dalam program ini, saya pikir itu memeriksa dan menolak setiap program dua-cit yang relevan.
Saya berpendapat bahwa cukup untuk mempertimbangkan program yang membaca semua kutipan dan mengaktifkan nomor yang dibentuk oleh set. Setiap cabang switch akan menjadi serangkaian tulisan dan penempatan. Tidak pernah ada titik menempatkan nomor yang sama lebih dari sekali di cabang, atau menempatkan digit output kedua sebelum yang pertama. (Secara moral saya yakin bahwa tidak ada gunanya mengeluarkan digit pertama selain di awal cabang atau digit kedua selain di akhir, tetapi untuk sekarang saya menghindari penyederhanaan itu).
Kemudian setiap cabang memiliki set target cit yang ingin ditetapkan, dan bergerak ke arah itu dengan mengatur bit yang ingin menjadi 0 sebagai 0, dan bit yang ingin menjadi 1 sebagai 0 lalu 1; operasi penulisan ini dapat dipesan dengan berbagai cara. Tidak ada gunanya mengatur sedikit ke 1 kecuali Anda sudah mengaturnya ke 0 dalam menjalankan itu, atau kemungkinan nop.
Itu mempertimbangkan 13680577296 program yang mungkin; butuh mesin 4-inti di bawah 7 jam untuk memeriksa semuanya tanpa menemukan solusi tunggal.
sumber
Ini
adalahupaya terbaik saya untuk menjawab pertanyaan saya sendiri.Saya tidak yakin apakah memenuhi persyaratan 3, dan terbuka untuk sanggahan.Itu tidak ulet :-(sumber
01
, CITS:110
. 2. Batalkan selama # 15. CITS:10U
. 3. Bacac = 1
, batalkan selama # 12. CITS:U0U
. 4. Bacac = 0
,d = 0
dan program akan mencetak01
lagi.