Existe-t-il un langage capable d'exprimer son propre compilateur Turing-complete?

Un commentaire sur tex.SE m'a fait réfléchir . La déclaration est essentiellement:

Si je peux écrire un compilateur pour la langue X dans la langue X, alors X est Turing-complete.

En termes de calcul et de langage formel, c'est:

Si décide et , alors . $M$ $L \subseteq L_{\mathrm{TM}}$ $\langle M \rangle \in L$ $F_L = \mathrm{RE}$

Ici désigne la langue de tous les encodages de la machine de Turing et désigne l'ensemble des fonctions calculées par des machines à . $L_{\mathrm{TM}}$ $F_L$ $L$

Est-ce vrai?

computability turing-completeness Raphael
la source

fermer, penser / convenir qu'il doit y avoir quelque chose de réel proche de cela, tout langage "non trivial" ou "suffisamment complexe" qui peut exprimer son propre simulateur est TM complet. un compilateur ne fait généralement pas partie d'un simulateur. c'est en effet un "modèle de conception" que l'on trouve dans de nombreuses preuves d'exhaustivité de la MT, mais qui n'a peut-être pas été généralisé / formalisé. peut-être un sujet pour une analyse / discussion plus approfondie dans le chat informatique . suspect / conjecture, il existe un autre thème intéressant, un peu comme "chaque langage récursif et énumérable non complexe / suffisamment complexe peut être mappé / réduit à un autre".

vzn

J'ai créé un langage ésotérique appelé InterpretMe, qui ne peut rien faire d' autre qu'exprimer son propre interprète, donc ce n'est certainement pas Turing complet.

Orthographe non contextuelle

Pouvez-vous expliquer la deuxième déclaration? Qu'est-ce que ? Quel est le lien entre cette déclaration et la première?

⟨ M ⟩

$\langle M \rangle$

reinierpost

@reinierpost indique généralement le nombre de , étant donné un certain codage (admissible). Par conséquent, . Par je désigne l'ensemble des fonctions calculées par le langage des machines de Turing.

⟨ M ⟩

$\langle M \rangle$

M

$M$

L_{T M} = {⟨ M ⟩ ∣ M is a Turing machine}

$L_{\mathrm{TM}} = \{ \langle M \rangle \mid M \text{ is a Turing machine}\}$

F_{L}

$F_L$

L

$L$

Raphael

Une meilleure façon de formuler la réclamation serait: "S'il existe un TM avec et , alors .

M

$M$

⟨ M ⟩ \in L

$\langle M \rangle \in L$

L_{M} = L

$L_M = L$

F_{L} = R E

$F_L = \mathrm{RE}$

Raphael

Réponses:

La déclaration informelle n'est pas vraie, comme le montre le langage de programmation suivant. N'importe quelle chaîne de, disons, caractères ASCII est un programme valide et la signification de chaque programme est, "Sortie d'un programme qui sort juste une copie de son entrée." Ainsi, chaque programme dans cette langue est un compilateur pour la langue mais la langue n'est pas complète de Turing.

Je ne sais pas si votre "version de la théorie de la calculabilité" est équivalente mais ce n'est pas vrai non plus. Selon le deuxième théorème de récursivité de Kleene , pour tout codage des machines de Turing, il existe une MT qui accepte son propre codage et rejette tous les autres. ¹ Cette machine est un contre-exemple de la proposition. Plus concrètement, nous pouvons atteindre le résultat en choisissant un codage. Par exemple, laissez chaque numéro impair coder la machine définie par "Si ma saisie est impaire, acceptez-la; sinon, rejetez" et laissez le numéro coder la machine codée par dans votre propre schéma de codage préféré pour les machines Turing. est dans la langue acceptée par mais $M$ $2x$ $x$ $\langle M\rangle$ $L$ $M$ $F_L$ n'est pas Turing complet.

¹ Le deuxième théorème de récursivité de Kleene dit que, pour toute énumération des fonctions récursives partielles (c'est-à-dire pour tout codage de programmes sous forme d'entiers), et toute fonction récursive partielle , il existe un entier tel que est la fonction qui mappe à . Ainsi, en particulier, soit la fonction qui accepte si et rejette autrement. Par le théorème, il existe un entier qui code le programme . Autrement dit, accepte son propre codage $(\phi_i)_{i\geq 0}$ $Q(x,y)$ $p$ $\phi_p$ $y$ $Q(p,y)$ $Q$ $x=y$ $p$ $\phi_p(y) = Q(p,y)$ $\phi_p$ $p$ et rejette toutes les autres entrées.

David Richerby
la source

Dans quel sens chaque programme de cette langue est-il un compilateur pour cette langue? Chaque programme est un programme qui entre un programme dans cette langue et produit un programme différent dans cette langue, oui, mais les quines ne sont généralement pas considérées comme des compilateurs.

user253751

Je pense que @immibis a un point: votre compilateur est alors que tous les programmes du langage sont , donc n'est clairement pas dans la langue. Suis-je en train de manquer quelque chose?

c

$c$

c (P) = {x \Rightarrow r e t u r n P}

$c(P) = \{ x \Rightarrow \mathtt{return}\ P \}$

P (x) = P

$P(x) = P$

c

$c$

Raphael

@immibis Je pense (tardivement) que vous avez raison. Il semble que ce que je voulais écrire était que la sémantique de chaque programme soit simplement "sortir votre entrée". Cela semble assez proche de ce que j'ai écrit que c'était probablement ce que je voulais dire en premier lieu. Ou peut-être que j'ai eu beaucoup de chance que la distance de modification entre ma mauvaise réponse et la bonne réponse était si petite. :-)

David Richerby

La réponse dit maintenant "ignore son entrée et sort une copie de son entrée" - vous ne pouvez pas faire les deux.

user253751

@immibis je reviendrai .

David Richerby