Esiste un linguaggio di programmazione completo di Turing tale che per un alfabeto fisso (ad esempio, ASCII), ogni possibile permutazione di quei caratteri è un programma semanticamente valido che può essere eseguito?
Consideriamo che i cicli infiniti siano anche semanticamente validi.
So che alcuni formati di dati, come Markdown, posseggono una validità semantica universale (ogni input è valido), ma non posso pensare a parole estranee a un linguaggio di programmazione con questa proprietà.
Ogni sequenza di ottetti può essere interpretata come codice Z80 valido in quanto non ci sono opcode o argomenti non validi; Immagino che lo stesso si applichi a vari altri processori, conosco solo Z80.
Per cose di basso livello come questo, potresti iniziare a imbatterti in domande su cosa significhi "eseguire un programma":
Tali domande sui linguaggi di programmazione sono quasi universalmente risolte con sì. Se al momento non esiste una lingua con la proprietà richiesta, puoi scommettere che qualcuno la vedrà come una sfida per creare una lingua (giocattolo) che ha la proprietà.
Come esempio di una lingua in cui ogni permutazione dei caratteri dell'alfabeto è sintatticamente valida è la lingua degli spazi bianchi , dove l'alfabeto della lingua stessa è costituito da spazio, tabulazione e avanzamento riga.
Perché accontentarsi di stringhe (di caratteri)? Dovresti riformulare la domanda in "qualsiasi serie di token". Non bit, i bit sono così informatici del ventesimo secolo.
Quindi, loop infiniti vanno bene, dici. Che dire della divisione per zero? Se sei abbastanza indulgente con la tua definizione di valido puoi ottenere un si, ma la maggior parte delle combinazioni sarebbe ancora priva di significato. Quindi direi che potresti sempre ottenere un programma valido tecnicamente ma quasi mai un programma valido semanticamente .
Leggi altre domande sui tag programming-languages syntax turing-completeness