Apakah ada bahasa pemrograman di mana setiap string adalah program yang valid?

10

Apakah ada bahasa pemrograman Turing yang lengkap sehingga untuk alfabet tetap (katakanlah, ASCII), setiap permutasi yang mungkin dari karakter-karakter tersebut adalah program yang secara semantik sah yang dapat dieksekusi?

Kami menganggap loop tak terbatas juga valid secara semantik.

Saya tahu beberapa format data, seperti Markdown, memiliki validitas semantik universal (setiap input valid), tetapi saya tidak bisa lepas tangan memikirkan bahasa pemrograman dengan properti ini.

programming-languages syntax turing-completeness mp-
sumber
@ PhilipKendall Itu adalah jawaban yang valid (jika merosot). Tentu saja hampir semua program akan segera JMP ke ruang yang tidak dikenal dan crash. Tapi itu tidak berarti mereka tidak bermakna. Mengingatkan saya pada superoptimisasi .
mp-
Misalkan Anda memiliki bahasa yang sepele ketika diberi huruf ascii itu mencetaknya dan pindah ke karakter berikutnya. Itu secara teknis memenuhi definisi Anda. Masukan apa pun valid. Ini akan menjadi bahasa yang agak konyol karena Anda tidak dapat melakukan sesuatu yang produktif dengannya, tetapi tentu saja kita tidak berbicara tentang kepraktisan.
Neil
@ Neil: itu bukan bahasa Turing-lengkap.
Doc Brown

Jawaban:

10

Setiap urutan oktet dapat ditafsirkan sebagai kode Z80 yang valid karena tidak ada opcode atau argumen yang tidak valid; Saya membayangkan hal yang sama akan berlaku untuk berbagai prosesor lain, saya pribadi kenal Z80.

Untuk hal-hal tingkat rendah seperti ini, Anda mungkin mulai mengalami pertanyaan tentang apa artinya "menjalankan program":

  • apa yang terjadi jika ia melompat di luar ruang yang diinisialisasi?
  • Bagaimana cara "program" berakhir?
Philip Kendall
sumber
1
"apa yang terjadi jika ia melompat di luar ruang yang diinisialisasi" - dengan hanya menambahkan aturan "melompat ke alamat 0 dalam kasus ini", itu harus cukup sederhana untuk ditangani. Seharusnya tidak terlalu sulit untuk mendefinisikan beberapa semantik tambahan untuk menangani kasus-kasus tepi.
Doc Brown
1
lompatan di luar ruang yang diinisialisasi adalah valid secara sintaksis, dan mungkin bahkan secara semantik juga valid (misalnya semantik yang didefinisikan dengan baik adalah untuk menghasilkan segfault).
Lie Ryan
9

Pertanyaan semacam itu tentang bahasa pemrograman hampir secara universal dijawab dengan ya. Jika saat ini tidak ada bahasa yang memiliki properti yang diminta, Anda dapat bertaruh bahwa seseorang akan melihatnya sebagai tantangan untuk membuat bahasa (mainan) yang memiliki properti tersebut.

Sebagai contoh bahasa di mana setiap permutasi karakter alfabet secara sintaksis valid adalah bahasa spasi , di mana alfabet bahasa itu sendiri terdiri dari ruang, tab dan linefeed.

Bart van Ingen Schenau
sumber
4
Juga, karena karakter non-spasi putih diabaikan sebagai komentar, tidak hanya setiap permutasi spasi, tetapi pada kenyataannya setiap permutasi karakter ASCII juga valid secara sintaksis.
Jörg W Mittag
1
Untuk menjadi seluk: melihat tutorial Whitespace , sepertinya manipulasi tumpukan [Spasi] tidak boleh diikuti oleh karakter [Tab]. Tapi saya kira akan mudah untuk memperluas bahasa untuk kasus-kasus khusus ini (misalnya, dengan memberi mereka semantik No-Op).
Doc Brown
@docbrown, dalam contoh saya melihat urutan [Spasi] [Tab], jadi saya tidak yakin dari mana Anda mendapatkan kesimpulan.
Bart van Ingen Schenau
@ BartartIngenSchenau: lihat ke dalam tutorial: manipulasi stack diperkenalkan oleh [Spasi] diikuti oleh salah satu dari empat perintah yang mungkin, yang dimulai dengan [Spasi] atau [LF] lainnya. Urutan [Spasi] [Tab] dapat muncul sebagai bagian dari angka, atau sebagai bagian dari perintah yang berbeda, tentu saja, tetapi [Tab] bukan karakter yang valid setelah perintah stack diperkenalkan oleh [Spasi].
Doc Brown
0

Mengapa puas dengan string (karakter)? Anda harus menguraikan kembali pertanyaan itu menjadi "serangkaian token". Bukan bit, bit komputerish begitu abad ke-20.

Jadi, loop tak terbatas OK, katamu. Bagaimana dengan pembagian dengan nol? Jika Anda cukup toleran dengan definisi valid Anda, Anda mungkin mendapat jawaban ya tetapi sebagian besar kombinasi masih tidak berarti. Jadi saya akan mengatakan Anda mungkin selalu mendapatkan program yang valid secara teknis tetapi hampir tidak pernah program yang semantik berlaku.

Martin Maat
sumber
"bit computerish begitu abad ke-20": Apa yang Anda maksud dengan ini?
Giorgio
Maksud saya string, karakter dan bit adalah detail teknis, pada dasarnya Anda berbicara tentang instruksi dan operan. Bagaimana penerapannya tidak relevan dengan pertanyaan.
Martin Maat
Ya, tetapi pengamatan ini benar bahkan 50 tahun yang lalu (bahasa formal bahkan lebih tua), jadi saya masih tidak yakin saya mengerti apa yang Anda maksud.
Giorgio
Saya hanya ingin membawa pertanyaan ke esensi logisnya. Ini bukan tentang string atau byte, ini tentang instruksi dan argumen. Bisakah Anda mencampurkannya dengan cara sewenang-wenang dan pastikan untuk mendapatkan program yang valid?
Martin Maat