Bisakah Anda menentukan bahasa pemrograman tanpa implementasi?

11

Apakah secara teori dimungkinkan untuk menentukan bahasa pemrograman yang tidak dapat diterapkan? Bahasa pemrograman adalah cara mendefinisikan fungsi. Implementasi berarti metode untuk menjalankan program yang diberikan dalam bahasa itu pada input yang diberikan ke output fungsi yang sesuai dengan program pada input tersebut.

Apa persyaratan minimal dari bahasa seperti itu?

formal-languages computability programming-languages Kaveh
sumber
3
Apa itu "implementasi" suatu bahasa?
Raphael
@ Raphael: Andalah yang mengubah "bahasa pemrograman" menjadi "bahasa." Sebelum Anda mengedit, sudah jelas apa arti dari implementasi bahasa.
Tsuyoshi Ito
@ TsuyoshiIto: Tidak cukup; Saya hanya mengadaptasi judul agar sesuai dengan pertanyaan, yang diubah pada cstheory.SE. Saya mengubahnya kembali, tetapi masih belum jelas apa artinya itu. Kompiler? Seorang penerjemah? Bagaimanapun, memigrasikan pertanyaan di sini yang hampir berumur satu tahun dan oleh pengguna yang tampaknya tidak pernah mengunjungi kembali pertanyaan di sana keliru.
Raphael
@Raphael: Bertanya “apa itu implementasi bahasa?” setelah menghapus semua petunjuk itu hanya di luar pemahaman saya. Tapi saya setuju bahwa pertanyaannya tidak jelas sejak awal.
Tsuyoshi Ito
Saya pikir definisi dugaan Anda tentang "bahasa pemrograman" salah dipahami. Setidaknya harus diubah dengan mengganti "fungsi" dengan "fungsi yang dapat dihitung". Kalau tidak, tidak jelas mengapa Anda memilih untuk menyebut bahasa sebagai "Bahasa pemrograman". Setelah Anda mengubahnya, pertanyaannya menjadi tidak berarti, karena tidak ada "bahasa pemrograman yang tidak ada implementasinya".
Uday Reddy

Jawaban:

7

Biasanya, menerapkan bahasa pemrograman setidaknya memberikan juru bahasa (atau kompiler ke bahasa) yang tidak lebih dari Turing-complete.

Dengan menggunakan "definisi" ini, kita dapat menentukan bahasa pemrograman seperti ini:

  • hanya ada satu program yang mungkin yaitu HALT;

  • spesifikasi HALT: itu adalah fungsi yang memecahkan masalah terputus - putus .

Menerapkan bahasa pemrograman ini membutuhkan pemecahan masalah yang terhenti dengan implementasi. (Yang tidak mungkin karena implementasi kami seharusnya tidak lebih kuat daripada mesin Turing).

Spesifikasi menangani logika dan dengan demikian dapat meminta lebih banyak. Spesifikasi lain yang tidak mungkin diterapkan adalah "false". (Atau kalimat yang bertentangan dalam spesifikasi) Tapi ini tidak terasa seperti spesifikasi, itulah sebabnya saya menggunakan contoh masalah penghentian.

jmad
sumber
1
Umum: Bahasa apa pun yang menentukan fungsi yang memecahkan masalah yang tidak dapat ditentukan tidak dapat diimplementasikan.
edA-qa mort-ora-y
@ edA-qamort-ora-y Secara teknis itu bisa diterapkan. Anda tidak dapat memutuskan Masalah Pemutusan, tetapi TM dapat mensimulasikan mesin lain dan menerima jika mesin itu berhenti; bahasa yang diterima oleh TM seperti itu persis bahasa (penyandian) mesin yang berhenti. Tetapi untuk tujuan praktis, kami biasanya menyukai operasi primitif bahasa pemrograman yang dijamin akan berakhir! (setidaknya pada input "masuk akal")
Ben
1
O(∞)
1/0 ≡ let loop = loop in loopΩ(∞)
3

Hanya catatan samping yang ingin tahu: mesin template C ++ sudah menyelesaikan Turing

Teorema 1: Dengan tidak adanya batasan instantiasi, templat C ++ lengkap-Turing.

