É possível criar um Quine em todas as idiomas de Turing-complete?

Question

Eu só queria saber se é 100% possível, se meu idioma estiver preenchido, para escrever um programa que imprima-se (é claro que não está usando uma função de leitura de arquivos)

Portanto, se o idioma tiver apenas as coisas realmente necessárias para torná -lo completo (eu provaria que, traduzindo o código Brainf*ck para ele), como saída, variáveis, condições e gotos (inferno sim, betos), posso tentar Escrevendo um Quine nele?

Também estou perguntando isso porque não tenho certeza de que um Quine se encaixe diretamente na lei de Turing de que a máquina de Turing é capaz de qualquer tarefa computacional. Eu só quero saber, então não tento há anos sem saber que pode ser impossível.

Answer 1

Qualquer linguagem de programação que esteja completa e que é capaz de produzir qualquer string (por uma função computável da string como programa - essa é uma condição técnica que é satisfeita em todas as linguagens de programação existentes) tem um programa de Quine (e, em Fato, infinitamente muitos programas de Quine e muitas curiosidades semelhantes), como segue pelo teorema do ponto fixo.

Veja aqui

Answer 2

Eu encontrei esta edição há alguns meses.

Embora escrever um Quine não prove necessariamente que um idioma está completo, é uma forte sugestão;), no que diz respeito à integridade, se você puder (como você disse), forneça uma tradução válida do seu idioma para outro turing-completo idioma, então seu idioma está completo.

Dito isto, qualquer idioma que seja completo completo que possa gerar uma string deve poder gerar um quine. Além disso, da Wikipedia:

Um Quine é um ponto fixo de um ambiente de execução, quando o ambiente de execução é visto como uma função. Quines são possíveis em qualquer linguagem de programação que tenha a capacidade de produzir qualquer string computável, como uma conseqüência direta de Teorema da Recursão de Kleene. Para diversão, os programadores às vezes tentam desenvolver o menor queda em qualquer linguagem de programação.

Answer 3

É possível ter uma linguagem de programação que não possa imprimir todos os símbolos em sua representação. Por exemplo, a E/S pode ser limitada a caracteres ASCII de 7 bits com palavras-chave do idioma em árabe. Essa é a única exceção que consigo pensar.

Answer 4

Bem, tecnicamente, nem sempre. De acordo com Prova na Wikipedia, a linguagem de programação deve ser uma numeração admissível. As linguagens de programação que complemam com explosões práticas são todas as numerações admissíveis. E uma linguagem de programação com exploração de Turing é uma numeração admissível, se for possível traduzir entre isso e outra numeração admissível.

Um exemplo de linguagem de programação com preenchimento de Turing que não é uma numeração admissível:

O código -fonte sempre contém uma ou duas cordas escapadas com calotas duplas. Se a entrada estiver vazia, produza a primeira string se houver duas seqüências ou loop para sempre, se houver uma. Caso contrário, avalie a última sequência no Python, usando a entrada original como entrada.

Não é uma numeração admissível porque, dado um programa Python, precisamos saber seu comportamento quando a entrada estiver vazia, para traduzi -lo para esse idioma. Mas podemos nunca saber se é um loop infinito, pois não podemos resolver o problema de parada. Sabemos que sempre existe uma tradução.

É impossível escrever queixas nesse idioma.