Existe uma linguagem de programação em que cada string é um programa válido?

10

Existe uma linguagem de programação completa de Turing tal que, para um alfabeto fixo (digamos, ASCII), toda permutação possível desses caracteres seja um programa semanticamente válido capaz de ser executado?

Consideramos que loops infinitos também são semanticamente válidos.

Eu sei que alguns formatos de dados, como o Markdown, possuem validade semântica universal (todas as entradas são válidas), mas não consigo pensar imediatamente em uma linguagem de programação com essa propriedade.

programming-languages syntax turing-completeness mp-
fonte
@PhilipKendall Essa é uma resposta válida (se degenerada). É claro que quase todos os programas JMP imediatamente entrar em espaço desconhecido e falhar. Mas isso não significa que eles não sejam significativos. Lembra-me da super otimização .
mp-
Suponha que você tenha uma linguagem trivial quando receber uma letra ascii, ela a imprime e passa para o próximo caractere. Isso tecnicamente satisfaz sua definição. Qualquer entrada é válida. Seria uma linguagem bastante tola, pois você não pode fazer nada produtivo com ela, mas é claro que não estamos falando de praticidade.
24518 Neil
@ Neil: essa não é uma linguagem completa para Turing.
Doc Brown

Respostas:

10

Cada sequência de octetos pode ser interpretada como código Z80 válido, pois não há opcodes ou argumentos inválidos; Eu imagino que o mesmo se aplicaria a vários outros processadores, eu apenas conheço pessoalmente o Z80.

Para coisas de baixo nível como essa, você pode começar a se perguntar sobre o que significa "executar um programa":

  • o que acontece se ele pular fora do espaço inicializado?
  • Como o "programa" termina assim mesmo?
Philip Kendall
fonte
1
"o que acontece se ele pular fora do espaço inicializado" - simplesmente adicionando uma regra "pula para endereçar 0 nesse caso", deve ser bem simples de manusear. Não deve ser muito difícil definir uma semântica extra para lidar com esses casos extremos.
Doc Brown
1
saltos fora do espaço inicializado são sintaticamente válidos e, possivelmente, até semanticamente válidos também (por exemplo, sua semântica bem definida é produzir um segfault).
Lie Ryan
9

Tais perguntas sobre linguagens de programação são quase universalmente respondidas com sim. Se atualmente não houver um idioma que possua a propriedade solicitada, você pode apostar que alguém o verá como um desafio para criar um idioma (de brinquedo) que possua a propriedade.

Como exemplo de um idioma em que toda permutação dos caracteres do alfabeto é sintaticamente válida é o idioma de espaço em branco , onde o alfabeto do idioma em si consiste em espaço, tabulação e avanço de linha.

Bart van Ingen Schenau
fonte
4
Além disso, como qualquer caractere que não seja de espaço em branco é ignorado como um comentário, não apenas toda permutação de espaço em branco, mas, de fato, toda permutação de caracteres ASCII também é sintaticamente válida.
Jörg W Mittag
1
Para ser minucioso: dando uma rápida olhada no tutorial Espaço em Branco , parece que uma manipulação de pilha [Space] não deve ser seguida por um caractere [Tab]. Mas acho que será simples estender a linguagem para esses casos especiais (por exemplo, fornecendo a eles semântica não operacional).
Doc Brown
@ docbrown, nos exemplos eu vejo sequências de [Space] [Tab], então não tenho certeza de onde você tirou sua conclusão.
Bart van Ingen Schenau
@BartvanIngenSchenau: veja o tutorial: uma manipulação de pilha é introduzida por um [Space] seguido de um dos quatro comandos possíveis, que começam com outro [Space] ou [LF]. A sequência [Space] [Tab] pode ocorrer como parte de um número ou como parte de um comando diferente, é claro, mas uma [Tab] não é um caractere válido após um comando de pilha introduzido por [Space].
Doc Brown
0

Por que se contentar com strings (de caracteres)? Você deve reformular essa pergunta para "qualquer série de tokens". Não bits, bits são tão computadorizados do século XX.

Então, loops infinitos estão OK, você diz. E a divisão por zero? Se você for tolerante o suficiente com sua definição de válido, poderá receber um sim, mas a maioria das combinações ainda não faria sentido. Então, eu diria que você sempre pode obter um programa tecnicamente válido, mas quase nunca um programa semanticamente válido.

Martin Maat
fonte
"bits são tão computadoristas do século XX": o que você quer dizer com isso?
Giorgio
Quero dizer, strings, caracteres e bits são um detalhe técnico, essencialmente você está falando sobre instruções e operadores. Como essas são implementadas é irrelevante para a questão.
Martin Maat
Sim, mas essa observação era verdadeira até 50 anos atrás (as línguas formais são ainda mais antigas), então ainda não tenho certeza de que entendi o que você quis dizer.
Giorgio
Eu só queria levar a questão à sua essência lógica. Não se trata de cadeias ou bytes, trata-se de instruções e argumentos. Você pode misturá-los de maneira arbitrária e obter um programa válido?
Martin Maat