Comment un Quine dans mon regard de langage de programmation?

Question

J'ai créé un langage de programmation complet-turation (déjà fait ses preuves) il doit être possible d'écrire un Quine , non?

Mais tous Quines que je connais stockent leur code source dans une chaîne, puis remplacer un caractère spécial à l'aide de quelque chose comme chr et ord.

Ma langue a seulement ce qui suit

• Arithmétique de base
• Int et les types de chaîne
• Variables
• == opérateur
• sous condition GOTO

Je ne sais pas comment je pourrais écrire un Quine comme je l'ai aucune manipulation de chaîne réelle disponible , je ne peux que les chaînes de constantes sortie. Pourtant, il est Turing-complet 100%.

Answer 1

Si vous avez des entiers, vous pouvez encoder ou des chaînes de décodage (schémas aussi simple que A = 1, B = 2, etc. sont suffisants pour le faire). Vous avez seulement besoin de pouvoir comparer des chaînes constantes ou pour comparer int. Par conséquent, il semble y avoir aucun problème fondamental.

Vous travaillez avec des chiffres et des choses d'écriture comme

if (n == 1) print "A"
if (n == 2) print "B"
...

Il peut y avoir quelques difficultés pratiques. La chose avec des chaînes n'est pas que vous avez personnages mais qu'ils sont équivalents à un très grand nombre. Qu'est-ce que vous avez besoin ici est soit d'avoir accès à des numéros de précision illimités ou à une sorte de tableau de nombres de taille fixe ou toute autre grande structure de données. Un tableau de nombres fera pour vous quelle chaîne peut faire. Mais si votre langue est Turing compléter devrait avoir un moyen d'accéder facilement une grande partie de la mémoire

Une langue complète limitée Turing sur une bande de 32 bits (ou si vous devez donner un nouveau nom à chaque autre espace mémoire de 32 bits) serait dommage, vous ne pourriez-vous écrire un Quine avec une telle restriction. D'ailleurs, il serait intéressant de savoir comment vous avez prouvé que votre langue a été complète si vous Turing n'avez pas des tableaux ou une structure similaire. La méthode commune habituellement je utiliser est de mettre en œuvre une machine de Turing en utilisant ma langue. Mais pour ce faire, je besoin d'une sorte de tableau pour simuler la bande.

Ce type de codage est essentiellement ce que Gödel a fait dans ce théorème de son incomplétude, trouver un moyen d'encoder des expressions logiques comme des entiers et raison sur ce point.

Si vous donnez des plusieurs éléments de syntaxe, nous pourrions même essayer de le faire (si vous ne disposez pas des fonctions mais seulement GOTO, qui sera également un problème, mais vous pouvez également simuler cela). Le problème fondamental est que vous devez trouver un moyen de « compresser » votre code source encodée. Si vous avez longue constante de chaîne disponible, il peut probablement aider.

Answer 2

Si votre langue est complète et il Turing est un Quine, il le plus probable sont infiniment beaucoup d'entre eux. Voici une façon de construire quelques-uns d'entre eux:

1. Mettre en œuvre un Brainfuck (ou un autre simple, langage complet Turing) interprète dans votre langue. Écrivez votre programme tel que le X1<brainfuck source>Y1 source lors de son exécution, le programme interprète Brainfuck.
2. Ecrire un string f(string a, string b) algorithme dans toutes les langues de votre choix que lorsque donné une a et b émet un programme Brainfuck que lorsque l'exécution envoie la chaîne a, l'intégralité du code source de Brainfuck, la chaîne b. Vous pouvez adapter un Quine Brainfuck existant pour le faire.
3. Calculer f(X1, Y1) puis intégrer le programme Brainfuck résultant dans votre programme de 1.

La première étape est la plus difficile, mais vous pouvez déjà pu le faire parce que l'un des moyens les plus faciles à prouver que quelque chose Turing complet est de mettre en œuvre un interprète pour une autre langue qui a déjà fait ses preuves à Turing complète.

La deuxième étape est avéré être possible déjà et est indépendant de votre langage de programmation.

La troisième étape est un calcul simple.

Answer 3

Apparemment, un programme dans votre langage de programmation est une chaîne. Une sortie d'un quine est un programme.

Par conséquent, une sortie d'un Quine est une chaîne. Si vous n'avez pas la manipulation de chaînes, il est impossible d'écrire un.

Vous devriez coder pour votre programme en chiffres (au lieu de texte simple Humen-lisible encodage) ou mettre en œuvre la manipulation de chaînes.