Une langue totale que seule une langue complète de Turing peut interpréter

Toute langue qui n'est pas complète de Turing ne peut pas écrire elle-même un interprète. Je n'ai aucune idée de l'endroit où je l'ai lu, mais je l'ai vu utilisé à plusieurs reprises. Il semble que cela donne lieu à une sorte de langage complet «ultime» non Turing; celui (s) qui ne peutêtre interprété par une machine de Turing. Ces langages ne seraient pas nécessairement capables de calculer toutes les fonctions totales des naturels aux naturels, ni nécessairement isomorphes (c'est-à-dire que les langages ultimes A et B existent de telle sorte qu'il existe une fonction F que A peut calculer mais B ne peut pas). Agda peut interpréter le système T de Godel et Agda est total, de sorte qu'un langage aussi ultime devrait être strictement plus puissant que le système T de Godel semble-t-il. Il me semble qu'un tel langage serait au moins aussi puissant que agda (même si je n'ai aucune preuve, juste un pressentiment).

Des recherches ont-elles été faites dans ce sens? Quels résultats sont connus (à savoir est-ce qu'un tel langage "ultime" est connu)?

Bonus: je crains qu'il existe un cas pathologique qui ne peut pas calculer des fonctions que le système T de Godel pourrait encore ne peut être interprété que par une machine de Turing car il permet de calculer des fonctions vraiment étranges. Est-ce le cas ou pouvons-nous savoir qu'un tel langage serait capable de calculer tout ce que le système T de Godel pourrait calculer?

C'est une question mal formulée, alors essayons d'abord de la comprendre. Je vais le faire dans le style de la théorie de la calculabilité. Ainsi j'utiliserai des nombres au lieu de chaînes: un morceau de code source est un nombre, plutôt qu'une chaîne de symboles. Cela n'a pas vraiment d'importance, vous pouvez remplacer par tout au long ci-dessous.s t r i n $\mathbb{N}$$\mathtt{string}$

Soit une fonction d'appariement .$\langle m, n\rangle$

Disons qu'un langage de programmation est donné par les données suivantes:$L = (P, ev)$

1. un ensemble décidable de "programmes valides", et$P \subseteq \mathbb{N}$
2. une calculable et partielle fonction .$ev : P \times \mathbb{N} \to \mathbb{N}$

Le fait que soit décidable signifie qu'il existe une carte calculable totale v a l i d : N → { 0 , 1 } telle que v a l i d ( n ) = $P$$valid : \mathbb{N} \to \{0,1\}$ . De manière informelle, nous disons qu'il est possible de dire si une chaîne donnée est un morceau de code valide. La fonction e v est essentiellement un interprète pour notre langage: e v ( m , n ) exécute le code m sur l'entrée n - le résultat peut être indéfini.$valid(n) = 1 \iff n \in P$$ev$$ev(m,n)$$m$$n$

Nous pouvons maintenant introduire une terminologie:

1. Une langue est totale si est une fonction totale pour tous les m ∈ P .$n \mapsto ev(m,n)$$m \in P$
2. Une langue interprète la langue L 2 = $L_1 = (P_1, ev_1)$ s'il existe u ∈ P 1 de telle sorte que e v 1 ( u , ⟨ n , m ⟩ ) ≃ e v 2 ( n , m ) pour tout n ∈ $L_2 = (P_2, ev_2)$$u \in P_1$$ev_1(u, \langle n, m \rangle) \simeq ev_2(n, m)$$n \in P$et . Ici u est le simulateur pour L 2 implémenté dans L 1 . Il est également connu sous le nom de programme universel pour L 2 .$m \in \mathbb{N}$$u$$L_2$$L_1$$L_2$

D'autres définitions de " interprète L 2 " sont possibles, mais je ne vais pas entrer dans le détail maintenant.$L_1$$L_2$

On dit que et L 2 sont équivalents s’ils s’interprètent.$L_1$$L_2$

Il y a le langage "le plus puissant" des machines de Turing (que vous appelez "une machine de Turing") dans lequel n ∈ N est un codage d'une machine de Turing et φ ( n , m ) est la fonction calculable partielle qui "exécute l'encodage de la machine de Turing par n sur l'entrée m ". Ce langage peut intercepter tous les autres langages, évidemment car nous avions besoin que e v soit calculable.$T = (\mathbb{N}, \varphi)$$n \in \mathbb{N}$$\varphi(n,m)$$n$$m$$ev$

Notre définition des langages de programmation est très détendue. Pour que les éléments suivants passent, exigons trois autres conditions:

• implémente la fonction successeur: il y a s u c c ∈ P tel que e v ( s u c c , m ) = m + 1 pour tout m ∈ N ,$L$$succ \in P$$ev(succ,m) = m+1$$m \in \mathbb{N}$
• implémente la fonction diagonale: il n'y a ; d i a g ∈ P de telle sorte que e v ( D i a g , m ) = ⟨ m , m ⟩ pour tout m ∈ N ,$L$$diag \in P$$ev(diag,m) = \langle m, m \rangle$$m \in \mathbb{N}$
• est fermé sous la composition des fonctions: si L implémente f et g alors il implémente également f ∘ g ,$L$$L$$f$$g$$f \circ g$

Un résultat classique est le suivant:

Théorème: si une langue peut s'interpréter elle-même, elle n'est pas totale.

Preuve. Supposons que est le programme universel pour un langauge totale L mis en œuvre en L , à savoir, pour tout m ∈ P et n ∈ N , $u$$L$$L$$m \in P$$n \in \mathbb{N}$ Comme successeur, diagonale et e v ( u , - ) sont implémentées dans L , il en est de même de leur composition k

$$ev(u, \langle m, n \rangle) \simeq ev(m, n).$$ $ev(u, {-})$$L$ . Il existe n 0 ∈ P de telle sorte que e v ( n 0 , k ) ≃ e v ( u , ⟨ k , k ⟩ ) + 1 , puis e v ( u , ⟨ n 0 , n 0 ⟩ ) ≃ e v $k \mapsto ev(u, \langle k, k \rangle) + 1$$n_0 \in P$$ev(n_0, k) \simeq ev(u, \langle k, k \rangle) + 1$ Comme il n'y a pasnombre égal son successeur, il résulte que L est non totale ou que L ne s'interprète pas. QED. $$ev(u, \langle n_0, n_0\rangle) \simeq ev(n_0, n_0) \simeq ev(u, \langle n_0, n_0 \rangle) + 1$$ $L$$L$

Observez que nous pourrions remplacer la carte successeur par toute autre carte sans point fixe.

Voici un petit théorème qui, je pense, effacera un malentendu.

Théorème: Chaque langue totale peut être interprétée par une autre langue totale.

Preuve. Soit une langue totale. On obtient un total L ' qui interprète L en accolant à L son évaluateur e v . Plus précisément, soit P ' = { ⟨ 0 , n ⟩ | ) = { e v ( n , m ) si  b = 0 , e v ( m 0 , m 1 ) si  b = $L$$L'$$L$$L$$ev$ et définir e v ' comme e v ' ( ⟨ b , n ⟩ , $P' = \{\langle 0, n\rangle \mid n \in P\} \cup \{\langle 1, 0\rangle\}$$ev'$ De toute évidence,L'est totale carLest totale. Pour voir queL'peut simulerLil suffitprendreu=⟨1,

$$ev'(\langle b, n \rangle, m) = \begin{cases} ev(n,m) & \text{if $b = 0$},\\ ev(m_0, m_1) & \text{if $b = 1$ and $m = \langle m_0, m_1 \rangle$} \end{cases}$$ $L'$$L$$L'$$L$ , Depuis lors e v ' ( u , ⟨ m , n ⟩ ) ≃ e v ( m , n ) , selonbesoins. QED.$u = \langle 1, 0\rangle$$ev'(u, \langle m, n\rangle) \simeq ev(m, n)$

Exercice: [ajouté le 2014-06-27] Le langage construit ci-dessus n'est pas fermé sous composition. Fixer la preuve du théorème pour que L ′ satisfasse aux exigences supplémentaires si L le fait.$L'$$L'$$L$

En d'autres termes, vous n'avez jamais besoin de la pleine puissance des machines de Turing pour interpréter un langage total - un langage total légèrement plus puissant L ' suffit. Le langage L ' est strictement plus puissant que L car il interprète L , mais L ne s'interprète pas lui-même.$L$$L'$$L'$$L$$L$$L$

Toute langue qui n'est pas complète de Turing ne peut pas écrire elle-même un interprète.

Cette déclaration est incorrecte. Considérez le langage de programmation dans lequel la sémantique de chaque chaîne est "Ignorez votre entrée et arrêtez immédiatement". Ce langage de programmation n'est pas Turing complet mais chaque programme est un interprète du langage.