Est-il possible de créer un Quine dans toutes les langues turation-complet?

Question

Je voulais juste savoir s'il est possible à 100%, si ma langue est Turing-complet, d'écrire un programme en ce qui s'imprime (bien sûr de ne pas utiliser une fonction de lecture de fichier)

Donc, si la langue a juste les choses vraiment nécessaires pour rendre turing complète (je prouverais que en traduisant Brainf * Code ck à elle), comme sortie, les variables, les conditions et GOTO (enfer oui, GOTO), puis-je essayer d'écrire un Quine dedans?

Je demande aussi parce que je ne suis pas sûr que Quine s'inscrit directement dans la loi de Turing que la machine de Turing est capable de toutes les tâches de calcul. Je veux juste savoir si je ne cherche pas pendant des années sans savoir qu'il peut être impossible.

Answer 1

  

Tout langage de programmation qui est   Turing complète, et qui est capable de   une chaîne de sortie (par un calculable   fonction de la chaîne en tant que programme -   c'est une condition technique est   satisfait dans tous les programmes   langue dans l'existence) a une Quine   programme (et, en fait, une infinité de   programmes Quine, et beaucoup similaires   curiosités) comme suit par le   théorème virgule fixe.

Voir

Answer 2

Je suis tombé sur cette question il y a quelques mois.

Alors que l'écriture d'un Quine ne démontre pas nécessairement qu'une langue est complète Turing, il est une suggestion forte;) En ce qui va Exhaustivité Turing, si vous pouvez (comme vous dites) fournir une traduction valide de votre langue à l'autre langue turing-complet, votre langue est turation complète.

Cela étant dit, une langue qui est Turing complet qui peut produire une chaîne doit être en mesure de générer un Quine. En outre, de Wikipedia:

  

A quine est un point fixe d'un environnement d'exécution, lorsque l'environnement d'exécution est considéré comme une fonction. Quines sont possibles dans toutes les langues de programmation qui a la capacité de produire une chaîne calculable, comme conséquence directe de Kleene de théorème récursion . Pour l'amusement, les programmeurs tentent parfois de développer le plus possible Quine dans toutes les langues de programmation donné.

Answer 3

Il est possible d'avoir un langage de programmation qui ne peut pas imprimer tous les symboles dans sa représentation. Par exemple, l'E / S peut être limitée à des caractères ASCII 7 bits avec des mots clés de la langue en arabe. C'est la seule exception que je peux penser.

Answer 4

Eh bien, techniquement, pas toujours. Selon le preuve sur Wikipédia , le langage de programmation doit être une numérotation recevable. langages de programmation Turing Complate pratiques et sains d'esprit sont les numérotations admissibles. Et un langage de programmation Turing Complate est une numérotation admissible s'il est possible de traduire entre cela et une autre numérotation admissible.

Un exemple Turing-complet langage de programmation qui ne constitue pas une numérotation admissible:

Le code source contient toujours une ou deux chaînes doublequoted échappées. Si l'entrée est vide, la sortie de la première chaîne s'il y a deux cordes, ou une boucle pour toujours s'il y a un. Dans le cas contraire, évaluer la dernière chaîne en Python, en utilisant l'entrée d'origine comme entrée.

Il est pas une numérotation admissible parce que, étant donné un programme Python, nous devons connaître son comportement lorsque l'entrée est vide, de le traduire dans cette langue. Mais on ne peut jamais savoir si elle est une boucle infinie, comme nous ne pouvons pas résoudre le problème de l'arrêt. Nous savons que la traduction existe toujours, cependant.

Il est impossible d'écrire Quines dans cette langue.