Si vous avez des entiers, vous pouvez encoder ou décoder des chaînes (des schémas aussi simples que A = 1, B = 2, etc. suffisent pour cela). Vous devez seulement être capable de comparer des chaînes constantes ou de comparer int. Par conséquent, il semble n'y avoir aucun problème fondamental.
Vous travaillez avec des chiffres et écrire des choses comme
if (n == 1) print "A"
if (n == 2) print "B"
...
Il peut y avoir quelques difficultés pratiques. La chose avec des cordes n'est pas que vous ayez des caractères, mais qu'ils sont équivalents à de très grands nombres. Ce dont vous avez besoin ici, c'est d'avoir accès à des nombres de précision illimités ou à une sorte de tableau de nombres de taille fixe, ou à d'autres grandes structures de données. Un tableau de nombres fera pour vous ce qu'une chaîne peut faire. Mais si votre langue est complète, Turing devrait avoir un moyen d'accéder facilement à une grande partie de la mémoire
Un langage complet de Turing limité à une bande de 32 bits (ou où vous devez donner un nouveau nom à chaque espace mémoire de 32 bits) serait dommage, pas sûr que vous pourriez écrire un quine avec une telle restriction. En passant, il serait intéressant de savoir comment vous avez prouvé que votre langue était complète si vous n'aviez pas de tableaux ou une structure similaire. La méthode courante que j'utilise habituellement consiste à implémenter une machine de Turing en utilisant mon langage. Mais pour ce faire, j'ai besoin d'une sorte de tableau pour simuler le groupe.
Ce type d'encodage est fondamentalement ce que Gödel a fait dans son théorème d'incomplétude, trouver un moyen d'encoder des expressions logiques comme des entiers, puis raisonner sur cela. Si vous donnez plus d'éléments de syntaxe, nous pourrions même essayer de le faire (si vous n'avez pas de fonctions mais seulement des gotos, cela posera également un problème, mais vous pouvez aussi simuler cela). Le problème de base est que vous devez trouver un moyen de "compresser" votre code source codé. Si vous avez une longue chaîne de caractères disponible, cela peut probablement vous aider.
Vous ne comprenez pas ce que Turing signifie. Cela ne signifie pas que vous pouvez écrire n'importe quel programme. –
@Neil, je poserais la question d'une manière différente: un tel encodage d'une machine de Turing existe-t-il, de sorte qu'il est impossible d'écrire un quine pour cela? (Cependant, il appartient à mathoverflow) –
@PAvel: pas sûr de ce que vous entendez par "encodage" d'une machine de Turing. @Neil: bien sûr, cela signifie que vous pouvez écrire ** n'importe quel programme **, même si le résultat peut être difficile à lire. C'est la définition d'un ordinateur universel. – kriss