Akibat wajar 1: Dengan tidak adanya batas instantiation, apakah kompiler C ++ akan berhenti ketika mengkompilasi program yang diberikan tidak dapat ditentukan.

... jadi C ++ itu sendiri dapat dianggap sebagai bahasa pemrograman yang tidak ada "implementasi" bisa ada ... :-D

Vor
sumber
Jadi mungkinkah "kompiler" C digunakan sebagai penerjemah jika orang tidak peduli dengan kode yang dihasilkan tetapi hanya diagnostik yang dihasilkan?
supercat
Ya, seperti yang ditunjukkan di kertas, kompiler berhenti dengan daftar kesalahan yang cocok dengan sejarah perhitungan mesin Turing (dan konfigurasi rekaman terakhirnya). Jelas input tidak bisa interaktif (harus dikodekan dalam kode sumber sebelum menjalankan kompiler).
Vor
2

Tidak jelas apa yang Anda maksud dengan "bahasa pemrograman" dan "implementasi bahasa". Anda perlu memberikan definisi yang ketat dari keduanya untuk mendapatkan jawaban.

Σ∗2Σ∗

MM0

Tapi ini bukan jenis bahasa spesifikasi yang orang maksud ketika mereka menggunakan frasa "bahasa pemrograman". Sebuah bahasa pemrograman biasanya dimaksudkan untuk menjadi bahasa untuk mengekspresikan fungsi dihitung (proses, ...) dan untuk berkomunikasi instruksi untuk mesin dan oleh karena itu ada TM yang dapat mensimulasikan program-program dan output hasil mereka. Jadi dalam arti memiliki bahasa pemrograman yang tidak dapat diimplementasikan tidak bermakna.

(Dugaan saya adalah bahwa Anda mungkin membingungkan bahasa pemrograman baik dengan bahasa spesifikasi atau bahasa formal . Dalam kasus apa pun, kami dapat menentukan bahasa yang tidak dapat dihitung.)

Kaveh
sumber
Saya cukup yakin "bahasa pemrograman" berarti bahasa pemrograman seperti yang biasa kita bicarakan, dan "implementasi bahasa" berarti lingkungan untuk menjalankan program dalam bahasa itu pada komputer nyata. Pertanyaannya tidak diformalkan , tapi pasti itu tidak jelas? Saya dapat dengan mudah menulis spec untuk bahasa pemrograman baru tanpa repot-repot mengimplementasikannya; pertanyaannya hanyalah menanyakan apakah mungkin untuk dilakukan sedemikian rupa sehingga bahasa tidak dapat diimplementasikan.
Ben
@Ben, jika Anda melihat pertanyaan asli pada cstheory Anda akan melihat tidak ada pemrograman kata dalam pertanyaan hanya dalam judul. Pertanyaan yang diposting oleh OP jelas. ps: Saya akan tertarik dengan definisi yang ketat (tidak perlu formal) tentang apa itu bahasa pemrograman. Kami tidak dapat membuktikan hasil negatif tentang bahasa pemrograman hanya berdasarkan intuisi dan contoh. Jika Anda memiliki referensi untuk definisi, silakan posting sebagai edit atau komentar untuk pertanyaan.
Kaveh
Cukup adil, meskipun SE mengklaim Anda menjawabnya 9 jam yang lalu, lama setelah dimigrasi dan diedit. Saya masih akan membuat interpretasi yang sama berdasarkan pada pertanyaan aslinya. Sejauh definisi bahasa pemrograman, saya akan mengatakan yang jelas-ish adalah tata bahasa formal ditambah baik pengurangan ke beberapa model komputasi dipahami dengan baik lainnya (kalkulus lambda, mesin turing, dll), atau semantik operasional yang ketat. Model reduksi akan membuat jawaban untuk pertanyaan ini sepele "tidak", jelas.
Ben
1

Ada banyak bahasa yang ditentukan tanpa implementasi, misalnya Algol 60 seharusnya menjadi bahasa untuk menulis algoritma, bukan untuk diimplementasikan. Beberapa dari banyak bahasa "hanya untuk bersenang-senang" telah ditentukan jauh sebelum implementasi, Intercal datang ke pikiran.

vonbrand
sumber