Ini adalah sebuah polisi dan pencuri tantangan berdasarkan definisi bahasa dan membuktikan bahwa mereka Turing lengkap.

Ini adalah utas polisi. Utas perampok ada di sini .

Polisi

Sebagai seorang polisi, Anda akan menyiapkan dua hal:

• Spesifikasi formal bahasa pemrograman, atau sistem komputasi lainnya. (Sistem komputasi didefinisikan di bawah ini.)

• Bukti bahwa sistem Anda Turing lengkap, sesuai dengan definisi yang agak ketat di bawah ini.

Anda akan memposting spesifikasi bahasa Anda, dan perampok akan mencoba untuk "memecahkannya" dengan membuktikan kelengkapan Turing-nya. Jika kiriman Anda tidak retak dalam waktu satu minggu, Anda dapat menandainya sebagai aman dan memposting bukti Anda. (Jawaban Anda dapat dibatalkan jika seseorang menemukan kesalahan dalam bukti Anda, kecuali jika Anda dapat memperbaikinya.)

Ini adalah sebuah kontes popularitas, jadi pemenang akan menjadi jawaban yang memiliki suara terbanyak, dan yang tidak retak atau tidak valid. Tantangannya terbuka - saya tidak akan menerima jawaban.

Demi tantangan ini, sistem komputasi akan didefinisikan sebagai empat hal:

• "Program set" P. Ini akan menjadi himpunan tak terhingga yang tak terhitung jumlahnya, misalnya string, integer, pohon biner, konfigurasi piksel pada kisi, dll. (Tetapi lihat batasan teknis di bawah ini.)

• Suatu "set input" I, yang juga akan menjadi set yang tak terhingga jumlahnya, dan tidak perlu set yang sama P(meskipun bisa jadi).

• "Himpunan keluaran" O, yang juga akan menjadi himpunan tak terhingga yang terhitung, dan mungkin atau mungkin tidak sama dengan PatauI

• Prosedur deterministik, mekanistik untuk menghasilkan output odari program pdan input i, di mana p, idan omerupakan anggota P, Idan Omasing - masing. Prosedur ini harus sedemikian rupa sehingga pada prinsipnya dapat diimplementasikan pada mesin Turing atau model komputasi abstrak lainnya. Prosedurnya, tentu saja, gagal berhenti, tergantung pada program dan inputnya.

Set P, Idan Oharus sedemikian rupa sehingga Anda dapat mengekspresikannya sebagai string dengan cara yang dapat dihitung. (Untuk pilihan yang paling masuk akal, ini tidak masalah; aturan ini ada untuk mencegah Anda memilih set yang aneh, seperti set mesin Turing yang tidak berhenti.)

Kelengkapan Turing akan didefinisikan sebagai berikut:

• Untuk setiap fungsi parsial dihitung fdari Ike O, terdapat sebuah program pdi Psehingga diberikan pdan masukan i, output adalah f(i)jika f(i)memiliki nilai. (Kalau tidak, program tidak akan berhenti.)

Kata "computable" dalam definisi di atas berarti "dapat dihitung menggunakan mesin Turing".

Perhatikan bahwa baik aturan 110 maupun tag siklik bitwise tidak selesai-Turing oleh definisi ini, karena mereka tidak memiliki struktur input-output yang diperlukan. Kalkulus Lambda adalah Turing lengkap, selama kita mendefinisikan Idan Omenjadi angka Gereja . (Ini bukan Turing-lengkap jika kita mengambil Idan Omenjadi ekspresi lambda secara umum.)

Perhatikan bahwa Anda tidak harus menyediakan implementasi bahasa Anda, tetapi Anda dapat memasukkannya dalam jawaban jika Anda mau. Namun, Anda tidak harus bergantung pada implementasi untuk mendefinisikan bahasa dengan cara apa pun - spec harus lengkap dengan sendirinya, dan jika ada kontradiksi antara spec dan implementasi, ini harus diperlakukan sebagai bug dalam implementasi.

Aritmatika yang ditutup matanya

Mungkin bahasa yang cukup mudah untuk memulai, relatif berbicara. (Ada batasan seberapa sulit bahasa yang saya dapat buat karena saya harus membuktikannya Turing-menyelesaikan sendiri!)

Untuk bahasa ini, set program adalah himpunan program Aritmatika Tunanetra seperti yang diberikan pada bagian "program" di bawah ini, set input adalah himpunan bilangan bulat positif, dan himpunan output adalah himpunan bilangan bulat (seluruh himpunan, bukan hanya bilangan bulat positif).

Bahasa ini cukup menarik - bahkan mungkin berguna secara praktis - karena memiliki kurang atau kurang total aliran kontrol, seluruhnya didasarkan pada perhitungan angka yang tidak dapat Anda lihat. Itu membuatnya berpotensi berguna sebagai bahasa untuk mengimplementasikan program di dalam sistem enkripsi homomorfik .

Spesifikasi

Blindfolded Arithmetic adalah bahasa pemrograman esoterik dengan spesifikasi sebagai berikut:

Penyimpanan data

Keadaan program Blindfolded Arithmetic yang sedang berjalan terdiri dari enam variabel, yang masing-masing dapat menyimpan integer. (Tidak ada batasan pada seberapa besar atau kecil bilangan bulat ini bisa mendapatkan, khususnya, mereka bisa pergi negatif.) Variabel disebut a, b, c, d, e, dan i.

Pada awal program, auntuk einklusif masing-masing diinisialisasi ke 0, dan idiinisialisasi ke bilangan bulat positif yang diambil dari input pengguna. (Jika tidak ada input tersedia, idiinisialisasi ke 1.)

Jika program berhenti eksekusi (ini hanya dapat terjadi karena pembagian dengan nol), nilai isegera sebelum pembagian itu digunakan digunakan sebagai output program.

Program

Program Blindfolded Arithmetic adalah daftar perintah, yang masing-masing memiliki salah satu dari bentuk berikut (di mana v dapat diganti dengan nama variabel apa saja, berpotensi nama yang berbeda setiap kali digunakan):

• v = v + v
• v = v - v
• v = v * v
• v = v / v

Perhatikan bahwa setiap operan dari perintah harus berupa variabel; bahasa ini tidak memungkinkan penggunaan bilangan bulat literal.

Eksekusi program dilakukan dengan menjalankan setiap perintah secara berurutan, dan kemudian kembali ke awal dan melanjutkan untuk menjalankan perintah secara berurutan lagi, ad infinitum (atau sampai ada upaya untuk membagi dengan nol, yang mengakhiri program) .

Setiap perintah memiliki semantik yang sama seperti yang Anda harapkan dari notasi, yang tidak berbeda dari yang digunakan oleh sebagian besar bahasa pemrograman praktis: nilai dari variabel kedua dan ketiga yang diambil dalam perintah diambil, operasi aritmatika (tambah / kurangi / gandakan / bagi masing-masing untuk empat bentuk perintah) diterapkan padanya, dan nilai yang dihasilkan disimpan ke dalam variabel pertama. Divisi di sini adalah pembagian integer, pembulatan ke 0.

Tidak ada aliran kontrol dalam bentuk apa pun, selain keluar dari program; perintah selalu berputar secara berurutan, hingga pembagian dengan nol (jika ada) terjadi dan mengakhiri program. Secara khusus, tidak ada cara untuk membaca variabel secara langsung, hanya menggunakannya sebagai sumber perhitungan yang hasilnya berdampak pada nilai yang diberikan ke variabel lain.